Tomo’s HotLine: [P2P]DHT（分散ハッシュテーブル）ショートクイズ に挑戦してみた、けど…。
クイズ１：
DHT（分散ハッシュ）でハッシュ関数hash_Aを使用していた。しかし、ハッシュ関数hash_Aが不完全で、異なる数字y,zに対してhash_A(y)=hash_A(z)になる場合があることがわかった。この時にDHT系全体としてどのような問題が生ずるだろうか？
ハッシュ関数hash_A が不完全であるという前提でシステムを構築していない場合、DHT に登録するデータに付与する 一意 な ID として dataID = hash_A(data) を用いている可能性がある。
dataID = hash_A(y) = hash_A(z) が付与されたデータを管理するノードB, C があるとする。ノードB, C には既に数字y を登録しているものとする。いま、ノードB に数字z を登録すると、dataID が同じであるためノードB に既に登録されている数字y は上書きされて消えてしまう(上書きを許さない設計なら数字z は DHT に登録できませんね)。また、この状態で DHT から dataID をもとにデータの取得を行うと、ノードB, C がそれぞれ異なる数字を返すことになる。
クイズ２：
ノードAの名前をA_nameとする。ノードAの保持するハッシュ値（hash_IDとしよう）を完全なハッシュ関数hash(）を使って
hash_ID=hash(name)
で定義する時、しばしばDHT系として不具合が生じる可能性がある。それはどうしてか？またそれを回避する方法を考えて下さい。ただし、回避方法としてなるべくnameを活用して欲しい。
ここで言う完全なハッシュ関数とは異なる数字y,zの時にhash(y)とhash(z)が異なる事を指す。
DHT にデータを登録していくにあたって、最良の場合でも登録可能なデータ数はノード数を超えることが出来なくなる(ってことですか? わかりません orz)。hash() は完全なハッシュ関数であるから、ノードA が保持する hash_ID は唯一のものである。これから、ノードAは唯一の hash_ID を生成するデータ、A_name しか保持できない(あれれ、問題ではそこまで言ってない…)。
はい、わかりませーん…。
もしかして、hash_ID = hash(name + rand()) ってこt、、、それでもハッシュ関数が完全かどうかは関係ありませんね…。
これは、やはりチラシの裏に留めておくべきでしたか、いろんな意味で。どう見ても勉強不足です。本当にありがとうございました。
