OpenJDK's rehashing-mechanisme

Question

OpenJDK's rehashing-mechanisme

Vond deze code op http://www.docjar.com/html /api/java/util/HashMap.java.html na het zoeken naar een HashMap-implementatie.

  264       static int hash(int h) {
  265          //This function ensures that hashCodes that differ only by
  266          //constant multiples at each bit position have a bounded
  267          //number of collisions (approximately 8 at default load factor).
  268           h ^= (h >>> 20) ^ (h >>> 12);
  269           return h ^ (h >>> 7) ^ (h >>> 4);
  270       }

Kan iemand hier enig licht op werpen? De reactie vertelt ons waarom deze code hier is, maar ik zou graag willen begrijpen hoe dit een slechte hash-waarde verbetert en hoe het garandeert dat de posities een beperkt aantal hebben botsingen . Wat betekenen deze magische nummers ?

18

toegevoegd 27 oktober 2011 op 08:34 de auteur c_maker bewerkt 28 oktober 2011 op 04:56

Bekeken: 1

de bron

1 antwoord

de auteur Affe · Answer 1 · 2011-10-27T08:50Z

Om het zinvol te maken, moet het worden gecombineerd met een goed begrip van hoe HashMap dingen toewijst aan emmers. Dit is de triviale functie waarmee een bucket-index wordt gekozen:

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

U ziet dus dat met een standaardtabel van 16, alleen de 4 minst significante bits van de hash van belang zijn voor het toewijzen van emmers! (16 - 1 = 15, die de hash maskeert bij 1111b)

Dit kan duidelijk slecht nieuws zijn als uw hashCode-functie terugkomt:

10101100110101010101111010111111

01111100010111011001111010111111

11000000010100000001111010111111
//etc etc etc

Zo'n hash-functie zou waarschijnlijk niet "slecht" zijn op een manier die voor de auteur zichtbaar is. Maar als je het combineert met de manier waarop de kaart emmers, boem, MapFail (tm) toekent.

Als u in gedachten houdt dat h een 32-bits getal is, zijn dit helemaal geen magic -nummers. Het systematiseert de meest significante bits van het getal naar rechts in de minst significante bits. Het doel is dat "verschillen" in het getal die overal "erover" voorkomen wanneer ze in binair formaat worden bekeken, zichtbaar worden in de minst significante bits.

Botsingen worden begrensd omdat het aantal verschillende getallen dat dezelfde relevante LSB's heeft, nu aanzienlijk wordt begrensd omdat eventuele verschillen die ergens in de binaire representatie voorkomen, worden gecomprimeerd in de bits die van belang zijn voor het inladen.