ハッシュ配列ツリー

コンピュータサイエンスにおいて、ハッシュ配列ツリー（HAT）は、1996年にエドワード・シタルスキーによって発表された動的配列データ構造であり、 ^{[ 1 ]}連続した1つのメモリ領域にデータを保持する単純な動的配列とは異なり、データ要素を格納するために個別のメモリ断片（または「葉」）の配列を保持します。その主な目的は、自動的な配列サイズ変更操作による要素のコピーの量を減らし、メモリ使用パターンを改善することです。

単純な動的配列は、配列内の要素数をnとすると、幾何拡張に基づいて線形 (Ω( n )) の空間を浪費するのに対し、ハッシュ配列ツリーはO ( √ n )程度の記憶領域しか浪費しません。アルゴリズムを最適化することで、データコピーを完全に排除できますが、その代償として浪費される空間が増加します。

単純な動的配列よりは若干遅いものの、定数時間（O (1)）でアクセスを実行できます。ハッシュ配列ツリーの末尾に一連のオブジェクトを追加する場合、このアルゴリズムはO(1)の償却性能を持ちます。名前とは異なり、ハッシュ関数は使用しません。

Sitarski の定義によれば、ハッシュ配列ツリーは、 2 のべき乗の数のリーフ配列を含むトップレベルディレクトリを持ちます。すべてのリーフ配列は、トップレベルディレクトリと同じサイズです。この構造は、表面的には配列ベースの衝突チェーンを持つハッシュテーブルに似ており、これがハッシュ配列ツリーという名前の由来となっています。完全なハッシュ配列ツリーはm ²個の要素を保持できます。ここで、mはトップレベルディレクトリのサイズです。^{[ 1 ]} 2 のべき乗を使用することで、商と余りの算術演算ではなくビット演算による物理アドレス指定が高速化され^{[ 1 ]}、拡張中に時折グローバル配列のコピーが発生する場合でも、追加操作の償却パフォーマンスが O(1) であることが保証されます。

一般的な動的配列の幾何拡張方式では、配列はメモリの連続したチャンクとして再割り当てされ、新しいサイズは現在のサイズの2倍になります（そして、データ全体が新しい場所に移動されます）。これにより、拡張された配列が新しい容量の半分までデータで満たされるため、O(n)の無駄なスペースが発生するものの、O(1)の償却演算が保証されます。

ハッシュ配列ツリーがいっぱいになると、追加の追加操作に対応するために、ディレクトリとリーフを以前のサイズの2倍に再構築する必要があります。古い構造に保持されていたデータは、新しい場所に移動されます。その後、1つの新しいリーフのみが割り当てられ、トップ配列に追加されるため、トップ配列は新しい容量の4分の1までしか満たされません。すべての余分なリーフはまだ割り当てられておらず、必要なときにのみ割り当てられるため、ストレージの無駄はO ( √n )だけです。^{[ 2 ]}

サイズを縮小するには複数の方法があります。ハッシュ配列ツリーが8分の1まで埋まったら、より小さく、半分まで埋まったハッシュ配列ツリーに再構築できます。別の方法としては、リーフのサイズを変更せずに、未使用のリーフ配列のみを解放する方法があります。さらに最適化するには、必要に応じてディレクトリ配列を拡張しながら、サイズを変更せずに新しいリーフを追加する方法があります（幾何級数的な拡張など）。これにより、無駄なスペースが小さな定数でO ( n )になるという代償を伴いますが、データコピーの必要性は完全に排除され、再構築は設定されたしきい値のオーバーヘッドに達した場合にのみ実行されます。^{[ 1 ]}

Brodnik ら^{[ 5 ]}は、ハッシュ配列ツリーと同様のスペース浪費プロファイルを持つ動的配列アルゴリズムを発表しました。Brodnik の実装では、ハッシュ配列ツリーと比較してアドレス計算関数がより複雑ですが、以前に割り当てられたリーフ配列を保持します。