Nejrychlejší hashmapa pod sluncem
Článek I Wrote The Fastest Hashtable popisuje, jak může vypadat nejrychlejší hashmapa pod sluncem, která poráží všechny vysoce optimalizované konkurenty.
Interně nepoužívá běžné open addressing, linear probing ani cuckoo hashing, ale o něco méně známou techniku Robin Hood hashování. Ta se nesnaží snížit množství kolizí ale průměrnou délku kolizního řetězce. Odtud pochází onen Robin Hood v názvu: bohatým bere (krátký řetěz kolizí) a chudým dává (dlouhý řetěz kolizí).
To efektivně vede k log(n) nejhoršímu času přístupu a možnosti naplnit
tabulku velice blízko 100%
V lineárním probingu je běžné, že dlouhé kolizní řetězce rostou nejrychleji. To dává smysl – zabírají hodně slotů a proto je velká šance, že do nich spadnou další klíče a délka řetězce dál naroste. Robin Hood při vložení efektivně provádí insertion sort, který řadí podle počtu slotů o kolik je klíč vzdálený od své ideální pozice.
Krátké kolizní řetězce mají také výhodu, že kdy žádaný klíč bude blízko, může se nacházet na stejné cache line jako první zkontrolovaný slot a proto není třeba načítat další data z RAM.
Relevantní čtení: