3

在Kademlia 协议中，节点 ID 是 160 位数字。节点存储在桶中，桶 0 存储除最后一位之外与该节点具有相同 ID 的所有节点，桶 1 存储除最后 2 位之外与该节点具有相同 ID 的所有节点，以此类推为所有 160 个存储桶打开。

找到我应该将新节点放入哪个存储桶的最快方法是什么？

我将存储桶简单地存储在一个数组中，并且需要这样的方法：

Bucket[] buckets; //array with 160 items

public Bucket GetBucket(Int160 myId, Int160 otherId)
{
    //some stuff goes here
}

显而易见的方法是从最重要的位开始，逐位比较，直到找到不同之处，我希望有一个基于聪明位旋转的更好方法。

实用说明：我的 Int160 存储在一个包含 20 个项目的字节数组中，优先考虑适用于这种结构的解决方案。

4

2 回答 2

3

你愿意考虑一个由 5 个 32 位整数组成的数组吗？（或 3 个 64 位整数）？使用整个单词可能会比使用字节提供更好的性能，但该方法在任何情况下都应该有效。

XOR 两个节点 ID 的相应单词，从最重要的开始。如果 XOR 结果为零，则转到下一个最重要的字。

否则，使用Hacker's Delight 中的恒定时间方法找到此 XOR 结果中设置的最高有效位。. 如果设置了最高有效位，则该算法产生 32 (64)，如果设置了最低有效位，则结果为 1，依此类推。这个索引，结合当前单词的索引，会告诉你哪个位不同。

于 2010-04-17T00:31:29.763 回答
2

对于初学者，您可以逐字节（或逐字）进行比较，当您在该字节（或单词）中发现差异时，搜索第一位差异。

在我看来，将节点添加到存储桶数组的速度如此之快，以至于您是否巧妙地进行位旋转以找到字节（或单词）中的第一个差异，或者只是在循环中搅动，这对我来说似乎有点难以置信最多 CHAR_BIT （或其他东西）。不过有可能。

此外，如果 ID 本质上是均匀分布的随机，那么您会在大约 255/256 的时间发现前 8 位的差异。如果您关心的只是一般情况下的行为，而不是最坏情况下的行为，那么就做一件愚蠢的事情：您的循环不太可能长时间运行。

x不过，作为参考，数字和之间差异y的第一位是 中设置的第一位x ^ y。如果您正在使用 GNU C 进行编程，那__builtin_clz可能是您的朋友。或者可能__builtin_ctz，我有点困...

不过，您的代码看起来像 Java，所以我猜您正在寻找的 bitfoo 是integer log。

于 2010-04-17T00:17:35.967 回答