indexFor dans hashmap ?

Question

J'essaie juste de me faire une idée du fonctionnement de Java HashMap en regardant le code. Lorsqu'un élément est ajouté, il se passe ce qui suit :

1. le code de hachage de la clé est obtenu
2. une fonction de hachage est appliquée sur le résultat
3. la méthode indexFor est appliquée sur le résultat de 2. Cela donne la première entrée dans le seau approprié. La liste liée dans le seau est ensuite itérée - la fin est trouvée et l'élément est ajouté.

En mise en œuvre d'indexO f est :

int indexOf(int h, int length) {
     return h & (length-1);
}

Je ne comprends pas le truc qui se passe dans la méthode indexOf. Quelqu'un peut-il l'expliquer ?

Gracias.

Answer 1

Cela fonctionne parce que Java HashMaps ont toujours une capacité, c'est-à-dire le nombre de seaux, égale à une puissance de 2. Travaillons avec une capacité de 256, soit 0x100, mais cela pourrait fonctionner avec n'importe quelle puissance de 2. En soustrayant 1 d'une puissance de 2, on obtient le masque binaire exact nécessaire pour obtenir, par bit et avec le hachage, l'index de seau correct, de l'ordre de 0 a length - 1 .

256 - 1 = 255
0x100 - 0x1 = 0xFF

Par exemple, un hachage de 257 (0x101) est soumis à un mélange de bits avec 0xFF pour obtenir un numéro de seau de 1.