HAT-spróbuj

HAT -trie to rodzaj radix trie , który wykorzystuje węzły tablicy do zbierania poszczególnych par klucz-wartość w węzłach radix i zasobnikach mieszania w tablicę asocjacyjną . W przeciwieństwie do prostej tablicy skrótów , HAT-próbuje przechowywać klucz-wartość w uporządkowanej kolekcji. Oryginalnymi wynalazcami są Nikolas Askitis i Ranjan Sinha. Askitis i Zobel wykazali, że budowanie i uzyskiwanie dostępu do kolekcji kluczy/wartości HAT-trie jest znacznie szybsze niż w przypadku innych posortowanych metod dostępu i jest porównywalne z mieszaniem tablicowym, które jest nieposortowaną kolekcją. Wynika to z przyjaznej pamięci podręcznej natury struktury danych, która próbuje pogrupować dostęp do danych w czasie i przestrzeni do 64-bajtowej linii pamięci podręcznej nowoczesnego procesora.

Opis

Nowa próba HAT rozpoczyna się jako wskaźnik NULL reprezentujący pusty węzeł. Pierwszy dodany klucz przydziela najmniejszy węzeł tablicy i kopiuje do niego parę klucz/wartość, która staje się pierwszym pierwiastkiem trie. Każda kolejna para klucz/wartość jest dodawana do początkowego węzła tablicy, aż do osiągnięcia maksymalnego rozmiaru, po czym węzeł jest rozdzielany przez ponowne rozdzielenie jego kluczy do zasobnika mieszania z nowymi bazowymi węzłami tablicy, po jednym dla każdego zajętego gniazda mieszania w zasobniku . Wiadro mieszające staje się nowym korzeniem trie. Ciągi kluczy są przechowywane w węzłach tablicy z bajtem kodowania długości poprzedzonym bajtami wartości klucza. Wartość powiązana z każdym kluczem może być przechowywana albo naprzemiennie z ciągami kluczy, albo umieszczona w drugiej tablicy, np. w pamięci bezpośrednio po węźle tablicy i do niego przyłączona.

Gdy trie rozrośnie się do pierwszego węzła wiadra z haszem, wiadro z haszem dystrybuuje nowe klucze zgodnie z funkcją mieszającą wartości klucza do węzłów tablicy znajdujących się pod węzłem wiadra. Klucze są dodawane do momentu osiągnięcia maksymalnej liczby kluczy dla określonego węzła zasobnika mieszającego. Zawartość zasobnika jest następnie redystrybuowana do nowego węzła radix zgodnie z pierwszym znakiem zapisanej wartości klucza, który zastępuje węzeł zasobnika mieszającego jako pierwiastek trie (np. patrz Burstsort ). Istniejące klucze i wartości zawarte w segmencie mieszania są skracane o jeden znak i umieszczane pod nowym węzłem podstawy w zestawie nowych węzłów tablicy.

Posortowany dostęp do kolekcji jest zapewniany przez wyliczanie kluczy w kursorze przez rozgałęzianie podstawy w celu złożenia wiodących znaków, kończąc na zasobniku mieszania lub węźle tablicy. Wskaźniki do kluczy zawartych w zasobniku mieszania lub węźle tablicy są składane w tablicę, która jest częścią kursora do sortowania. Ponieważ w zasobniku mieszającym lub w węźle tablicy znajduje się maksymalna liczba kluczy, we wszystkich punktach w czasie istnieje ustalony z góry ustalony limit rozmiaru kursora. Po wyczerpaniu kluczy dla węzła mieszającego lub węzła tablicy przez get-next (lub get-previous) (patrz Iterator ) kursor jest przesuwany do następnego wpisu węzła radix i proces się powtarza.

Linki zewnętrzne