0xDEADBEEF

[RSS]
««« »»»

Nejrychlejší hashmapa pod sluncem

5. 10. 2017

Článek I Wrote The Fas­test Ha­sh­table po­pi­suje, jak může vy­pa­dat nej­rych­lejší ha­shmapa pod slun­cem, která poráží všechny vysoce op­ti­ma­li­zo­vané kon­ku­renty.

In­terně ne­po­u­žívá běžné open ad­d­res­sing, linear pro­bing ani cucko ha­shing, ale o něco méně známou tech­niku Robin Hood ha­sho­vání. Ta se ne­snaží snížit množ­ství kolizí ale prů­měr­nou délku ko­liz­ního ře­tězce. Odtud po­chází onen Robin Hood v názvu: bo­ha­tým bere (krátký řetěz kolizí) a chudým dává (dlouhý řetěz kolizí).

To efek­tivně vede k log(n) nej­hor­šímu času pří­stupu a mož­nosti na­pl­nit ta­bulku velice blízko 100%

V li­ne­ár­ním pro­bingu je běžné, že dlouhé ko­lizní ře­tězce rostou nej­rych­leji. To dává smysl – za­bí­rají hodně slotů a proto je velká šance, že do nich spad­nou další klíče a délka ře­tězce dál na­roste. Robin Hood při vlo­žení efek­tivně pro­vádí in­ser­tion sort, který řadí podle počtu slotů o kolik je klíč vzdá­lený od své ide­ální pozice.

Krátké ko­lizní ře­tězce mají také výhodu, že kdy žádaný klíč bude blízko, může se na­chá­zet na stejné cache line jako první zkon­t­ro­lo­vaný slot a proto není třeba na­čí­tat další data z RAM.

Re­le­vantní čtení:

píše k47 (@kaja47, k47)