Trys dalys pseudokodu

Trys dalys: maišos funkcija, kolizijų tvarkymas, plėtimasis.

Maišos funkcija

FNV-1a — viena iš paprasčiausių gerų. Vienas xor ir viena daugyba baitui:

hashKey(s):
    h ← 14695981039346656037        // offset basis
    kiekvienam baitui b iš s:
        h ← h XOR b
        h ← h * 1099511628211       // prime
    grąžink h

Kibiro numeris — hashKey(title) % len(buckets).

Ji dirba su BAITAIS, ir maišos lentelei tai teisinga. Dvi vienodos eilutės turi vienodus baitus, kad ir kokia abėcėle parašytos; skirtingos — beveik neabejotinai skirtingus. Funkcijai nereikia žinoti, kas yra raidė.

Septintame žingsnyje pamatysi struktūrą, kuriai baitų nepakanka — ir kodėl.

Kolizijos: grandinėlės

Du skirtingi raktai gali duoti tą patį kibirą. Sprendimas paprasčiausias: kiekvienas kibiras laiko grandinėlę, o paieška ją pereina.

Get(title):
    i ← hashKey(title) % len(buckets)
    kiekvienam e nuo buckets[i] per grandinėlę:
        c.Hit()
        jei e.key == title: grąžink e.item, true
    grąžink tuščią, false

Palyginimų skaičius = grandinėlės ilgis. Būtent todėl skaitiklis šioje pamokoje toks svarbus: jis matuoja tiksliai tą dydį, nuo kurio priklauso, ar O(1) tikras.

Vienodas raktas nėra kolizija

Šitą lengva supainioti, tad iš karto:

• kolizija — skirtingi raktai patenka į tą patį kibirą. Neišvengiama, tvarkoma grandinėle;
• vienodas raktas — tas pats pavadinimas įrašomas antrą kartą. Tai ne kolizija; Put privalo pakeisti esamą įrašą.

Pirmoje pamokoje parašei gen -dup-rate. Ji gamina vienodus raktus, ne kolizijas — ir šeštame žingsnyje pamatysi, ką ji iš tikrųjų padaro indeksui.

Plėtimasis

Kai įrašų daugėja, o kibirų ne, grandinėlės ilgėja ir O(1) tampa melu.

Apkrovos koeficientas (load factor) = įrašai ÷ kibirai. Pasiekus 1.0, kibirų skaičius padvigubinamas ir viskas perskaičiuojama iš naujo:

grow():
    senas ← buckets
    buckets ← naujas masyvas, 2x didesnis
    kiekvienam įrašui sename: įdėk jį iš naujo pagal hashKey % naują dydį

Tai O(n) operacija. Bet ji vyksta retai — lygiai kaip antros pamokos append, ir dėl tos pačios priežasties. Amortizacija čia ta pati sąvoka.