分散ハッシュテーブル
DHTはサーバの集合により構成され、主な機能はハッシュテーブルと同等である。あるキー(ビット列)をハッシュ関数、あるいは何らかの直線化関数により論理的な空間の1点に射影し、射影された点に値を関連づけることを特徴とする。DHTは高いスケーラビリティを持つことが特徴である。スケーラビリティは、DHTに参加するノード数Nに対して、どのノードから探索を開始しても、全てのノードにO(N)オーダよりも良いオーダ (Chord等の代表的なアルゴリズムではO(log(N))) の通信により到達可能なことが確率的に保証されていることによる。この性質は、スケーラビリティを実現するための自律分散的なアルゴリズムに従った多数のノードによる、ハッシュテーブルを管理する論理空間の分割統治によるものである。論理空間の一部の管理を分担したDHTノード間で構成するオーバーレイネットワークの構成と、その上でのルーティングを工夫することでスケーラビリティを実現している。
以上から、キーに対するハッシュ関数の適用方法、ハッシュ値を射影する論理空間の定義、ハッシュ値の論理空間への射影方法、分割統治のための論理空間の分割方法、ノードの空間への射影方法、ノードで構成するオーバーレイネットワークの構成方法(参加・脱退・経路の学習など)などの差異により、さまざまな特徴のDHTが存在する。
分散ハッシュテーブルのアルゴリズムを特徴付ける大きな要素として、キーを写像する論理空間と、各ノードが保持する経路表の管理方法による分類を行う。