分散式杂凑表的简单基本解释

DHT 为用户提供与普通哈希表相同类型的接口(按键查找值) ，但是数据分布在任意数量的连接节点上。维基百科有一个很好的基本介绍，如果我写更多的话，基本上就是在反刍

Http://en.wikipedia.org/wiki/distributed_hash_table

好吧，他们基本上是一个非常简单的想法。DHT 提供了一个类似字典的接口，但是节点分布在整个网络中。DHT 的诀窍在于，通过散列找到存储特定密钥的节点，因此实际上您的散列表存储桶现在是网络中的独立节点。

这提供了大量的容错性和可靠性，并可能带来一些性能好处，但是也引起了许多令人头疼的问题。例如，当一个节点由于失败或其他原因离开网络时会发生什么？以及如何在节点连接时重新分配密钥，以使负载大致平衡。说到这个，你是怎么平均分配钥匙的？当一个节点加入时，如何避免重新散列所有内容？(记住，如果增加桶的数量，就必须在普通散列表中执行此操作)。

解决这些问题的一个示例是由 n 个节点组成的逻辑环，每个节点负责1/n 个密钥空间。一旦向网络中添加了一个节点，它就会在环上找到一个位置，坐落在另外两个节点之间，并负责其兄弟节点中的一些键。这种方法的优点是不会影响环中的其他节点; 只有两个兄弟节点必须重新分发密钥。

例如，在一个三节点环中，第一个节点的键值为0-10，第二个节点的键值为11-20，第三个节点的键值为21-30。如果出现第四个节点并将自己插入到节点3和0之间(记住，它们在一个环中) ，它可以负责比如说3的一半密钥空间，所以现在它处理26-30，而节点3处理21-25。

还有许多其他类似的覆盖结构，它们使用基于内容的路由来查找存储密钥的正确节点。在一个环中定位一个密钥需要每次在环中搜索一个节点(除非您保留一个本地查找表，这在数千个节点的 DHT 中是有问题的) ，这是 O (n)-跳路由。其他结构-包括增强环-保证 O (logn)-跳路由，以及一些声称 O (1)-跳路由的代价更多的维护。

阅读维基百科页面，如果你真的想深入了解，可以看看哈佛大学的 课程，它有一个相当全面的阅读清单。

我想补充一下亨利的有用的答案，因为我刚刚对一致哈希有了一个深入的了解。普通/幼稚散列查找是由两个变量构成的函数，其中一个变量是桶的数量。一致哈希的美妙之处在于，我们从方程中剔除了桶的数量“ n”。

在初始散列中，第一个变量是要存储在表中的对象的键。我们把钥匙叫做“ X”。第二个变量是桶的数量，“ n”。因此，要确定对象存储在哪个桶/机器中，必须计算: hash (x) mod (n)。因此，当您更改存储桶的数量时，也会更改存储几乎所有对象的地址。

把这个和一致哈希比较一下。让我们将“ R”定义为散列函数的范围。R 是某个常数。在一致哈希中，对象的地址位于 hash (x)/R。由于我们的查找不再是桶数量的函数，所以当我们更改桶数时，我们的重新映射就会减少。

Http://michaelnielsen.org/blog/consistent-hashing/

DHT 的核心是一个散列表。键-值对存储在 DHT 中，可以用键查找值。键是值的唯一标识符，这些值可以从块链中的块到地址和文档。

DHT 与普通散列表的不同之处在于，DHT 上的存储和查找分布在多个(可能是数百万)节点或计算机上。DHT 的这一特性使它看起来像是用于存储和检索的分布式数据库。参与节点之间没有主从层次结构或集中控制。所有节点都被视为对等节点。