HAT-trie - HAT-trie

The HAT-Trie je typ radix trie který používá uzly pole ke shromažďování jednotlivců páry klíč – hodnota pod uzly radix a hash kbelíky do asociativní pole. Na rozdíl od jednoduchého hash tabulka „Pokusy HAT ukládají klíč – hodnota do objednané kolekce. Původními vynálezci jsou Nikolas Askitis a Ranjan Sinha.[1][2] Dr. Askitis ukazuje, že budování a přístup ke kolekci klíčů / hodnot HAT-trie je podstatně rychlejší než jiné metody tříděného přístupu a je srovnatelné s Array Hash, který je netříděnou kolekcí.[3] To je způsobeno povahou datové struktury, která je přátelská k mezipaměti, která se pokouší seskupit přístup k datům v čase a prostoru do 64 bajtů velikost řádku mezipaměti moderního CPU.

Popis

Nový HAT-Trie začíná jako ukazatel NULL představující prázdný uzel. První přidaný klíč přiděluje nejmenší uzel pole a zkopíruje do něj pár klíč / hodnota, který se stane prvním kořenem trie. Každý následující pár klíč / hodnota se přidá do počátečního uzlu pole, dokud se nedosáhne maximální velikosti, po které se uzel roztrhne re-distribucí jeho klíčů do hash kbelíku s novými základními uzly pole, jeden pro každý obsazený hash slot v kbelíku . Hash kbelík se stává novým kořenem trie. Klíčové řetězce jsou uloženy v uzlech pole s bajtem kódujícím délku s předponou bajtů hodnoty klíče. Hodnotu přidruženou ke každému klíči lze uložit buď in-line střídavě s řetězci kláves, nebo umístit do druhého pole, např. Paměti bezprostředně za a připojit se k uzlu pole.[4]

Jakmile se trie rozrostla do prvního uzlu hash kbelíku, hash kbelík distribuuje nové klíče podle a hashovací funkce hodnoty klíče do uzlů pole obsažených pod uzlem segmentu. Klíče se přidávají, dokud není dosaženo maximálního počtu klíčů pro konkrétní uzel hash kbelíku. Obsah kbelíku je poté znovu distribuován do nového uzlu radix podle prvního znaku hodnoty uloženého klíče, který nahradí uzel kbelíku hash jako kořen tri[5] (např. viz Burstsort[6]). Existující klíče a hodnoty obsažené v hash kbelíku jsou zkráceny o jeden znak a umístěny pod nový uzel radix v sadě nových uzlů pole.

Tříděný přístup ke kolekci poskytuje výčet klíčů do kurzoru rozvětvením radix trie k sestavení úvodních znaků, končících buď hash kbelíkem nebo uzlem pole. Ukazatele na klíče obsažené v hash kbelíku nebo uzlu pole jsou sestaveny do pole, které je součástí kurzoru pro třídění. Vzhledem k tomu, že v hash kbelíku nebo uzlu pole je maximální počet klíčů, existuje předem nastavený pevný limit velikosti kurzoru ve všech časových bodech. Poté, co jsou klíče pro hash kbelík nebo uzel pole vyčerpány funkcí get-next (nebo get-previous) (viz Iterátor ) kurzor se přesune do dalšího záznamu uzlu radix a proces se opakuje.[7]

Reference

  1. ^ popsáno v článku publikovaném v Proc. Třicátá australasská konference o informatice (ACSC2007), Ballarat, Austrálie. CRPIT, 62. Dobbie, G., Ed. ACS. 97-105
  2. ^ https://dl.acm.org/citation.cfm?id=1273761 HAT-trie: Datová struktura založená na Trie založená na mezipaměti pro řetězce
  3. ^ Askitis, N. & Zobel, J. (2005), Cache-aware collision resolution for string hash tables, in ‘Proc. SPIRE String Processing and Information Retrieval Symp. “, Springer-Verlag, str. 92–104
  4. ^ Askitis, N. a Zobel, J. 2011. Redesigning the string hash table, burst trie, and BST to exploit cache. ACM J. Exp. Algor. 15, 1, článek 1.7 (leden 2011)
  5. ^ Burst pokusy: rychlá a efektivní datová struktura řetězcových klíčů ACM Trans. Inf. Syst., Sv. 20, č. 2. (duben 2002), str. 192-223, doi: 10,1145 / 506309,506312 Steffen Heinz, Justin Zobel, Hugh E. Williams
  6. ^ Sinha, R. a Wirth, A. 2010. Inženýrský výbuch: Směrem k rychlému třídění řetězců na místě. ACM J. Exp. Algor. 15, článek 2.5 (březen 2010)
  7. ^ http://www.siam.org/meetings/alenex03/Abstracts/rsinha.pdf Cache-vědomé třídění velkých sad řetězců s dynamickými pokusy

Externí odkaz