HATトライは、配列ノードを使用して基数ノードの下の個々のキーと値のペアを収集し、ハッシュ バケットを連想配列に収集する基数トライの一種です。単純なハッシュ テーブルとは異なり、HAT トライはキーと値を順序付けられたコレクションに格納します。元の発明者は、Nikolas Askitis と Ranjan Sinha です。[1] [2] Askitis と Zobel は、HAT トライのキーと値のコレクションの構築とアクセスが他のソートされたアクセス方法よりも大幅に高速であり、ソートされていないコレクションである配列ハッシュに匹敵することを示しました。[3]これは、時間と空間内でデータへのアクセスを現代の CPU の 64 バイトのキャッシュ ライン サイズにグループ化しようとするデータ構造のキャッシュ フレンドリーな性質によるものです。
説明
新しいHATトライは、空ノードを表すNULLポインタから始まります。最初に追加されたキーは最小の配列ノードを割り当て、そこにキー/値のペアをコピーします。これがトライの最初のルートになります。その後、各キー/値のペアは、最大サイズに達するまで最初の配列ノードに追加されます。その後、ノードはバーストされます。バーストとは、キーをハッシュバケットに再分配し、バケット内の占有ハッシュスロットごとに新しい配列ノードを追加することです。ハッシュバケットはトライの新しいルートになります。キー文字列は、キー値バイトの先頭に長さエンコードバイトを付加して配列ノードに格納されます。各キーに関連付けられた値は、キー文字列と交互にインラインに格納するか、または2番目の配列（例えば、直後のメモリ）に配置して配列ノードに結合することができます。[4]
トライが最初のハッシュバケットノードまで成長すると、ハッシュバケットはキー値のハッシュ関数に従って、バケットノードの下にある配列ノードに新しいキーを分配します。キーは、特定のハッシュバケットノードのキーの最大数に達するまで追加され続けます。その後、バケットの内容は、格納されているキー値の最初の文字に従って新しい基数ノードに再分配され、ハッシュバケットノードがトライのルートとして置き換えられます[5]（例えば、バーストソート[6]を参照）。ハッシュバケットに含まれる既存のキーと値はそれぞれ1文字ずつ短縮され、新しい基数ノードの下にある新しい配列ノードのセットに配置されます。
コレクションへのソートされたアクセスは、キーをカーソルに列挙することで実現されます。キーは基数トライを分岐して先頭の文字を組み立て、ハッシュバケットまたは配列ノードで終了します。ハッシュバケットまたは配列ノードに含まれるキーへのポインタは、ソート用のカーソルの一部である配列に組み立てられます。ハッシュバケットまたは配列ノードにはキーの最大数があるため、カーソルのサイズには、すべての時点で事前に設定された固定の制限があります。ハッシュバケットまたは配列ノードのキーがget-next（またはget-previous）（反復子を参照）によって使い果たされると、カーソルは次の基数ノードエントリに移動し、このプロセスが繰り返されます。[7]
参考文献
- ^ Proc. Thirtieth Australasian Computer Science Conference (ACSC2007)、Ballarat Australia. CRPIT、62に掲載された論文で説明されている。Dobbie, G., Ed. ACS. 97-105
- ^ https://dl.acm.org/citation.cfm?id=1273761 HAT-trie: キャッシュを考慮した文字列用トライベースデータ構造
- ^ Askitis, N. & Zobel, J. (2005), 文字列ハッシュテーブルのキャッシュを考慮した衝突解決, 『Proc. SPIRE String Processing and Information Retrieval Symp.』, Springer-Verlag, pp. 92–104
- ^ Askitis, N. and Zobel, J. 2011. キャッシュを活用するための文字列ハッシュテーブル、バーストトライ、BSTの再設計. ACM J. Exp. Algor. 15, 1, Article 1.7 (2011年1月)
- ^ バーストトライ：文字列キーのための高速で効率的なデータ構造 ACM Trans. Inf. Syst., Vol. 20, No. 2. (2002年4月), pp. 192-223, doi:10.1145/506309.506312 by Steffen Heinz, Justin Zobel, Hugh E. Williams
- ^ Sinha, R. and Wirth, A. 2010. エンジニアリングバーストソート：高速インプレース文字列ソートに向けて. ACM J. Exp. Algor. 15, Article 2.5 (2010年3月)
- ^ http://www.siam.org/meetings/alenex03/Abstracts/rsinha.pdf 動的トライによる大規模な文字列セットのキャッシュを考慮したソート
外部リンク
- C言語でのHAT-Trie実装のリファレンス
- 高速でメモリ効率の高いHATトライのC++実装
