「あいうえお」ということは少なくともノードが数１０個あれば「あいうえお」で 書かれているデータは全て分散管理ができる。
ところで、「あ」で始まるファイル名と「ぬ」で始まるファイル名はどちらの方が 多いだろうか？一般的には明らかに「あ」の方が管理しているデータ量が多いはず だ。つまり「あいうえおDHT」では各ノードによってデータの保持している量に ばらつきがあって、不公平感があるのだ。ノード「あ」とノード「ぬ」では負荷に かなりの違いがある。
もうひとつ問題がある。それはノードの数に拡張性が無い事だ。「あいうえお」は 50音だから50個あるわけなので、「あいうえおDHT」では50個ノードがあればデータ は管理できる。しかし、ノードが1000個あった場合どうだろうか？ 「あいうえお」は50個しかないので、「あいうえおDHT」ではノード数５０を 超えるノードはデータはこの方法では管理できない。なんらかの改良をしなければ ならない。
このように「あいうえおDHT」では考え方が直感的であるのだが上記のような 2つの欠点があった。それを解決するのがハッシュという概念だ。
一般にハッシュ関数をｆとするとｘとｙが違えばf(x),f(y)は異なる。 もうちょっと言うとxとyが「ほとんど同じ」であってもf(x),f(y)は「全く異なる」。 そして、一般に集合Xに対してxをXの要素とすると集合F=f(x)は ほぼランダムな要素となる。 つまり、ｘがどんな要素であっても、それがたくさん集まって全体集合Ｘを ハッシュ関数にかけるとその結果はランダムな要素からなる集合のように見える のだ。ちなみにハッシュ関数の出力する値を一般にハッシュ値と呼ぶ。
イメージを掴んでもらうため補足をしよう。 今、ハッシュ関数をfとするとハッシュ値は次のような感じになる。
・f(スカイプ）=1520329652
・f(スカイプ。）=5206812783
・f(スカイプ！）=9206283712
・f(スカイプしようかな？それともとりあえずメッセンジャーかな？）=3879018213
このように、少し文字列が変わってもハッシュ値が大きく変わる事がわかるだろう。 またどんなに長い文字列だとしてもハッシュ値の「長さ」は一定である。
このハッシュ値を使えば、先ほど「あいうえおDHT」の欠点であるノード間の不公平な 負荷は解消される。 つまり、今、「モナリザ」という名前のデータを管理したいとすれば、 x=f(モナリザ）となるハッシュ値xを管理するノードにデータを渡せばよい。
もし、ある人が「スカイプ」のデータを登録したければ、ノード「1520329652」に データを登録すれば良い。 逆に「スカイプ」のデータが欲しければノード「1520329652」にデータを 参照すれば良い。これは一般のDHTと同じ考え方だ。
また、ハッシュ値を大きくすれば多くのノードが参加してもうまく負荷分散すること がわかるだろう。「あいうえおDHT」では50個までのノードしか上手く機能しないが、 今6桁の10進数を出力するハッシュ関数を使えば、10万ノードまでうまく負荷分散が できる。
ちなみにハッシュ関数としてはSHA-１をよく使うが、これは0〜数10億までハッシュ値 が存在する。つまり数10億ノードが参加しても大丈夫！ということだ。これがDHTでは 非常に多くのノードの参加が可能である理由のひとつとなる。
最後にハッシュ関数を使ってハッシュ値を求めるには非常に高速でできることを付け 加えておこう。
ハッシュ関数を使うと、各ノード毎にデータ量・件数を公平に管理でき、 また非常の多くのノードが参加するDHTが作れる事を説明した。ただし、 「あいうえおDHT」については直感的で説明しやすいので今後も何度も登場する。
まず、いつものように「あいうおえおDHT」を考えてみよう。「あいうえお」は50音 だから、ノードが50個あれば丁度一つの文字に対して一つのノードが対応するわけで ある。では、ノードが20個ならばそれぞれのノードはどのように管理すれば良いの だろうか？
今、あ行を考えてみよう。
このときには各文字についてノードが存在するから、各ノードはその頭文字から 始まるデータを管理すれば良い。
ノード「う」がない状態だ。ということは頭文字「う」を管理することをどこかの ノードにに任せないといけない。 例えば、あいうえおＤＨＴでは管理するノードがない場合、 その直前に存在するノードがそのデータを管理する事にしよう。ということは ノード「い」が頭文字「う」のデータも管理する事になる。
ノード「い」、「う」、「お」がない状態だ。状態２の考え方でいくと、 ノード「あ」が頭文字「い、う」のデータ、ノード「え」が頭文字「お」 のデータも管理する事になる。
（※ちなみに先ほどの「あいうえお」DHTのルールである次のノードの直前（つまり次のノードのハッシュ値の1つ前）まで管理する方法は実はDHTの代表格「Chord」と全く同じである。）
では話を抽象化してハッシュ空間で考えてみよう。
今、ハッシュ関数f()が0〜6までの整数のハッシュ値を取るとする。 つまり任意の文字列x についてf(x)=[{0,1,2,3,4,5,6}のいずれか]となる。
◇ノード数が１の場合、そのノードは全てのデータを管理する事になる。 この時全てのデータに関してハッシュ値とそれに対応されたデータの表が一つ できるはずである。 このようなデータとハッシュ値を対応した表を「ハッシュテーブル」と呼ぶ事 にしよう。 なお、テーブルとは英語で「表」を表わす。
コミックを例に取るとハッシュテーブルとはこんな感じの表になる。
ハッシュ値:ハッシュに対応したデータ
0:ドラえもん
1:ワンピース
2:ドラゴンボール
3:こち亀
4:島耕作
5:NANA
6:ジパング
では、ノード数が３の場合にはどうなるのであろうか？ 例えば、ノード「０」とノード「２」、ノード「５」の３つのノードが存在する 場合にはそれぞれが保持するハッシュテーブルは以下の通りになる。
ノード「０」のハッシュテーブル
0:ドラえもん
1:ワンピース
ノード「２」のハッシュテーブル
2:ドラゴンボール
3:こち亀
4:島耕作
ノード「５」のハッシュテーブル
5:NANA
6:ジパング
このように「ハッシュテーブル」が各ノードに分散して配置される事になる事が 分かるだろう。この技術が「分散ハッシュテーブル」すなわちDHT(Distributed Hash Table」と呼ばれる 理由である。
今のようにすれば、例えばハッシュ空間が非常に巨大になってノードが数億参加して も同じようなルールで各ノードが分散してハッシュテーブルを持つことになる。
既にピンと来ている人がいると思うが、例えばワンピースのデータが欲しければ ノード０、ジパングのデータがほしければノード５に問い合わせをすれ ばよい。
ところで、ノード０やノード５と通信するにはどうすれば 良いのだろうか？全てのノードのIPアドレスを集中管理をするのは大変だ。 そこで、ルーティングと言う手段を使って巧妙にこのことを解決している。