Falsche Idee, String-Schlüssel in HashMap zu verwenden?

Entwickler müssen das Problem der Hash-Kollisionen in HashMap nicht umgehen, um die Programmkorrektheit zu erreichen.

Hier sind einige wichtige Dinge zu verstehen:

1. Kollisionen sind ein inhärentes Merkmal von Hashing und müssen es auch sein. Die Anzahl der möglichen Werte (Strings in Ihrem Fall, gilt aber auch für andere Typen) ist erheblich größer als der Bereich der Ganzzahlen.
2. Jede Verwendung von Hashing hat eine Möglichkeit, mit Kollisionen umzugehen, und die Java Collections (einschließlich HashMap) sind keine Ausnahme.
3. Hashing ist nicht an Gleichheitstests beteiligt. Es ist wahr, dass gleiche Objekte gleiche Hashcodes haben müssen, aber das Gegenteil ist nicht der Fall: Viele Werte haben denselben Hashcode. Versuchen Sie also nicht, einen Hashcode-Vergleich als Ersatz für Gleichheit zu verwenden. Sammlungen nicht. Sie verwenden Hashing, um eine Untersammlung (in der Java Collections-Welt) als Bucket bezeichnet) auszuwählen, verwenden jedoch .equals (), um tatsächlich die Gleichheit zu überprüfen.
4. Sie müssen sich nicht nur keine Gedanken über Kollisionen machen, die zu falschen Ergebnissen in einer Sammlung führen, sondern für die meisten Anwendungen müssen Sie sich * normalerweise * auch keine Gedanken über die Leistung machen - Java hashed Collections do a ziemlich gute Arbeit bei der Verwaltung von Hashcodes.
5. Besser noch, für den Fall, dass Sie nach (Strings as keys) gefragt haben, müssen Sie sich nicht einmal um die Hashcodes selbst kümmern, da die String-Klasse von Java einen ziemlich guten Hashcode generiert. Tun Sie so die meisten der gelieferten Klassen Java.

Noch ein paar Details, wenn Sie es wollen:

Die Funktionsweise von Hashing (insbesondere bei Hashing-Sammlungen wie der HashMap von Java, nach der Sie gefragt haben) ist folgende:

• Die HashMap speichert die von Ihnen angegebenen Werte in einer Sammlung von Untersammlungen, die als Buckets bezeichnet werden. Diese sind tatsächlich als verknüpfte Listen implementiert. Es gibt eine begrenzte Anzahl von diesen: iirc, 16, um standardmäßig zu starten, und die Anzahl erhöht sich, wenn Sie mehr Elemente in die Karte einfügen. Es sollte immer mehr Eimer als Werte geben. Um ein Beispiel zu geben: Wenn Sie unter Verwendung der Standardeinstellungen 100 Einträge zu einer HashMap hinzufügen, gibt es 256 Buckets.

• Jeder Wert, der als Schlüssel in einer Karte verwendet werden kann, muss in der Lage sein, einen ganzzahligen Wert, den so genannten Hashcode, zu generieren.

• Die HashMap verwendet diesen Hashcode, um einen Bucket auszuwählen. Letztendlich bedeutet dies, dass der ganzzahlige Wert modulo für die Anzahl der Buckets verwendet wird. Zuvor verfügt Javas HashMap jedoch über eine interne Methode (hash()), mit der der Hashcode optimiert wird, um einige bekannte Quellen von zu reduzieren klumpen.

• Bei der Suche nach einem Wert wählt die HashMap den Bucket aus und sucht dann nach dem einzelnen Element durch eine lineare Suche in der verknüpften Liste mit .equals().

Also: Sie müssen Kollisionen nicht umgehen, um die Korrektheit zu gewährleisten, und Sie müssen sich normalerweise keine Sorgen um die Leistung machen, und wenn Sie native Java Klassen (wie String) verwenden. müssen Sie sich auch nicht um die Generierung der Hashcode-Werte kümmern.

In dem Fall, dass Sie Ihre eigene Hashcode-Methode schreiben müssen (was bedeutet, dass Sie eine Klasse mit einem zusammengesetzten Wert geschrieben haben, wie z. B. ein Vorname/Nachname-Paar), wird die Sache etwas komplizierter. Es ist durchaus möglich, hier etwas falsch zu machen, aber es ist keine Raketenwissenschaft. Beachten Sie zunächst Folgendes: Das einzige, was Sie tun müssen, um die Richtigkeit sicherzustellen, ist sicherzustellen, dass gleiche Objekte gleiche Hashcodes ergeben. Wenn Sie also eine hashcode () -Methode für Ihre Klasse schreiben, müssen Sie auch eine equals () -Methode schreiben und die gleichen Werte in jeder prüfen.

Es ist möglich, eine Hashcode () -Methode zu schreiben, die zwar schlecht, aber korrekt ist, mit der ich meine, dass sie die Bedingung "Gleiche Objekte müssen gleiche Hashcodes ergeben" erfüllen würde, aber dennoch sehr schlecht abschneidet, wenn sie viele Kollisionen aufweist.

Der kanonisch entartete schlimmste Fall wäre das Schreiben einer Methode, die für alle Fälle einfach einen konstanten Wert (z. B. 3) zurückgibt. Dies würde bedeuten, dass jeder Wert in denselben Bucket gehasht wird.

Es würde immer noch funktionieren, aber die Leistung würde sich auf die einer verknüpften Liste verschlechtern.

Offensichtlich werden Sie keine so schreckliche hashcode () -Methode schreiben. Wenn Sie eine anständige IDE verwenden, kann sie eine für Sie generieren. Da StackOverflow Code liebt, ist hier der Code für die oben genannte Vor-/Nachname-Klasse.

public class SimpleName {
    private String firstName;
    private String lastName;
    public SimpleName(String firstName, String lastName) {
        super();
        this.firstName = firstName;
        this.lastName = lastName;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result
                + ((lastName == null) ? 0 : lastName.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SimpleName other = (SimpleName) obj;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }
}