[B! データ構造] ono_matopeのブックマーク

ono_matope id:ono_matope

データ構造に関するono_matopeのブックマーク (2)

リニアハッシュ（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 2014/01/04
ノード一台追加した時の移動量は確かに減ってる(そのかわり1台しかリバランスされないけど)

データ構造
リンク
Prefix hash tree - Wikipedia
prefix hash tree(PHT)は分散ハッシュテーブル (DHT)上で複雑なクエリを可能にする分散データ構造である。prefix hash treeはDHTのルックアップインタフェースを使用し、トライ木に基づいたデータ構造を構築し、これは高効率であり、かつ耐障害性がある。効率性に関しては、更新はインデックスされるドメインの大きさに対し2重対数のオーダである。また、耐障害性に関しては、prefix hash treeのいずれのノードにおいて障害が発生しても他のノード上のデータはアクセス可能である。外部リンク[編集] http://berkeley.intel-research.net/sylvia/pht.pdf - Prefix Hash Tree: An Indexing Data Structure over Distributed Hash Tables http://
ono_matope 2012/10/17
データ構造
リンク
1