Volgens de Java-documentatie, de hash-codevoor een String-object wordt berekend als:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]met behulp van
intrekenkunde, waarbijs[i]de
ide teken van de tekenreeks,nis de lengte van
de string, en^geeft machtsverheffing aan.
Waarom wordt 31 als vermenigvuldiger gebruikt?
Ik begrijp dat de vermenigvuldiger een relatief groot priemgetal moet zijn. Dus waarom niet 29, of 37, of zelfs 97?
Antwoord 1, autoriteit 100%
Volgens Joshua Bloch’s Effective Java(een boek dat niet kan worden genoeg aanbevolen, en die ik kocht dankzij de voortdurende vermeldingen op stackoverflow):
De waarde 31 is gekozen omdat het een oneven priemgetal is. Als het even was en de vermenigvuldiging overstroomde, zou informatie verloren gaan, omdat vermenigvuldigen met 2 gelijk staat aan verschuiven. Het voordeel van het gebruik van een prime is minder duidelijk, maar het is traditioneel. Een mooie eigenschap van 31 is dat de vermenigvuldiging kan worden vervangen door een shift en een aftrekking voor betere prestaties:
31 * i == (i << 5) - i. Moderne VM’s doen dit soort optimalisatie automatisch.
(uit Hoofdstuk 3, Item 9: Hashcode altijd overschrijven als je gelijk aan overschrijft, pagina 48)
Antwoord 2, autoriteit 19%
Goodrich en Tamassia hebben op basis van meer dan 50.000 Engelse woorden (gevormd als de vereniging van de woordenlijsten in twee varianten van Unix) berekend dat het gebruik van de constanten 31, 33, 37, 39 en 41 minder dan 7 botsingen zal opleveren in elk geval. Dit kan de reden zijn dat zoveel Java-implementaties voor dergelijke constanten kiezen.
Zie paragraaf 9.2 Hash-tabellen (pagina 522) van Gegevensstructuren en algoritmen in Java.
Antwoord 3, autoriteit 13%
Op (meestal) oude processors kan vermenigvuldigen met 31 relatief goedkoop zijn. Op een ARM is het bijvoorbeeld maar één instructie:
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
De meeste andere processors hebben een aparte shift- en aftrekinstructie nodig. Als je multiplier echter langzaam is, is dit nog steeds een overwinning. Moderne processors hebben meestal snelle vermenigvuldigers, dus het maakt niet veel uit, zolang 32 maar aan de goede kant gaat.
Het is geen geweldig hash-algoritme, maar het is goed genoeg en beter dan de 1.0-code (en veel beter dan de 1.0-specificatie!).
Antwoord 4, autoriteit 9%
Door te vermenigvuldigen worden bits naar links verschoven. Dit gebruikt meer van de beschikbare ruimte voor hash-codes, waardoor botsingen worden verminderd.
Door geen macht van twee te gebruiken, worden de meest rechtse bits van de lagere orde ook ingevuld, om te worden gemengd met het volgende stuk gegevens dat in de hash gaat.
De uitdrukking n * 31is gelijk aan (n << 5) - n.
Antwoord 5, autoriteit 7%
Je kunt de oorspronkelijke redenering van Bloch lezen onder “Opmerkingen” in http://bugs .java.com/bugdatabase/view_bug.do?bug_id=4045622. Hij onderzocht de prestaties van verschillende hashfuncties met betrekking tot de resulterende “gemiddelde ketengrootte” in een hashtabel. P(31)was in die tijd een van de gebruikelijke functies die hij in het boek van K&R vond (maar zelfs Kernighan en Ritchie konden zich niet herinneren waar het vandaan kwam). Uiteindelijk moest hij er eigenlijk een kiezen en daarom nam hij P(31)omdat het goed genoeg leek te presteren. Hoewel P(33)niet echt slechter was en vermenigvuldiging met 33 even snel te berekenen is (alleen een shift met 5 en een optelling), koos hij voor 31 aangezien 33 geen priemgetal is:
Van de overige
vier, zou ik waarschijnlijk Selecteer P (31), want het is de goedkoopste te berekenen op een RISC
machine (omdat 31 is het verschil van twee machten van twee). P (33)
op dezelfde goedkoop te berekenen, maar de prestaties is iets slechter, en
33 is samengesteld, die me zenuwachtig maakt.
Dus de redenering niet zo rationeel was als veel van de antwoorden hier lijken te impliceren. Maar we zijn allemaal goed in het bedenken van rationele redenen na gut beslissingen (en zelfs Bloch misschien gevoelig voor dat zijn).
6, Autoriteit 5%
Eigenlijk, 37 zou vrij goed te werken! z: = 37 * x kan worden berekend als y := x + 8 * x; z := x + 4 * y. Beide stappen overeenkomen met een LEA x86-instructies, dus dit is extreem snel.
In feite vermenigvuldigen met de even grote prime 73 kan worden gedaan met dezelfde snelheid door het instellen y := x + 8 * x; z := x + 8 * y
gebruiken 73 of 37 (in plaats van 31) misschien beter, omdat het leidt tot dichtere code : De twee LEA aanwijzingen slechts 6 bytes versus 7 bytes te verplaatsen + shift + aftrekken van de vermenigvuldiging met 31. een mogelijk nadeel is dat de 3-argument LEA instructies die hier gebruikt werd trager op Intel’s Sandy bridge architectuur, met een verhoogde latentie van 3 cycli.
Bovendien 73 is favoriet nummer Sheldon Cooper’s.
7, Autoriteit 4%
Neil Coffey verklaart waarom 31 wordt gebruikt onder Het gladstrijken van de vooringenomenheid .
In principe is het gebruik van 31 geeft je een meer gelijkmatige set-bit kansverdeling voor de hash-functie.
Antwoord 8
Bloch gaat hier niet helemaal op in, maar de grondgedachte die ik altijd heb gehoord/geloofd is dat dit elementaire algebra is. Hashes komen neer op vermenigvuldiging en modulusbewerkingen, wat betekent dat je nooit getallen met gemeenschappelijke factoren wilt gebruiken als je dat kunt helpen. Met andere woorden, relatief priemgetallen zorgen voor een gelijkmatige verdeling van de antwoorden.
De getallen waaruit een hash bestaat, zijn meestal:
- modulus van het datatype waarin je het plaatst
(2^32 of 2^64) - modulus van het aantal buckets in uw hashtabel (varieert. Vroeger was Java prime, nu 2^n)
- vermenigvuldigen of verschuiven met een magisch getal in je mixfunctie
- De invoerwaarde
Je hebt eigenlijk maar een paar van deze waarden in de hand, dus je moet wat extra voorzichtig zijn.
Antwoord 9
In de nieuwste versie van JDK wordt 31 nog steeds gebruikt. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode()
Het doel van hash-tekenreeks is
- uniek (laat de operator
^zien in het hashcode-berekeningsdocument, het helpt uniek) - goedkope kosten voor het berekenen
31 is de maximale waarde die in 8 bit (= 1 byte) register kan worden ingevoerd, is het grootste priemgetal dat in het register van 1 byte kan worden ingevoerd, is oneven getal.
Vermenigvuldigen met 31 is <<5, trek het dan zelf af en heb daarom goedkope middelen nodig.
Antwoord 10
Java String hashCode() en 31
Dit komt omdat 31 een mooie eigenschap heeft – de vermenigvuldiging kan worden vervangen door een bitsgewijze verschuiving die sneller is dan de standaard vermenigvuldiging:
31 * i == (i << 5) - i
Antwoord 11
Ik weet het niet zeker, maar ik vermoed dat ze een aantal priemgetallen hebben getest en hebben ontdekt dat 31 de beste verdeling gaf over een aantal mogelijke strings.