HAT-trie
HAT-Trieは、基数ノードを使用して基数ノードとハッシュバケットの下の個々のキーと値のペアを連想配列に収集する基数トライの一種です。単純なハッシュテーブルとは異なり、HAT-trysはキー値を順序付けられたコレクションに格納します。元の発明者はNikolasAskitisとRanjanSinhaです。 Askitis博士は、HAT-trieキー/値コレクションの構築とアクセスは、他のソートされたアクセス方法よりもかなり高速であり、ソートされていないコレクションである配列ハッシュに匹敵することを示しています。これは、データへのアクセスを時間と空間で64バイトにグループ化しようとするデータ構造のキャッシュフレンドリーな性質によるものです。最新のCPUのキャッシュラインサイズ。
説明
新しいHAT-Trieは、空のノードを表すNULLポインターとして始まります。最初に追加されたキーは、最小の配列ノードを割り当て、その中にキーと値のペアをコピーします。これが、トライの最初のルートになります。後続の各キー/値ペアは、最大サイズに達するまで最初の配列ノードに追加されます。その後、ノードは、バケット内の占有されているハッシュスロットごとに1つずつ、新しい基になる配列ノードを持つハッシュバケットにキーを再配布することによってバーストされます。 。ハッシュバケットがトライの新しいルートになります。キー文字列は、キー値バイトの前に長さエンコーディングバイトが付加された配列ノードに格納されます。各キーに関連付けられた値は、キー文字列と交互にインラインで格納するか、2番目の配列（たとえば、直後のメモリなど）に配置して配列ノードに結合することができます。
トライが最初のハッシュバケットノードに成長すると、ハッシュバケットは、キー値のハッシュ関数に従って新しいキーをバケットノードの下に含まれる配列ノードに配布します。キーは、特定のハッシュバケットノードのキーの最大数に達するまで追加され続けます。次に、バケットの内容は、格納されたキー値の最初の文字に従って新しい基数ノードに再配布されます。これにより、ハッシュバケットノードがトライルートとして置き換えられます（たとえば、Burstsort を参照）。ハッシュバケットに含まれる既存のキーと値は、それぞれ1文字短縮され、一連の新しい配列ノードの新しい基数ノードの下に配置されます。
コレクションへのソートされたアクセスは、基数トライを分岐して先頭の文字をアセンブルし、ハッシュバケットまたは配列ノードのいずれかで終了することにより、キーをカーソルに列挙することによって提供されます。ハッシュバケットまたは配列ノードに含まれるキーへのポインターは、ソート用のカーソルの一部である配列にアセンブルされます。ハッシュバケットまたは配列ノードには最大数のキーがあるため、すべての時点でカーソルのサイズに事前設定された固定制限がハッシュバケットまたは配列ノードのキーがget-next（またはget-previous）によって使い果たされた後（イテレータを参照）、カーソルが次の基数ノードエントリに移動し、プロセスが繰り返されます。
参考文献
^ Procに掲載された記事に記載されています。第30回オーストラリアコンピュータサイエンス会議（ACSC2007）、オーストラリアのバララット。CRPIT、62. Dobbie、G.、Ed。ACS。97-105 ^ https://dl.acm.org/citation.cfm?id=1273761 HAT-trie：文字列のキャッシュを意識したTrieベースのデータ構造 ^ Askitis、N.＆Zobel、J.（2005）、文字列ハッシュテーブルのキャッシュを意識した衝突解決、’Proc。SPIRE文字列処理と情報検索の症状’、Springer-Verlag、pp。92–104 ^ Askitis、N.およびZobel、J. 2011.キャッシュを活用するために、文字列ハッシュテーブル、バーストトライ、およびBSTを再設計します。ACMJ.Exp。アルゴール。15、1、第1.7条 ^ バースト試行：文字列キーACMTransの高速で効率的なデータ構造。Inf。Syst。、Vol。20、No. 2.、pp。192-223、doi：10.1145 / 506309.506312 by Steffen Heinz、Justin Zobel、Hugh E.Williams ^ Sinha、R. and Wirth、A. 2010.エンジニアリングバーストソート：高速のインプレース文字列ソートに向けて。ACMJ.Exp。アルゴール。15、第2.5条 ^ http: //www.siam.org/meetings/alenex03/Abstracts/rsinha.pdf動的な試行による大量の文字列セットのキャッシュを意識した並べ替え
外部リンク
CでのHAT-Trieの実装を参照してください