簡介
分散式散列表示意圖發展背景
研究分散式散列表的主要動機是為了開發點對點系統，像是Napster、Gnutella及Freenet。這些系統得益於使用分散在網際網路上的各項資源以提供實用的套用，特別在頻寬及硬碟存儲空間上，他們所提供的檔案分享功能因此得到最大的好處。
這些系統使用不同的方法來解決如何找到擁有某數據的節點的問題。Napster 使用中央的索引伺服器：每個節點加入網路的同時，會將他們所擁有的檔案列表傳送給伺服器，這使得伺服器可以進行搜尋並將結果回傳給進行查詢的節點。但中央索引伺服器讓整個系統易受攻擊，且可能造成法律問題。於是，Gnutella 和相似的網路改用大量查詢模式（flooding query model）：每次搜尋都會把查詢訊息廣播給網路上的所有節點。雖然這個方式能夠防止單點故障（single point of failure），但比起 Napster 來說卻極沒效率。
最後，Freenet 使用了完全分散式的系統，但它建置了一套使用經驗法則的基於關鍵值的轉送方法（key based routing）。在這個方法中，每個檔案與一個關鍵值相結合，而擁有相似關鍵值的檔案會傾向被相似的節點構成的集合所保管。於是查詢訊息就可以根據它所提供的關鍵值被轉送到該集合，而不需要經過所有的節點。然而，Freenet 並不保證存在網路上的數據在查詢時一定會被找到。
分散式散列表為了達到 Gnutella 與 Freenet 的分散性（decentralization）以及 Napster 的效率與正確結果，使用了較為結構化的基於關鍵值的轉送方法。不過分散式散列表也有個 Freenet 有的缺點，就是只能作精確搜尋，而不能只提供部份的關鍵字；但這個功能可以在分散式散列表的上層實做。
最初的四項分散式散列表技術——內容可定址網路（Content addressable network，CAN）、Chord（Chord project）[1]、pastry（Pastry (DHT)），以及 Tapestry (DHT)（Tapestry (DHT)）皆同時於2001年發表。從那時開始，相關的研究便一直十分活躍。在學術領域以外，分散式散列表技術已經被套用在BitTorrent及CoralCDN（Coral Content Distribution Network）等。
性質
分散式散列表本質上強調以下特性：
離散性：構成系統的節點並沒有任何中央式的協調機制。
伸縮性：即使有成千上萬個節點，系統仍然應該十分有效率。
容錯性：即使節點不斷地加入、離開或是停止工作，系統仍然必須達到一定的可靠度。
要達到以上的目標，有一個關鍵的技術：任一個節點只需要與系統中的部份節點溝通。一般來說，若系統有n 個節點，那么只有 Θ(logn) 個節點是必須的（見後述）。因此，當成員改變的時候，只有一部分的工作（例如數據或關鍵值的傳送，散列表的改變等）必須要完成。
有些分散式散列表的設計尋求能對抗網路中惡意的節點的安全性，但仍然保留參加節點的匿名性。在其他的點對點系統（特別是檔案分享）中較為少見。參見匿名點對點技術。
最後，分散式散列表必須處理傳統分散式系統可能遇到的問題，例如負載平衡、數據完整性，以及效能問題（特別是確認轉送訊息、數據存儲及讀取等動作能快速完成）。
結構
分散式散列表的結構可以分成幾個主要的組件[2][3]。其基礎是一個抽象的關鍵值空間（keyspace），例如說所有160位長的字元串集合。關鍵值空間分區（keyspace partitioning）將關鍵值空間分區成數個，並指定到在此系統的節點中。而延展網路則連線這些節點，並讓他們能夠藉由在關鍵值空間內的任一值找到擁有該值的節點。
當這些組件都準備好後，一般使用分散式散列表來存儲與讀取的方式如下所述。假設關鍵值空間是一個160位長的字元串集合。為了在分散式散列表中存儲一個檔案，名稱為 filename 且內容為 data，我們計算出 filename 的 SHA1 散列值——一個160位的關鍵值 k——並將訊息 put(k,data) 送給分散式散列表中的任意參與節點。此訊息在延展網路中被轉送，直到抵達在關鍵值空間分區中被指定負責存儲關鍵值 k 的節點。而 (k,data) 即存儲在該節點。其他的節點只需要重新計算 filename 的散列值 k，然後提交訊息 get(k) 給分散式散列表中的任意參與節點，以此來找與 k 相關的數據。此訊息也會在延展網路中被轉送到負責存儲 k 的節點。而此節點則會負責傳回存儲的數據 data。
以下分別描述關鍵值空間分區及延展網路的基本概念。這些概念在大多數的分散式散列表實現中是相同的，但設計的細節部份則大多不同。
關鍵值空間分區
大多數的分散式散列表使用某些穩定散列（consistent hashing）方法來將關鍵值對應到節點。此方法使用了一個函式 δ(k1,k2) 來定義一個抽象的概念：從關鍵值k1 到 k2 的距離。每個節點被指定了一個關鍵值，稱為ID。ID 為 i 的節點擁有根據函式 δ 計算，最接近 i 的所有關鍵值。
例：Chord 分散式散列表實現將關鍵值視為一個圓上的點，而 δ(k1,k2) 則是沿著圓順時鐘地從 k1 走到 k2 的距離。結果，圓形的關鍵值空間就被切成連續的圓弧段，而每段的端點都是節點的ID。如果 i1 與 i2 是鄰近的 ID，則 ID 為 i2 的節點擁有落在 i1 及 i2 之間的所有關鍵值。
穩定散列擁有一個基本的性質：增加或移除節點只改變鄰近ID的節點所擁有的關鍵值集合，而其他節點的則不會被改變。對比於傳統的散列表，若增加或移除一個位置，則整個關鍵值空間就必須重新對應。由於擁有數據的改變通常會導致數據從分散式散列表中的一個節點被搬到另一個節點，而這是非常浪費頻寬的，因此若要有效率地支持大量密集的節點增加或離開的動作，這種重新配置的行為必須儘量減少。
延展網路
每個節點保有一些到其他節點（它的鄰居）的連結。將這些連結總合起來就形成延展網路。而這些連結是使用一個結構性的方式來挑選的，稱為網路拓樸。
所有的分散式散列表實現拓樸有某些基本的性質：對於任一關鍵值 k，某個節點要不就擁有 k，要不就擁有一個連結能連結到距離較接近 k 的節點。因此使用以下的貪心算法即可容易地將訊息轉送到擁有關鍵值 k 的節點：在每次運行時，將訊息轉送到 ID 較接近 k 的鄰近節點。若沒有這樣的節點，那我們一定抵達了最接近 k 的節點，也就是擁有 k 的節點。這樣的轉送方法有時被稱為“基於關鍵值的轉送方法”。
除了基本的轉送正確性之外，拓樸中另有兩個關鍵的限制：其一為保證任何的轉送路徑長度必須儘量短，因而請求能快速地被完成；其二為任一節點的鄰近節點數目（又稱最大節點度（Degree (graph theory)））必須儘量少，因此維護的花費不會過多。當然，轉送長度越短，則最大節點度越大。以下列出常見的最大節點度及轉送長度（n 為分散式散列表中的節點數）
最大節點度 O(1)，轉送長度 O(logn)
最大節點度 O(logn)，轉送長度 O(logn / loglogn)
最大節點度 O(logn)，轉送長度 O(logn)
最大節點度 O(n1 / 2)，轉送長度 O(1)
第三個選擇最為常見。雖然他在最大節點度與轉送長度的取捨中並不是最佳的選擇，但這樣的拓樸允許較為有彈性地選擇鄰近節點。許多分散式散列表實現利用這種彈性來選擇延遲較低的鄰近節點。
最大的轉送長度與直徑有關：最遠的兩節點之間的最短距離。無疑地，網路的最大轉送長度至少要與它的直徑一樣長，因而拓樸也被最大節點度與直徑的取捨限制住，而這在圖論中是基本的性質。因為貪婪算法(Greedy Method)可能找不到最短路徑，因此轉送長度可能比直徑長。
示例
分散式散列表實現與協定Bamboo
Bunshin
內容可定址網路 (Content Addressable Network)
Chord
DKS系統
Kademlia
Leopard
MACE
Pastry
P-Grid
Tapestry
BitTorrent：檔案分享套用。BitTorrent 可以選用DHT作為分散式Tracker。
Warez P2P：檔案分享套用。
The Circle：檔案分享套用與聊天。
CSpace：安全的溝通系統。
Codeen：網頁高速快取。
CoralCDN
Dijjer
eMule：檔案分享套用。
I2P：匿名網路。
jxta：開放原始碼的點對點平台。
NEOnet：檔案分享套用。
Overnet：檔案分享套用。
