wake-up-neo.net

Welche Hashfunktion verwendet Java zur Implementierung der Hashtable-Klasse?

Aus dem Buch CLRS ("Einführung in Algorithmen") gibt es verschiedene Hashfunktionen wie mod, multiplizieren usw. 

Welche Hash-Funktion verwendet Java zur Zuordnung der Schlüssel zu Slots?

Ich habe gesehen, dass hier eine Frage Hashing-Funktion in Java Language verwendet wird. Aber es beantwortet die Frage nicht, und ich denke, dass die markante Antwort auf diese Frage falsch ist. Es sagt, dass hashCode () Sie Ihre eigene Hash-Funktion für Hashtable ausführen lässt, aber ich denke, dass es falsch ist.

Die von hashCode () zurückgegebene Ganzzahl ist der eigentliche Schlüssel für Hashtble, dann verwendet Hashtable eine Hashfunktion, um den Hashcode zu hashieren. Diese Antwort impliziert, dass Java die Möglichkeit bietet, Hashtable eine Hashfunktion zu geben, aber nein, das ist falsch. hashCode () gibt den echten Schlüssel an, nicht die Hash-Funktion.

Was genau verwendet die Hash-Funktion also Java?

47
Jackson Tale

Wenn ein Schlüssel zu einer HashMap in OpenJDK hinzugefügt oder von dieser angefordert wird, ist der Ablauf der Ausführung der folgende:

  1. Der Schlüssel wird mit der vom Entwickler definierten hashCode()-Methode in einen 32-Bit-Wert umgewandelt.
  2. Der 32-Bit-Wert wird dann durch eine zweite Hash-Funktion (von der Andrews Antwort den Quellcode enthält) in einen Offset innerhalb der Hash-Tabelle umgewandelt. Diese zweite Hash-Funktion wird von der Implementierung von HashMap bereitgestellt und kann vom Entwickler nicht überschrieben werden.
  3. Der entsprechende Eintrag der Hashtabelle enthält einen Verweis auf eine verknüpfte Liste oder Null, wenn der Schlüssel noch nicht in der Hashtabelle vorhanden ist. Bei Kollisionen (mehrere Schlüssel mit demselben Versatz) werden die Schlüssel zusammen mit ihren Werten einfach in einer einfach verknüpften Liste gesammelt.

Wenn die Hashtabellengröße entsprechend hoch gewählt wurde, ist die Anzahl der Kollisionen begrenzt. Daher dauert eine einzelne Suche im Durchschnitt nur eine konstante Zeit. Dies wird als erwartete konstante Zeit bezeichnet. Wenn ein Angreifer jedoch die Kontrolle über die in eine Hash-Tabelle eingefügten Schlüssel hat und Kenntnis über den verwendeten Hash-Algorithmus hat, kann er viele Hash-Kollisionen auslösen und daher eine lineare Suchzeit erzwingen. Aus diesem Grund wurden einige Hashtabellenimplementierungen kürzlich dahingehend geändert, dass sie ein Zufallselement enthalten, das es einem Angreifer erschwert, vorherzusagen, welche Schlüssel Kollisionen verursachen.

Einige ASCII Kunst

key.hashCode()
     |
     | 32-bit value
     |                              hash table
     V                            +------------+    +----------------------+
HashMap.hash() --+                | reference  | -> | key1 | value1 | null |
                 |                |------------|    +----------------------+
                 | modulo size    | null       |
                 | = offset       |------------|    +---------------------+
                 +--------------> | reference  | -> | key2 | value2 | ref |
                                  |------------|    +---------------------+
                                  |    ....    |                       |
                                                      +----------------+
                                                      V
                                                    +----------------------+
                                                    | key3 | value3 | null |
                                                    +----------------------+
91
Niklas B.

Gemäß der Quelle von Hashmap wird jeder Hashcode mit der folgenden Methode gehasht:

 /**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Der Grund dafür, dass jeder Hashcode erneut gehasht wird, ist das weitere Vermeiden einer Kollision (siehe Kommentare oben).

HashMap verwendet auch eine Methode, um den Index eines Hash-Codes zu bestimmen (da length immer eine Potenz von 2 ist, können Sie & anstelle von% verwenden):

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

Die Put-Methode sieht ungefähr so ​​aus:

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

Der Zweck eines Hash-Codes besteht darin, eine eindeutige Ganzzahldarstellung für ein gegebenes Objekt bereitzustellen. Es ist daher sinnvoll, dass die hasCode-Methode von Integer den Wert einfach zurückgibt, da jeder Wert für dieses Integer-Objekt eindeutig ist.

27
Andrew Liu

Hashing ist im Allgemeinen in zwei Schritte unterteilt: A. HashCode B. Komprimieren

In Schritt a. Es wird eine Ganzzahl generiert, die Ihrem Schlüssel entspricht. Dies kann von Ihnen in Java geändert werden.

In Schritt b. Eine Komprimierungstechnik wird von Java angewendet, um die von Schritt a zurückgegebene Ganzzahl abzubilden. zu einem Slot in der Hashmap oder Hashtabelle. Diese Komprimierungstechnik kann nicht geändert werden.

4

Ich denke, das Konzept ist verwirrend. Eine Hash-Funktion ordnet eine Eingabe mit variabler Größe einer Ausgabe mit fester Größe (dem Hash-Wert) zu. Bei Java-Objekten ist die Ausgabe eine 32-Bit-Ganzzahl mit Vorzeichen.

Javas Hashtable verwendet den Hashwert als Index für ein Array, in dem das eigentliche Objekt gespeichert wird, wobei die Modulo-Arithmetik und Kollisionen berücksichtigt werden. Dies ist jedoch kein Hashing.

Die Java.util.HashMap-Implementierung führt vor der Indizierung einige zusätzliche Bit-Swapping-Werte für den Hash-Wert aus, um in einigen Fällen vor übermäßigen Kollisionen zu schützen. Es wird "zusätzlicher Hash" genannt, aber ich denke nicht, dass dies ein korrekter Begriff ist.

0
forty-two
/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Dies ist die neueste Hash-Funktion, die von der HashMap-Klasse in Java verwendet wird

0
Avinash