HATトライ

HATトライは、配列ノードを使用して、基数ノードの下の個々のキーと値のペアとハッシュバケットを連想配列に収集する基数トライの一種です。単純なハッシュテーブルとは異なり、HATトライはキーと値を順序付けられたコレクションに格納します。元の発明者は、Nikolas AskitisとRanjan Sinhaです。^{[1] [2]} AskitisとZobelは、HATトライのキー/値コレクションの構築とアクセスが他のソートされたアクセス方法よりも大幅に高速であり、ソートされていないコレクションである配列ハッシュに匹敵することを示しました。^[3]これは、時間と空間内でデータへのアクセスを現代のCPUの 64バイトのキャッシュラインサイズにグループ化しようとするデータ構造のキャッシュフレンドリーな性質によるものです。

新しい HAT トライは、空のノードを表す NULL ポインターとして開始します。最初に追加されたキーは、最小の配列ノードを割り当て、キーと値のペアをそこにコピーします。これがトライの最初のルートになります。後続の各キーと値のペアは、最大サイズに達するまで最初の配列ノードに追加されます。その後、ノードは、そのキーをハッシュ バケットに再配布してバーストされます。新しい基礎配列ノードは、バケット内の占有ハッシュ スロットごとに 1 つずつあります。ハッシュ バケットは、トライの新しいルートになります。キー文字列は、長さエンコード バイトをキー値バイトの前に付けて配列ノードに格納されます。各キーに関連付けられた値は、キー文字列と交互にインラインで格納することも、2 番目の配列 (たとえば、直後のメモリ) に配置して配列ノードに結合することもできます。^[4]

トライが最初のハッシュ バケット ノードに成長すると、ハッシュ バケットはキー値のハッシュ関数に従って、バケット ノードの下にある配列ノードに新しいキーを分配します。特定のハッシュ バケット ノードのキーの最大数に達するまで、キーは追加され続けます。次に、バケットの内容は、格納されたキー値の最初の文字に従って新しい基数ノードに再分配され、ハッシュ バケット ノードがトライのルートとして置き換えられます^[5] (たとえば、バーストソート^[6]を参照)。ハッシュ バケットに含まれる既存のキーと値はそれぞれ 1 文字短縮され、新しい基数ノードの下の新しい配列ノードのセットに配置されます。

コレクションへのソートされたアクセスは、キーをカーソルに列挙することで提供されます。キーは基数トライを分岐して先頭の文字を組み立て、ハッシュ バケットまたは配列ノードのいずれかで終了します。ハッシュ バケットまたは配列ノードに含まれるキーへのポインターは、ソート用のカーソルの一部である配列に組み立てられます。ハッシュ バケットまたは配列ノードにはキーの最大数があるため、すべての時点でカーソルのサイズには事前に設定された固定の制限があります。ハッシュ バケットまたは配列ノードのキーが get-next (または get-previous) によって使い果たされると ( Iterator を参照)、カーソルは次の基数ノード エントリに移動され、プロセスが繰り返されます。^[7]

• C での HAT-Trie 実装の参照
• 高速でメモリ効率の良いHATトライのC++実装