Quelle fonction de hachage Java utilise-t-il pour implémenter Hashtable class?
du livre CLRS ("Introduction to Algorithms"), il existe plusieurs fonctions de hachage, telles que mod, multiply, etc.
quelle fonction de hachage Java utilise-t-il pour mapper les clés des machines à sous?
j'ai vu qu'il y a une question ici fonction de hachage utilisé dans le langage Java . Mais il ne répond pas à la question, et je pense que la réponse marquée pour cette question est fausse. Il est dit que hashCode () vous permet de faire votre propre hachage la fonction de table de hachage, mais je pense que c'est à tort.
le nombre entier retourné par hashCode() est la vraie clé pour Hashtble, puis Hashtable utilise une fonction de hachage pour hachurer le hashCode(). Ce que cette réponse implique, C'est que Java vous donne une chance de donner au Hashtable une fonction de hashing, mais non, c'est faux. hashCode() donne la vraie clé, pas la fonction de hachage.
alors quelle est exactement la fonction de hachage que Java utilise?
5 réponses
Lorsqu'une clé est ajoutée ou demandée à un HashMap dans OpenJDK, le flux d'exécution est le suivant:
- la clé est transformée en une valeur de 32 bits en utilisant la méthode
hashCode()définie par le développeur. - la valeur de 32 bits est alors transformée par une seconde fonction de hachage (dont la réponse D'Andrew contient le code source) en un décalage à l'intérieur de la table de hachage. Cette seconde fonction de hachage est fournie par la mise en œuvre de HashMap et ne peut pas être annulée par le développeur.
- L'entrée correspondante de la table de hachage contient une référence à une liste, ou la valeur null si la clé n'existe pas encore dans la table de hachage. S'il y a des collisions (plusieurs clés avec le même décalage), les clés ainsi que leurs valeurs sont simplement collectées dans une liste liée.
si la taille de la table de hachage a été choisie de manière appropriée, le nombre de collisions sera limitée. Ainsi, une seule recherche ne prend en moyenne que du temps constant. Cela s'appelle temps constant attendu . Cependant, si un attaquant a le contrôle sur les clés insérées dans une table de hachage et la connaissance de l'algorithme de hachage en usage, il peut provoquer beaucoup de collisions de hachage et donc forcer le temps de recherche linéaire. C'est pourquoi certaines implémentations de tables de hachage ont été modifiées récemment pour inclure un élément aléatoire qui rend plus difficile pour un attaquant de prédire les clés provoqueront des collisions.
Some ASCII art
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 |
+----------------------+
selon la source de hashmap, chaque hashCode est hashé en utilisant la méthode suivante:
/**
* 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);
}
la raison pour laquelle chaque hashCode est de nouveau hashé, est de prévenir davantage d'une collision (voir les commentaires ci-dessus)
HashMap utilise également une méthode pour déterminer l'index d'un code de hachage (puisque la longueur est toujours une puissance de 2, Vous pouvez utiliser & au lieu du%):
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
la méthode put ressemble à quelque chose comme:
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
le but d'un code de hachage est de fournir une représentation entière unique pour un objet donné. Il est logique, alors, que la méthode hashCode D'entier renvoie simplement la valeur parce que chaque valeur serait unique à cet objet entier.
Hashing en général se divise en deux étapes: un. HashCode B. Compression
dans l'étape a. un entier correspondant à votre clé est généré. Ceci peut être modifié par vous en Java.
à l'étape B. une technique de compression est appliquée par Java pour mapper l'entier retourné par l'étape a. à une fente dans le hashmap ou hashtable. Cette technique de compression ne peut pas être modifiée.
je pense qu'il y a une certaine confusion au sujet du concept ici. Une fonction de hachage fait correspondre une entrée de taille variable à une sortie de taille fixe (la valeur de hachage). Dans le cas d'objets Java, la sortie est un entier signé 32 bits.
le Hashtable de Java utilise la valeur de hachage comme un index dans un tableau où l'objet réel est stocké, en tenant compte de l'arithmétique modulo et des collisions. Cependant, ce n'est pas le hachage.
La java.util.HashMap mise en œuvre effectue un échange de bits supplémentaires sur la valeur de hachage avant l'indexation pour protéger contre les collisions excessives dans certains cas. On l'appelle "hash supplémentaire", mais je ne pense pas que ce soit un terme correct.
pour le mettre d'une manière très simple le deuxième hachage n'est rien d'autre que de trouver le numéro d'index du tableau de seau où la nouvelle paire de valeur de clé sera stockée. Ce mapping est fait pour obtenir le numéro d'index à partir de la plus grande valeur int du hashcode de la clé obj. Maintenant si deux objets clés inégaux ont le même code de hachage alors la collision se produira car ils seront mappés au même index de tableau. Dans ce cas, la deuxième clé ainsi que sa valeur seront ajoutées à la liste liée. Ici le tableau index pointera vers le dernier noeud ajouté.