HashMap Java 8 mise en œuvre
Que par le lien suivant document: Java HashMap Mise En Œuvre
Je suis confus avec la mise en œuvre de HashMap
(ou plutôt, une amélioration dans HashMap
). Mes questions sont:
Tout d'abord
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
Pourquoi et comment sont ces constantes utilisées? Je veux des exemples de cette.
La manière dont ils sont la réalisation d'un gain de performance avec cette?
Deuxièmement
Si vous consultez le code source de HashMap
dans le JDK, vous trouverez ci-après statique intérieur de la classe:
static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
HashMap.TreeNode<K, V> parent;
HashMap.TreeNode<K, V> left;
HashMap.TreeNode<K, V> right;
HashMap.TreeNode<K, V> prev;
boolean red;
TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
super(arg0, arg1, arg2, arg3);
}
final HashMap.TreeNode<K, V> root() {
HashMap.TreeNode arg0 = this;
while (true) {
HashMap.TreeNode arg1 = arg0.parent;
if (arg0.parent == null) {
return arg0;
}
arg0 = arg1;
}
}
//...
}
Comment est-il utilisé? Je veux juste une explication de l'algorithme.
Vous devez vous connecter pour publier un commentaire.
HashMap
contient un certain nombre de compartiments. Il utilisehashCode
pour déterminer le seau à les mettre en. Pour des raisons de simplicité l'imaginer comme un module.Si notre hashcode est 123456 et nous avons 4 seaux,
123456 % 4 = 0
afin que l'élément va dans le premier seau, Seau 1.Si notre hashcode de la fonction est bonne, il doit fournir une répartition uniforme de sorte que tous les compartiments sera utilisé un peu aussi. Dans ce cas, le seau utilise une liste liée à stocker les valeurs.
Mais vous ne pouvez pas compter sur les gens pour mettre en place les bonnes fonctions de hachage. Les gens vont souvent écrire des pauvres des fonctions de hachage qui aboutira à un non-même de la distribution. Il est également possible que nous pourrions juste pas de chance avec nos entrées.
Le moins, même cette distribution est, plus nous avançons en O(1) opérations et plus nous nous dirigeons vers O(n) opérations.
La mise en œuvre de la Hashmap tente d'atténuer ce, par l'organisation de certains compartiments des arbres plutôt que des listes liées si les seaux devient trop grand. C'est ce que
TREEIFY_THRESHOLD = 8
est pour. Si un seau contient plus de huit éléments, il devrait devenir un arbre.C'est un arbre Rouge-Noir arbre. Il est tout d'abord triés par code de hachage. Si le hash codes sont les mêmes, il utilise le
compareTo
méthode deComparable
si les objets à implémenter cette interface, sinon l'identité de code de hachage.Si les entrées sont supprimées de la carte, le nombre d'entrées dans le seau peut réduire, de sorte que cette structure de l'arbre n'est plus nécessaire. C'est ce que l'
UNTREEIFY_THRESHOLD = 6
est pour. Si le nombre d'éléments dans un seau descend au-dessous de six, nous pourrions aussi bien aller en arrière à l'aide d'une liste liée.Enfin, il y a le
MIN_TREEIFY_CAPACITY = 64
.Lorsqu'un hachage de la carte augmente en taille, il redimensionne automatiquement pour avoir plus de seaux. Si nous avons une petite carte de hachage, le risque de nous arriver très seaux pleins est assez élevé, parce que nous n'avons pas qui ont de nombreux compartiments différents pour mettre des trucs dans. C'est beaucoup mieux d'avoir un plus gros hachage de la carte, avec plus de seaux qui sont moins complète. Cette constante indique fondamentalement de ne pas commencer à faire des seaux dans les arbres si notre hash map est très petite, il devrait redimensionner à être plus première place.
Pour répondre à votre question au sujet de le gain de performance, ces optimisations ont été ajoutés pour améliorer le pire cas. Je ne fais que spéculer, mais vous auriez probablement seulement voir une notable amélioration de la performance en raison de ces optimisations si votre
hashCode
fonction n'a pas été très bonne.Images sont à moi (merci MSPaint). De les réutiliser comme bon vous semble.
String
, ont une bien plus grande valeur de l'espace de laint
hashcode, par conséquent, les collisions sont inévitables. Maintenant, il dépend de la valeur réelle, comme de véritablesString
s, que vous mettez dans la map, si vous obtenez une distribution uniforme ou pas. Une mauvaise distribution peut être le résultat de la juste de la malchance.java.lang.String
a un déterministe, non cryptographiquehashCode
, de sorte que les attaquants peuvent trivialement créer des Chaînes de caractères avec la collision hashCodes. Avant cette optimisation, ce qui pourrait dégrader la HashMap opérations de O(n) en temps, maintenant, il se dégrade à O(log(n)).if the objects implement that interface, else the identity hash code.
j'étais à la recherche de cette autre partie.Pour le placer plus simple (autant que je le pouvais plus simple) + un peu plus de détails.
Ces propriétés dépendent beaucoup de l'intérieur des choses, ce serait très cool de le comprendre avant de le déplacer directement.
TREEIFY_THRESHOLD -> quand un unique seau est atteint (et le nombre total dépasse
MIN_TREEIFY_CAPACITY
), il est transformé en un parfaitement équilibré rouge/noir nœud de l'arborescence de. Pourquoi? En raison de la vitesse de recherche. Pensez à ce sujet d'une manière différente:Certaines intro pour le sujet suivant. Pourquoi le nombre de bacs/seaux toujours une puissance de deux? Au moins deux raisons: plus rapide que modulo et modulo sur les nombres négatifs sera négatif. Et vous ne pouvez pas mettre une Entrée dans le "négatif" seau:
Au lieu il y a une belle astuce utilisée à la place de modulo:
Qui est sémantiquement le même que modulo. Il va garder les bits de poids faible. Cela a une conséquence interessante lorsque vous faites:
C'est là multipliant les seaux entre en jeu. Sous certaines conditions (qui prendra beaucoup de temps à expliquer dans détails exacts), les seaux sont doublé de taille. Pourquoi? Quand les seaux sont doublé de taille, il y a un peu plus jouer.
Comme tel, ce processus est appelé re-hachage. Ce peut être lente. C'est (pour les personnes qui prennent soin) comme HashMap est "plaisanté" comme: rapide, rapide, rapide, slooow. Il existe d'autres implémentations de recherche pauseless hashmap...
Maintenant UNTREEIFY_THRESHOLD entre en jeu après re-hachage. À ce stade, certaines entrées peuvent se déplacer à partir de ce bacs à d'autres (ils ajoutent un peu plus à l'
(n-1)&hash
calcul et comme tel, il peut se déplacer à autres seaux) et il pourrait atteindre ceUNTREEIFY_THRESHOLD
. À ce stade, il n'est pas rentable de garder le bacred-black tree node
, mais comme unLinkedList
au lieu de cela, commeMIN_TREEIFY_CAPACITY est le nombre minimum de seaux avant une certaine seau est transformée en un Arbre.
TreeNode
est une autre manière de stocker les entrées qui appartiennent à un seul bin de laHashMap
. Dans les anciennes implémentations les entrées d'un bac ont été stockés dans une liste chaînée. Dans Java 8, si le nombre d'entrées dans une poubelle, passée un seuil (TREEIFY_THRESHOLD
), ils sont stockés dans une structure de l'arbre au lieu de l'original de la liste liée. Cette optimisation.De la mise en œuvre:
TREEIFY_THRESHOLD
ET le nombre total de caisses est au moinsMIN_TREEIFY_CAPACITY
. J'ai essayé de couvrir que dans ma réponse...Vous auriez besoin de le visualiser: dire qu'il y a une Clé de Classe avec seulement hashCode() de la fonction substituée retourne toujours la même valeur
et puis quelque part d'autre, je suis l'insertion de 9 entrées dans une table de hachage avec toutes les clés étant les instances de cette classe. par exemple,
L'arbre transversal est plus rapide {O(log n)} que LinkedList {O(n)} et à mesure que n augmente, la différence devient de plus en plus importante.
compareTo
deComparable
.identityHashCode
est un autre mécanisme qu'il utilise.Key
ne pas mettre en œuvreComparable
,identityHashCode
sera utilisé 🙂static final int MIN_TREEIFY_CAPACITY = 64;
, d'où vient cette variable entre en image. Conformément à la réponse ci-dessus, les seaux ne serait pas converti à l'arbre, à moins que le nombre de compartiments a atteintstatic final int MIN_TREEIFY_CAPACITY = 64;
Le changement dans la table de hachage de la mise en œuvre a été ajouté avec JEP-180. Le but était de:
Cependant performance pure n'est pas le seul gain. Il sera également empêcher HashDoS attaque, dans le cas d'un hachage de la carte est utilisé pour stocker les entrées de l'utilisateur, parce que le rouge-noir arbre qui est utilisé pour stocker des données dans le seau a pire des cas, l'insertion de la complexité en O(log n). L'arbre est utilisé après un certains critères sont remplis - voir Eugène réponse.
De comprendre la mise en œuvre interne de la table de hachage, vous devez comprendre le hachage.
Le hachage dans sa forme la plus simple, est une autre manière à l'attribution d'un code unique pour toute variable/objet après l'application de la formule de/l'algorithme sur ses propriétés.
Une véritable fonction de hachage doit suivre cette règle –
“Fonction de hachage doit renvoyer le même code de hachage de chaque et chaque fois que la fonction est appliquée sur même ou égale objets. En d'autres termes, deux objets égaux doit produire le même code de hachage de constance.”