分散式雜湊表

分布式散列表（英语：distributed hash table，缩写DHT）是分布式计算系统中的一类，用来将一个关键值（key）的集合分散到所有在分布式系统中的节点，并且可以有效地将消息转送到唯一一个拥有查询者提供的关键值的节点（Peers）。这里的节点类似散列表中的存储位置。分布式散列表通常是为了拥有极大节点数量的系统，而且在系统的节点常常会加入或离开（例如网络断线）而设计的。在一个结构性的延展网络（overlay network）中，参加的节点需要与系统中一小部分的节点沟通，这也需要使用分布式散列表。分布式散列表可以用以创建更复杂的服务，例如分布式文件系统、点对点技术文件分享系统、合作的网页缓存、多播、任播、域名系统以及即时通信等。

发展背景

研究分布式散列表的主要动机是为了开发点对点系统，像是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）、Pastry（Pastry (DHT)），以及Tapestry (DHT)（Tapestry (DHT)）皆同时于2001年发表。从那时开始，相关的研究便一直十分活跃。在学术领域以外，分布式散列表技术已经被应用在BitTorrent及CoralCDN（Coral Content Distribution Network）等。

结构

分布式散列表的结构可以分成几个主要的组件。其基础是一个抽象的关键值空间（keyspace），例如说所有160位长的字符串集合。关键值空间分区（keyspace partitioning）将关键值空间分区成数个，并指定到在此系统的节点中。而延展网络则连接这些节点，并让他们能够借由在关键值空间内的任一值找到拥有该值的节点。
当这些组件都准备好后，一般使用分布式散列表来存储与读取的方式如下所述。假设关键值空间是一个160位长的字符串集合。为了在分布式散列表中存储一个文件，名称为且内容为，我们计算出的SHA1散列值——一个160位的关键值——并将消息送给分布式散列表中的任意参与节点。此消息在延展网络中被转送，直到抵达在关键值空间分区中被指定负责存储关键值的节点。而即存储在该节点。其他的节点只需要重新计算的散列值，然后提交消息给分布式散列表中的任意参与节点，以此来找与相关的数据。此消息也会在延展网络中被转送到负责存储的节点。而此节点则会负责传回存储的数据。
以下分别描述关键值空间分区及延展网络的基本概念。这些概念在大多数的分布式散列表实现中是相同的，但设计的细节部分则大多不同。

关键值空间分区

大多数的分布式散列表使用某些稳定散列（consistent hashing）方法来将关键值对应到节点。此方法使用了一个函数来定义一个抽象的概念：从关键值到的距离。每个节点被指定了一个关键值，称为ID。ID为的节点拥有根据函数计算，最接近的所有关键值。
例：Chord分布式散列表实现将关键值视为一个圆上的点，而则是沿着圆顺时钟地从走到的距离。结果，圆形的关键值空间就被切成连续的圆弧段，而每段的端点都是节点的ID。如果与是邻近的ID，则ID为的节点拥有落在及之间的所有关键值。
稳定散列拥有一个基本的性质：增加或移除节点只改变邻近ID的节点所拥有的关键值集合，而其他节点的则不会被改变。对比于传统的散列表，若增加或移除一个位置，则整个关键值空间就必须重新对应。由于拥有数据的改变通常会导致数据从分布式散列表中的一个节点被搬到另一个节点，而这是非常浪费带宽的，因此若要有效率地支持大量密集的节点增加或离开的动作，这种重新配置的行为必须尽量减少。
将相近的关键值分配给了距离相近的节点Locality-preserving_hashing，可以实现更短的查询延迟，从而提高DHT的查询效率。相关工作包括Self-Chord和LDHT