リニアハッシュ（Linear Hash）

今年の技術士二次試験には、Linear Hashに関する出題がありました。
恥ずかしながら、僕はLinear Hashって分からなかったのですが、Hashに関する一般的な知識から何とか回答することはできました。
木構造との比較でPros & Consを求めた出題ですので、Linear Hashを深追いする必要はないのでしょうけれど、分からなかったことをそのままにしないのが僕のPolicy。なぜかあまり情報が見つからなかったので、Memoっておくことにしました。

Linear HashのHash関数は他にもあるかも知れませんが、調べた感じでは．．．

h[i](c) = c mod (2^i)N

式の意味は後で分かると思うので、実際の動きを追ってみます。

まず、Hash空間のSizeの初期状態が4だとします。（N=4）
このとき、iは０としておきます。（今は深く考えないでください。）
すると、現時点でのHash関数は

h(c) = c mod 4

ここで、例として5,7,8,14,17,12とIndex化していきます。
この時点で、Hash値とそこにぶら下がった値は下の図のようになります。

この時点でHash値0と1はSynonymが発生し、検索効率が落ちています。
そこで、Hash空間を大きくして、Synonymが極力発生しないようにしたいと思います。

しかし、普通のHashであれば、全ての値に関して、Index化をやりなおす必要がありますのでちょっと大事になってしまいます。Linear Hashでは全ての値についてIndex化を行う必要はありません。
手順を見てみましょう。

とにかく、Hash空間を0～4に増やします。

そして、ここが面白いところですが、Hash関数は

h(c) = c mod 5

ではなくて、もとの定義のiを1増やして

h(c) = c mod (2^1)4 = c mod 8

と、するのです。
ですが、この様にすると、例えば、7のHash値は7ですから、Hash空間のSizeを越えてしまいます。そこで、結果として得られた「Hash値がHash空間のSizeを越えるようであれば、前と同じHash関数を使う」と言うことにしておきます。
すると、Hash空間の1～3にぶら下がっている値は、結果としてHash値変更無しと言うことになります。影響を受けるのは、Hash値0にぶら下がっている値だけです。

Hash値0にぶら下がっている、8と12のHashを上に従って計算すると、それぞれ0と4。
ですので、12は4の下に動かします。

さらにHash空間を拡張してみます。これも面白いところですが、Hash関数は

h(c) = c mod (2^1)4 = c mod 8

のまま利用します。しかし、Hash空間が広がっていますので、「Hash値がHash空間のSizeを越えるようであれば、前と同じHash関数を使う」というRuleの部分の関係でHash値1にぶら下がっている5と17が影響を受けます。つまり、5のHash値は5ですが、17のHash値は1のままですので、値5がHash値5の下に移動します。ここでも影響を受けるのは、Hash値1の下だけです。

と、この様に、Hash空間の拡張が、Incrementalに出来るので、Hash空間が足りなくなった！！と後でジタバタする必要が無いわけですね。すばらしい！！