Hopscotch hash - Hopscotch hashing

Hopscotch hash. Tady, H je 4. Šedé položky jsou obsazené. V části (a) položka X je přidána s hodnotou hash 6. Lineární sonda zjistí, že položka 13 je prázdná. Protože 13 je více než 4 záznamy od 6, algoritmus hledá dřívější záznam, který se má vyměnit za 13. První místo, které je třeba hledat, je H−1 = 3 položky dříve, na vstupu 10. To bitová mapa tohoto vstupu naznačuje, že to d, položka na vstupu 11, může být přemístěna na 13. Po přemístění d„Záznam 11 je stále příliš daleko od záznamu 6, takže algoritmus zkoumá záznam 8. Bitová mapa s informacemi o hopu označuje tuto položku C na vstupu 9 lze přesunout na vstup 11. Nakonec A se přesune do záznamu 9. Část (b) zobrazuje stav tabulky těsně před přidáním X.

Hopscotch hash je schéma v programování k vyřešení hashovací kolize hodnot hashovací funkce v stůl použitím otevřené adresování. Je také vhodný pro implementaci a souběžná hash tabulka. Hopscotch hash byl zaveden uživatelem Maurice Herlihy, Nir Shavit a Moran Tzafrir v roce 2008.[1] Název je odvozen od posloupnosti chmele, které charakterizují algoritmus vkládání tabulky.

Algoritmus používá jediné pole n kbelíky. Pro každý kbelík jeho sousedství je malá sbírka H po sobě jdoucí segmenty (tj. segmenty s indexy blízkými původnímu hašovanému segmentu). Požadovanou vlastností sousedství je to, že náklady na nalezení položky v kbelících sousedství se blíží nákladům na nalezení v samotném kbelíku (například tím, že kbelíky v sousedství spadají do stejné řádek mezipaměti ). Velikost sousedství musí být v nejhorším případě dostatečná, aby pojala logaritmický počet položek (tj. Musí pojmout log (n) položky), ale v průměru jen konstantní počet. Pokud je vyplněno okolí nějakého kbelíku, změní se velikost tabulky.

V hopscotch hash, jako v kukačka hash a na rozdíl od v lineární sondování, bude daná položka vždy vložena do a nalezena v sousedství jejího hashovaného kbelíku. Jinými slovy, bude vždy nalezen buď v původní položce hashovaného pole, nebo v jedné z následujících H-1 sousední položky. H může být například 32, běžná velikost strojového slova. Sousedství je tedy „virtuální“ segment, který má pevnou velikost a překrývá následující H-1 kbelíky. Pro urychlení hledání obsahuje každý segment (položka pole) slovo „hop-information“, an H-bitová bitmapa, která označuje, která z následujících H-1 položky obsahují položky, které jsou hašovány do virtuálního bloku aktuální položky. Tímto způsobem lze položku rychle vyhledat tak, že se podíváte na slovo, abyste zjistili, které položky patří do kbelíku, a poté skenujte přes konstantní počet položek (většina moderních procesorů podporuje speciální operace manipulace s bitem, díky nimž je vyhledávání v -informační "bitmapa velmi rychlá).

Zde je způsob přidání položky X který byl hašován do kbelíku i:

  1. Pokud je hop-informační slovo pro kbelík i ukazuje, že již existují H položky v tomto kbelíku, tabulka je plná; rozbalte hashovací tabulku a zkuste to znovu.
  2. Počínaje vstupem i, použijte lineární sondu k vyhledání prázdné položky v indexu j. (Pokud neexistuje žádný prázdný slot, tabulka je plná.)
  3. Zatímco (j−i) mod n ≥ H, posuňte prázdný slot směrem k i jak následuje:
    1. Prohledat H-1 předchozí sloty j pro položku y jehož hash hodnota k je uvnitř H-1 z j, tj. (j−k) mod n < H. (To lze provést pomocí informačních slov hop.)
    2. Pokud taková položka neexistuje y existuje v rozsahu, tabulka je plná.
    3. Hýbat se y na j, čímž se vytvoří nový prázdný slot blíže k i.
    4. Soubor j do prázdné pozice uvolněné uživatelem y a opakovat.
  4. Obchod X ve slotu j a zpět.

Myšlenka je, že hašování pekla „přesune prázdný slot směrem k požadovanému kbelíku“. Tím se odlišuje od lineární sondování který ponechává prázdný slot, kde byl nalezen, pravděpodobně daleko od původního kbelíku nebo od kukačka hash který za účelem vytvoření volného segmentu přesune položku z jednoho z požadovaných segmentů v cílových polích a až poté se pokusí najít přemístěnou položku na nové místo.

Chcete-li odebrat položku z tabulky, jednoduše ji odeberete ze záznamu v tabulce. Pokud jsou sousední segmenty zarovnány do mezipaměti, je možné použít operaci reorganizace, ve které jsou položky přesunuty do nyní prázdného místa, aby se zlepšilo zarovnání.

Jednou z výhod hashcotch hash je, že poskytuje dobrý výkon při velmi vysokých faktorech zatížení tabulky, dokonce i těch, které přesahují 0,9. Část této účinnosti je způsobena používáním lineární sondy pouze k vyhledání prázdného slotu během vkládání, nikoli pro každé vyhledávání jako v originálu lineární sondování algoritmus hash tabulky. Další výhodou je, že lze použít jakoukoli hashovací funkci, zejména jednoduchou, která je blízká univerzální.

Viz také

Reference

  1. ^ Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). „Hopscotch hashing“ (PDF). DISC '08: Sborník z 22. mezinárodního sympozia o distribuovaných výpočtech. Arcachon, Francie: Springer-Verlag. 350–364.

externí odkazy