Kodėl „Java hashCode“ () eilutėje naudoja 31 kaip daugiklį?

Pagal „Java“ dokumentaciją String objekto maišos kodas apskaičiuojamas taip:

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

naudojant int aritmetiką, kur s[i] yra eilutės i -asis simbolis, n yra eilutės ilgis, o ^ eksponentacija.

Kodėl 31 naudojamas kaip daugiklis?

Suprantu, kad daugiklis turėtų būti santykinai didelis pirminis skaičius. Tad kodėl gi ne 29 ar 37 ar net 97?

424
18 нояб. nustatė jacobko 18 nov. 2008-11-18 19:39 '08, 07:39 pm 2008-11-18 19:39
@ 10 atsakymų

Pasak Joshua Bloch Efektyviosios Java (knyga, kurios nepakanka, ir kurią aš nusipirkau dėl nuolatinių nuorodų į stackoverflow):

Vertė 31 buvo pasirinkta, nes tai yra nelyginis pirminis skaičius. Jei ji būtų lygi ir padauginta, informacija būtų prarasta, nes padauginus iš 2, tai yra lygi perkėlimui. „Prime“ naudojimo pranašumas yra mažiau akivaizdus, ​​tačiau jis yra tradicinis. Gera 31 ypatybė yra tai, kad dauginimas gali būti pakeistas pamainomis ir atimties rezultatais: 31 * я == (i << 5) - i . Šiuolaikinės virtualios mašinos automatiškai atlieka šį optimizavimą.

(iš 3 skyriaus 9 punkto: visada pakeiskite maišos kodą, kai yra viršesnis lygus, p. 48)

360
18 нояб. Atsakymą pateikia matt b . 2008-11-18 21:53 '08 at 9:53 pm 2008-11-18 21:53

Kaip teigia Goodrich ir Tamassia , jei vartojate daugiau kaip 50 000 angliškų žodžių (sudarytų kaip dviejų „Unix“ variantų žodinių sąrašų sąjunga), naudodami 31, 33, 37, 39 ir 41 konstantas, kiekvienu atveju susidaro mažiau nei 7 susidūrimai. Žinodami tai, nenuostabu, kad daugelis „Java“ diegimų pasirenka vieną iš šių konstantų.

Beje, buvau viduryje skaitydamas „polinomo maišos kodo“ skyrių, kai pamačiau šį klausimą.

EDIT: čia yra nuoroda į „pdf“ knygos „10mb“ knygą, apie kurią kalbu aukščiau. Žr. 10.2 skyrių „Hash Tables“ (413 puslapis) „Java“ duomenų struktūros ir algoritmai

75
18 нояб. JohnZaj atsakymas . 2008-11-18 23:56 '08 2008-11-18 23:56 23:56

Dažniausiai (daugiausia) seni perdirbėjai, padauginti iš 31, gali būti palyginti pigūs. Pavyzdžiui, ARM, tai tik vienas nurodymas:

 RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5) 

Daugumai kitų procesorių reikės atskiro perjungimo ir atimties komandos. Tačiau, jei jūsų daugiklis yra lėtas, tai vis dar yra pergalė. Šiuolaikiniai procesoriai paprastai turi spartų daugiklį, todėl nesvarbu, ar 32 yra dešinėje pusėje.

Tai nėra puikus maišymo algoritmas, bet jis yra pakankamai geras ir geresnis už 1.0 kodą (ir daug geriau nei 1,0 spec!).

56
18 нояб. Atsakyti Tom Hawtin - tackline lapkritis 18 2008-11-18 20:01 '08 at 8:01 pm 2008-11-18 20:01

Padauginus bitai yra perkelti į kairę. Jis naudoja daugiau turimų maišos kodo erdvių, mažindamas susidūrimus.

Nenaudojant dviejų jėgų, taip pat užpildomi mažiausiai reikšmingi ir dešinieji didžiausi bitai, kurie turi būti sumaišyti su sekančia į maišą įvedama duomenų dalimi.

Sąvoka n * 31 lygiavertė (n << 5) - n .

28
19 мая '09 в 21:10 2009-05-19 21:10 atsakymą pateikė erickson gegužės 19 d. , 09:21, 2009-05-19 21:10

Originalų „Bloch“ motyvaciją galite perskaityti skyriuje „Komentarai“, esančioje http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Jis ištyrė skirtingų maišos funkcijų atlikimą pagal gautą „vidutinį grandinės dydį“ maišos lentelėje. P(31) buvo viena iš bendrų laiko funkcijų, kurią jis rado knygoje K R (bet net Kernighanas ir Richie negalėjo prisiminti, iš kur jis buvo kilęs). Galų gale jis turėjo pasirinkti vieną, ir jis paėmė P(31) nes jis atrodė pakankamai geras. Nors P(33) iš tikrųjų nebuvo blogesnis, o skaičiavimui padauginus iš 33 vienodai greitai (tik pakeitimas po 5 ir papildymas), jis pasirinko 31, nes 33 nėra pirminis skaičius:

Iš likusių keturių, aš tikriausiai pasirinkčiau P (31), nes tai yra pigiausia apskaičiuoti RISC mašinoje (kadangi 31 yra dviejų dviejų galių skirtumas). P (33) taip pat yra pigus apskaičiuoti, tačiau jo našumas yra šiek tiek blogesnis, o 33 yra sudėtingas, kuris yra šiek tiek nervingas.

Taigi argumentai nebuvo tokie racionalūs, kaip atrodo daugelis čia pateiktų atsakymų. Bet mes, visi intuityvūs sprendimai, mes sugalvojame gerų racionalių priežasčių (ir netgi Blokas gali būti linkęs į tai).

24
10 февр. David Ongaro atsakymas vasario 10 d 2016-02-10 03:46 '16 at 3:46 2016-02-10 03:46

Iš tiesų, 37 veiks labai gerai! z: = 37 * x galima apskaičiuoti kaip y := x + 8 * x; z := x + 4 * y y := x + 8 * x; z := x + 4 * y y := x + 8 * x; z := x + 4 * y y := x + 8 * x; z := x + 4 * y . Abu veiksmai atitinka vieną LEA x86 nurodymą, todėl tai labai greitai.

Iš tiesų, dauginimas su dar didesniu skaičiumi 73 gali būti atliekamas tuo pačiu greičiu, nustatant y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y .

Naudojant 73 arba 37 (vietoj 31) gali būti geriau, nes jis sukuria tankesnį kodą: dvi LEA instrukcijos užima tik 6 baitus, o 7 baitai - perkelti + pertrauka + atimtis dauginimui iš 31. trijų argumentų LEA instrukcijos, naudojamos čia, tapo lėtesnės Intel Sandy Bridge architektūroje su padidėjusiu 3 ciklų vėlavimu.

Be to, 73 yra Sheldon Cooper mėgstamiausias numeris.

22
27 июля '11 в 22:37 2011-07-27 22:37 atsakymas duotas hrr liepos 27 d. 11 val. 22:37 2011-07-27 22:37

„Neil Coffey“ paaiškina, kodėl 31 lyginimas naudojamas lyginant.

Iš esmės, naudojant 31 suteikia jums lygesnę tikimybės pasiskirstymą maišos funkcijai.

18
07 дек. Atsakymą pateikė TheJuice 07 Dec 2011-12-07 18:27 '11 at 18:27 2011-12-07 18:27

JDK-4045622 , kur Jozuė Blochas apibūdina priežastis, dėl kurių buvo pasirinktas šis (naujas) String.hashCode() įgyvendinimas

Toliau pateiktoje lentelėje parodyta įvairių trijų duomenų rinkinių, aprašytų pirmiau, rezultatai:

1) Visi žodžiai ir frazės su įrašais „Merriam-Webster“ 2-ajame tarptautiniame žodyne be žodyno (311, 141 eilutės, vidutinis ilgis 10 simbolių).

2) Visos linijos / bin /, / usr / bin /, / usr / lib /, / usr / ucb / ir / usr / openwin / bin / * (66,304 eilutės, vidutinis ilgis 21 simbolis).

3) Tinklalapių, kuriuos surinko kelias valandas praėjusią naktį, renkamų URL sąrašas (28 372 eilutės, vidutinis ilgis 49 simboliai).

Lentelėje rodomas našumo rodiklis yra „vidutinis grandinės dydis“ visiems maišos lentelės elementams (ty numatoma vertė yra raktų skaičius, palyginti su paieškos elementu).

  Webster Code Strings URLs --------- ------------ ---- Current Java Fn. 1.2509 1.2738 13.2560 P(37) [Java] 1.2508 1.2481 1.2454 P(65599) [Aho et al] 1.2490 1.2510 1.2450 P(31) [K+R] 1.2500 1.2488 1.2425 P(33) [Torek] 1.2500 1.2500 1.2453 Vo Fn 1.2487 1.2471 1.2462 WAIS Fn 1.2497 1.2519 1.2452 Weinberger Fn(MatPak) 6.5169 7.2142 30.6864 Weinberger Fn(24) 1.3222 1.2791 1.9732 Weinberger Fn(28) 1.2530 1.2506 1.2439 

Šioje lentelėje yra aišku, kad visos funkcijos, išskyrus dabartinę „Java“ funkciją ir dvi sulaužytas „Weinberger“ funkcijas, pasižymi puikiu, beveik neatskiriamu našumu. Turiu hipotezę, kad tai yra „teorinis idealas“, kurį galėtumėte gauti, jei vietoj maišos funkcijos naudojote tikrą atsitiktinių skaičių generatorių.

Norėčiau išskirti WAIS funkciją, nes jos specifikacijoje yra atsitiktinių skaičių puslapiai, o jo našumas nėra geresnis nei bet kuri iš paprastesnių funkcijų. Kiekviena iš likusių šešių funkcijų atrodo kaip puikus pasirinkimas, tačiau turime pasirinkti vieną. Manau, kad dėl jų papildymo, nors ir nedidelis, norėčiau atmesti „Vo Option“ ir „Weinberger“ funkciją. Iš likusių keturių, aš norėčiau pasirinkti P (31), nes tai yra pigiausias apskaičiuoti RISC mašinoje (nuo 31 metų yra dviejų laipsnių skirtumas). P (33) taip pat yra pigus apskaičiuoti, tačiau jo našumas yra šiek tiek blogesnis, o 33 - sudėtingas, todėl mane šiek tiek nervina.

Josh

6
13 июня '17 в 0:17 2017-06-13 00:17 atsakymas pateikiamas „ Flow“ birželio 13 d., 17 val. 0:17 2017-06-13 00:17

Blochas ne visai įsijungia į tai, bet loginis pagrindas, kurį visada girdėjau / manau, yra tai, kad tai yra pagrindinė algebra. Hashes sumažėja iki dauginimo ir moduliavimo, o tai reiškia, kad jūs niekada nenorėsite naudoti numerių su bendrais veiksniais. Kitaip tariant, gana paprasti skaičiai suteikia tolygų atsakymų pasiskirstymą.

Skaičiai, sudaryti iš maišos, paprastai yra:

  • modulio duomenų tipą, kurį įdėjote (2 ^ 32 arba 2 ^ 64)
  • kaušų skaičiavimo modulis jūsų maišymo lentelėje (pakeitimai. „Java“ sistemoje naudojamas neveikos režimas, dabar 2 ^ n)
  • padauginkite arba keiskite magišką skaičių savo mišinio funkcijoje
  • Įvesties vertė

Jūs tikrai galite kontroliuoti tik keletą šių vertybių, taigi šiek tiek daugiau dėmesio skiriama.

5
29 апр. Atsakyti į Jason balandžio 29 d 2010-04-29 01:39 '10 ne 1:39 2010-04-29 01:39

Aš nesu įsitikinęs, bet manau, kad jie patikrino tam tikrą pirminių skaičių pavyzdį ir nustatė, kad 31 davė geriausią pasiskirstymą dėl kai kurių galimų styginių pavyzdžių.

5
18 нояб. Atsakymą pateikė Dave L. 18 lapkričio. 2008-11-18 19:58 '08, 19:58, 2008-11-18 19:58

Peržiūrėkite kitus klausimus apie „ žymes arba Užduoti klausimą