タブレーションハッシュ

コンピュータサイエンスにおいて、タブレーションハッシュ法は、テーブルルックアップと排他的論理和演算を組み合わせることで、ハッシュ関数の汎用ファミリーを構築する方法です。これは、コンピュータゲーム用のゾブリストハッシュ法として最初に研究されました。その後、カーターとウェグマンによる研究で、この方法が任意の固定長キーに拡張されました。タブレーションハッシュ法の一般化も開発され、テキスト文字列などの可変長キーを処理できるようになりました。

タブレーション ハッシュは単純ですが、他のハッシュ関数とは異なる強力な理論的特性を持っています。特に、3 独立です。つまり、3 組のキーはすべて、3 組のハッシュ値にマッピングされる可能性が等しくなります。ただし、4 独立ではありません。タブレーション ハッシュのより洗練されているが遅い変種では、この方法がより高い独立性に拡張されます。

タブレーション ハッシュは独立性が高いため、ホップスコッチ ハッシュ、カッコウ ハッシュ、集合交差のサイズを推定する MinHash手法など、高品質のハッシュ関数を必要とするハッシュ メソッドで使用できます。

基本的な考え方は次のとおりです。

まず、ハッシュするキーを、選択した長さの小さな「ブロック」に分割します。次に、各ブロックに 1 つずつルックアップ テーブルのセットを作成し、ランダムな値を入力します。最後に、テーブルを使用して各ブロックのハッシュ値を計算し、ビット単位の排他的論理和演算を使用して、これらすべてのハッシュを最終的なハッシュ値に結合します。^[1]

より正式には:

ハッシュするキーのビット数をp 、出力ハッシュ関数で必要なビット数をqとします。ブロック サイズr ≤ p を選択します。ブロック サイズの選択によって、時間とメモリ使用量のトレードオフが制御されるため、テーブルが大きくなりすぎないように、たとえばテーブルがコンピュータのキャッシュ メモリに収まるようにする必要があります。^[2]ブロックが小さいほどメモリの使用量が少なくなりますが、ハッシュ関数の速度が低下します。キーを表すために必要な rビットのブロック数t = ceil( p / r ) を計算します。

2次元の2 ^r × t配列Tを作成し、ランダムなqビットの数値を入力します。これで、 T を使用して任意のキー xのハッシュ値h ( x ) を計算できます。これを行うには、x をrビット値に分割します。ここで、 x _0はxの最下位rビットで構成され、x _{1 は}次のrビットで構成されます。たとえば、r  = 8 の場合、x _{i は}xのi番目のバイトになります。次に、これらのrビットと位置の値をTのインデックスとして使用し、排他的論理和演算を使用して結果を結合します。^[1]

h ( x ) = T [0][ x ₀ ] ⊕ T [1][ x ₁ ] ⊕ T [2][ x ₂ ] ⊕ ... ⊕ T [t-1][ x _t-1 ] です。

各x _{iに対して同じテーブル (例:} T[0] )を使用することは無効であることに注意してください。その場合、ハッシュ関数は同じx _iを持つが異なる順序で並べ替えられた文字列を区別できなくなります。

r  =  t  = 8、q  =  p = 64の典型的な例のコードを 以下に示します。

// 乱数の秘密テーブル
uint64_t T [ 8 ][ 256 ]; for ( int i = 0 ; i < 8 ; i ++ ) for ( int j = 0 ; j < 256 ; j ++ ) T [ i ][ j ] = getRandomUInt64 (); 
        
           
        

// 単純な集計ハッシュ関数
uint64_t hash ( uint64_t x ) { uint64_t res = 0 ; for ( int i = 0 ; i < 8 ; i ++ ) res ^= T [ i ][( char )( x >> 8 * i )]; return res ; }   
      
           
          
    

タブレーションハッシュ法の最初の例はゾブリストハッシュ法である。これはチェスなどの抽象的なボードゲームの位置をハッシュする方法で、1970年に発表したアルバート・リンゼイ・ゾブリストにちなんで名付けられた^。[3]この方法では、チェスの駒とチェス盤のマス目の組み合わせなど、各ゲームの特徴に対してランダムなビット文字列を生成する。次に、任意のゲームの位置をハッシュするために、その位置の特徴のビット文字列をビット単位の排他的論理和で結合する。結果のハッシュ値は、転置表のインデックスとして使用できる。通常、各移動では少数のゲームの特徴のみが変化するため、移動後の位置のゾブリスト値は、移動前の位置の値からすばやく更新でき、位置のすべての特徴をループする必要もない。^[4]

より一般的な任意のバイナリ値に対するタブレーションハッシュは、後にCarterとWegman (1979)によって再発見され、PătraşcuとThorup (2012)によってさらに詳細に研究されました。

Carter と Wegman (1979) は、ハッシュ関数を生成するためのランダム化スキームがユニバーサルであるとは、任意の 2 つのキーについて、それらが衝突する(つまり、互いに同じ値にマップされる) 確率が 1/ mである( mはキーが取り得る値の数) と定義しています。彼らはその後の論文 Wegman と Carter (1981) で、より強い特性を定義しました。ハッシュ関数を生成するためのランダム化スキームがk独立であるとは、すべてのk組のキーと各可能なk組の値について、それらのキーがそれらの値にマップされる確率が 1/ m ^kであるということです。2 独立ハッシュ スキームは自動的にユニバーサルであり、ユニバーサル ハッシュ スキームは、アルゴリズムの初期化フェーズの一部として乱数x を格納し、各ハッシュ値にx を追加することで、2 独立スキームに変換できます。したがって、ユニバーサル性は本質的に 2 独立性と同じです。ただし、kの値が大きい場合のk独立性はより強力な特性であり、より少数のハッシュ アルゴリズムによって保持されます。

Pătraşcu & Thorup (2012) が指摘しているように、タブレーション ハッシュは 3 独立ですが 4 独立ではありません。任意の単一のキーxについて、T [ x ₀ ,0] が任意のハッシュ値になる可能性は等しく、T [ x ₀ ,0] と残りのテーブル値の排他的論理和によってこの特性は変化しません。任意の 2 つのキーxとyについて、x が任意のハッシュ値にマップされる可能性は以前と同様に等しく、x _i  ≠  y _iとなる位置iが少なくとも 1 つあります。テーブル値T [ y _i , i ] はh ( y )の計算に使用されますが、 h ( x )の計算には使用されないため、 h ( x ) の値が決定された後でも、 h ( y ) が任意の有効なハッシュ値になる可能性は等しくあります。同様に、任意の3つのキーx、y、zについて、少なくとも3つのキーのうちの1つには、その値z _iが他の2つと異なる位置iがあり、そのためh ( x )とh ( y )の値が決定された後でも、h ( z )が任意の有効なハッシュ値である可能性は等しくあります。^[5]

しかし、この推論は 4 つのキーに対しては成り立たない。なぜなら、w、x、y、zのキーセットがあり、その 4 つのうちのどれもが、少なくとも 1 つの他のキーと共有しないバイト値を持たないからである。たとえば、キーがそれぞれ 2 バイトで、w、x、y、zがバイト値として 0 または 1 を持つ 4 つのキーである場合、各位置の各バイト値は 4 つのキーのうち 2 つによって共有される。これらの 4 つのキーの場合、タブレーションハッシュによって計算されたハッシュ値は常に式h ( w ) ⊕ h ( x ) ⊕ h ( y ) ⊕ h ( z ) = 0 を満たしますが、4 独立ハッシュ方式の場合、同じ式が満たされる確率は 1/ mだけである。したがって、タブレーションハッシュは 4 独立ではない。^[5]

タブレーションハッシュはユニバーサルハッシュ方式であるため、ユニバーサル性が十分であれば、あらゆるハッシュベースのアルゴリズムで使用できます。たとえば、ハッシュ連鎖では、操作あたりの予想時間は衝突確率の合計に比例しますが、これは、あらゆるユニバーサル方式で、真にランダムなハッシュ関数の場合と同じであり、ハッシュテーブルの負荷係数が一定であれば常に一定です。したがって、タブレーションハッシュは、操作あたりの予想時間が一定であることを理論的に保証しながら、ハッシュ連鎖のハッシュ関数を計算するために使用できます。^[6]

しかし、ユニバーサルハッシュは、他のハッシュアルゴリズムのパフォーマンスを保証するほど強力ではありません。たとえば、線形プローブの場合、5つの独立したハッシュ関数は定数時間の動作を保証するのに十分強力ですが、4つの独立したハッシュ関数では失敗することがあります。^[7]ただし、3つの独立したハッシュ関数しかないにもかかわらず、タブレーションハッシュは線形プローブに対して同じ定数時間保証を提供します。^[8]

ハッシュ テーブルを実装するための別の手法であるカッコウ ハッシュ法では、ハッシュ関数に関係なく、ルックアップごとに一定の時間が保証されます。カッコウ ハッシュ テーブルへの挿入が失敗してテーブル全体が再構築される場合もありますが、そのような失敗は起こりにくいため、挿入ごとの予想時間 (完全にランダムなハッシュ関数または対数独立のハッシュ関数を使用) は一定です。一方、タビュレーション ハッシュ法では、失敗確率に関する既知の最良の境界はより高く、挿入に一定の予想時間がかかることを保証できないほど高くなります。それでも、タビュレーション ハッシュ法は、テーブルが使用されても変化しない静的なキー セットに対して、カッコウ ハッシュ テーブルを線形予想時間で構築することを保証するのに十分です。^[8]

上で説明したタビュレーション ハッシュ (「単純なタビュレーション ハッシュ」) は 3 独立のみですが、この方法のバリエーションを使用すると、はるかに高い独立性を持つハッシュ関数を取得できます。Siegel (2004) は、排他的論理和演算を使用してテーブルからのランダムな値を結合するという同じアイデアと、キー ビットをテーブル インデックスに変換するためのエクスパンダ グラフに基づくより複雑なアルゴリズムを使用して、 kの任意の定数または対数値に対してkに依存しないハッシュ スキームを定義しています。ただし、Siegel のタビュレーション ハッシュのバリエーションを使用して各ハッシュ値を計算するために必要なテーブル検索の数は、一定ではあるものの、依然として多すぎて実用的ではありません。また、Siegel の手法でエクスパンダが使用されているため、完全に構築的ではありません。Thorup (2013) は、より構築的な方法で、より迅速に高い独立性に到達する、タビュレーション ハッシュに基づくスキームを提供しています。彼は、1 ラウンドの単純なタブレーション ハッシュを使用して入力キーを元の長さの 6 倍に拡張し、次に拡張されたキーに対して 2 ラウンドの単純なタブレーション ハッシュを使用すると、独立数がパラメーターr (キーをブロックに分割する際のブロックあたりのビット数) の指数関数となるハッシュ スキームが得られることを観察しました。

単純な集計は、キー内のブロックの位置ごとに異なるランダム値のテーブルを初期化する必要があるため、固定長のキーに制限されます。 Lemire (2012) は、文字列などの可変長キーに適した集計ハッシュのバリエーションを研究しています。 Lemire が研究した一般的なタイプのハッシュ スキームでは、キー内の位置に関係なく、ブロックの値でインデックス付けされた単一のテーブルT を使用します。 ただし、このテーブルの値は、ビットごとの排他的論理和よりも複雑な関数によって結合される場合があります。 Lemire は、このタイプのスキームは 3 独立にはできないことを示しています。 それでも、2 独立を実現することは可能であることを示しています。 特に、値T [ x _i ] (ここで、x _iは、前述のように、入力のi番目のブロック) を有限体上の多項式の係数として解釈し、結果の多項式の剰余を別の多項式で割ったものを取る集計スキームは、2 独立ハッシュ関数を与えます。

混合タブレーションハッシュ（およびそれほど一般的ではないツイストタブレーション）は、タブレーションハッシュの特性を強化しながら、ほぼ同じパフォーマンスを維持する方法として、DahlgaardとThorup ^[9]によって導入されました。混合タブレーションは、「ダブルタブレーション」Thorup（2013）ハッシュ関数と単純なタブレーションハッシュ関数のXOR演算と見ることができます。これは、混合タブレーションをダブルタブレーションよりもはるかに高速にするようにパラメータを選択した場合でも、多くの優れた特性を持つことがわかります^[10]

アイデアは、数字を選んで、だけではなくビットにハッシュすることです。これにより、新しい「派生文字」が生成され、2番目のハッシュ関数によってハッシュされ、2つの値が排他的論理和されます。正式には、 と があり、どちらも単純な集計関数です。 の場合、混合集計ハッシュは次のように定義されます。${\displaystyle d}$${\displaystyle 2^{rd+q}}$${\displaystyle 2^{q}}$${\displaystyle d}$${\displaystyle h_{1}:[2^{p}]\to [2^{rd}]\times [2^{q}]}$${\displaystyle h_{2}:[2^{rd}]\to [2^{q}]}$${\displaystyle (v_{1},v_{2})=h_{1}(x)}$${\displaystyle h(x)=h_{2}(v_{1})\oplus v_{2}.}$

次の例は、、およびを使用したアルゴリズムを示しています。 ${\displaystyle p=q=64}$${\displaystyle r=8}$${\displaystyle d=2}$

int D = 2 ; uint128_t T1 [ 8 ][ 256 ]; uint64_t T2 [ D ][ 256 ];   
 
 

// テーブルにランダムな値を入力します
for ( int j = 0 ; j < 256 ; j ++ ) { for ( int i = 0 ; i < 8 ; i ++ ) T1 [ i ][ j ] = getRandomUInt128 (); for ( int i = 0 ; i < D ; i ++ ) T2 [ i ][ j ] = getRandomUInt64 (); }         
           
        
           
        


// D 個の派生文字を含む x の混合タブを計算します
uint64_t hash ( uint64_t x ) { uint128_t v1v2 = 0 ; for ( int i = 0 ; i < 8 ; i ++ ) v1v2 ^= T1 [ i ][( char )( x >> 8 * i )]; uint64_t v1 = v1v2 >> 64 ; // 下位ビットから v1 を取得しますuint64_t h = ( uint64_t ) v1v2 ; // 上位ビットから v2 を取得しますfor ( int i = 0 ; i < D ; i ++ ) h ^= T2 [ i ][( char )( v1 >> 8 * i )]; return h ; }   
      
           
          
             
        
           
          
    

^{混合集計法は、2016年に[11]} k分割に関して強い集中力を持つことが示され、これはFlajoletとMartinによる古典的な方法など、異なる要素を数えるアルゴリズムに有用である。

二次資料

• Morin, Pat (2014 年 2 月 22 日)、「セクション 5.2.3: タブレーション ハッシュ」、Open Data Structures (疑似コード) (0.1G β 版)、pp. 115–116、2016年 1 月 8 日に取得。
• Mitzenmacher, Michael ; Upfal, Eli (2014)、「いくつかの実用的なランダム化アルゴリズムとデータ構造」、Tucker, Allen、Gonzalez, Teofilo、Diaz-Herrera, Jorge (編)、『コンピューティング ハンドブック: コンピュータ サイエンスとソフトウェア エンジニアリング(第 3 版)』、CRC Press、pp. 11-1 – 11-23、ISBN 9781439898529特にセクション11.1.1「タブレーションハッシュ」（11-3～11-4ページ）を参照してください。

一次資料