リニアハッシュ（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は０としておきます。（今は深く考えないでください。） すると、

[ono_matope]

ノード一台追加した時の移動量は確かに減ってる(そのかわり1台しかリバランスされないけど)