HashMap question de mise en œuvre

Question

HashMap contient une table de hachage qui est un tableau qui détiennent les valeurs

comme je l'ai compris la table de hachage a une taille initiale, mais il peut s'augmenté après beaucoup d'invocation de mettre() (dépend sur le facteur de charge)

de toute façon je me demande comment vous pouvez trouver une valeur après avoir changé la taille de la table de hachage parce que je sais que pour calculer le code de la clé spécifique, vous pouvez utiliser la taille de la table

par exemple touche * prime% taille

alors comment ça marche?

Answer 1

Visage répond à la question en général: les valeurs de hachage calculées à partir des clés sont mis en correspondance avec les seaux en les répartissant modulo la taille réelle de la carte, et lorsque la carte est redimensionnée, tous les éléments sont répartis à nouveau sur la nouvelle gamme de godets. Cependant, à partir de Java 1.4, il y a quelques choses derrière le rideau qui valent la peine d'être connues. Tout d'abord, dans une carte de hachage traditionnelle, la taille est idéalement un nombre premier, car cela permet de répartir les éléments plus uniformément sur la gamme de seaux. Cependant, dans le Java 1.4 HashMap, la taille est toujours une puissance de deux! Cela rendrait la distribution standard très mauvaise - cependant, dans cette implémentation, les valeurs de hachage sont recopiées en interne en utilisant un algorithme très rapide pour lisser la distribution.

Plus de détails dans les bulletins d'information Java spécialisés, numéros 54 et 54b.

Answer 2

Parce que la clé est généralement utilisée pour localiser la corbeille dans laquelle votre valeur a été placée. La réaffectation n'affecte pas cela, puisque tous les objets sont réaffectés à de nouveaux emplacements en fonction de la nouvelle taille.

Answer 3

Si vous regardez le code de la méthode addEntry(..), vous voyez:

if (size++ >= threshold) 
    resize(2 * table.length); 

Sur le redimensionnement, la méthode transfer(..) est appelée, qui:

Transferts toutes les entrées de la table en cours de NEWTABLE .