Paisktabeli visualiseerija

Hash tables employ deterministic mathematical algorithms to map arbitrary keys to finite index spaces, optimizing for O(1) temporal retrieval. Collisions, an inevitable consequence of the pigeonhole principle, necessitate strict resolution protocols. Chaining relies on linked list allocations, while linear and quadratic probing use mathematical step functions to navigate array indices. The load factor continuously dictates the statistical probability of these computationally expensive collisions.

Räsitabel on lihtsalt massiiv koos reegliga — räsifunktsiooniga —, mis muudab iga võtme pesa numbriks. Selle asemel et iga kirjet ükshaaval läbi vaadata, arvutad, kuhu element kuulub, ja lähed otse sinna; just seetõttu püsib otsing kiire ka miljonite võtmete korral. Konks: kiirus sõltub võtmete ühtlasest jaotusest. Lisa siia mõni ja vaata, kui kiiresti tahavad kaks võtit sama pesa.

Kuna räsitabel muutub aeglaseks lineaarseks otsinguks, kui liiga palju võtmeid satub samasse pessa — täpselt see halvim juht, mille saad üleval esile kutsuda —, võib ründaja, kes teab su räsifunktsiooni, luua tuhandeid võtmeid, mis meelega kokku põrkavad. 2011. aastal halvas see 'hash-flooding' võte veebiservereid keeltes PHP, Java, Python ja Ruby ühe pahatahtliku päringuga. Lahenduseks olid juhusliku seemnega räsifunktsioonid nagu SipHash, mis on tänaseks paljudes keeltes standard.