找到正确的 kademlia 存储桶的最简单方法
在 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 个项目的字节数组中，与这种结构配合良好的解决方案将是首选。
In the Kademlia protocol node IDs are 160 bit numbers. Nodes are stored in buckets, bucket 0 stores all the nodes which have the same ID as this node except for the very last bit, bucket 1 stores all the nodes which have the same ID as this node except for the last 2 bits, and so on for all 160 buckets.
What's the fastest way to find which bucket I should put a new node into?
I have my buckets simply stored in an array, and need a method like so:
Bucket[] buckets; //array with 160 items
public Bucket GetBucket(Int160 myId, Int160 otherId)
{
//some stuff goes here
}
The obvious approach is to work down from the most significant bit, comparing bit by bit until I find a difference, I'm hoping there is a better approach based around clever bit twiddling.
Practical note:
My Int160 is stored in a byte array with 20 items, solutions which work well with that kind of structure will be preferred.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您愿意考虑 5 个 32 位整数的数组吗？ （或 3 个 64 位整数）？使用整个单词可能会比使用字节提供更好的性能，但该方法在任何情况下都应该有效。
从最高有效位开始，对两个节点 ID 的相应字进行异或。如果 XOR 结果为零，则转到下一个最高有效字。
否则，使用 来自 Hacker's Delight 的恒定时间方法。。如果设置了最高有效位，则该算法结果为 32 (64)，如果设置了最低有效位，则该算法结果为 1，依此类推。该索引与当前单词的索引相结合，将告诉您哪一位不同。
Would you be willing to consider an array of 5 32-bit integers? (or 3 64-bit integers)? Working with whole words may give you better performance than working with bytes, but the method should work in any case.
XOR the corresponding words of the two node IDs, starting with the most significant. If the XOR result is zero, move on to the next most significant word.
Otherwise, find the most significant bit that is set in this XOR result using the constant time method from Hacker's Delight.. This algorithm results in 32 (64) if the most significant bit is set, and 1 if the least significant bit is set, and so on. This index, combined with the index of the current word, will will tell you which bit is different.
对于初学者，您可以逐字节（或逐字）进行比较，当您在该字节（或字）中发现差异时，搜索第一个差异位。
在我看来，将节点添加到存储桶数组中的速度是如此之快，以至于无论您是否进行巧妙的位调整以找到字节（或字）内的第一个差异，或者只是在循环中搅动，这都非常重要，这似乎有点难以置信最多 CHAR_BIT（或其他）。不过有可能。
另外，如果 ID 本质上是随机且均匀分布的，那么您将在大约 255/256 的时间内发现前 8 位存在差异。如果您关心的是平均情况行为，而不是最坏情况，那么就做愚蠢的事情：您的循环不太可能长时间运行。
不过，作为参考，数字
x和y之间的第一位差异是x ^ y中设置的第一位。如果您使用 GNU C 进行编程，__builtin_clz可能是您的朋友。或者可能是__builtin_ctz，我有点困了...不过，你的代码看起来像 Java，所以我猜你正在寻找的 bitfoo 是 整数日志。
For starters you could compare byte-by-byte (or word-by-word), and when you find a difference search within that byte (or word) for the first bit of difference.
It seems vaguely implausible to me that adding a node to an array of buckets will be so fast that it matters whether you do clever bit-twiddling to find the first bit of difference within a byte (or word), or just churn in a loop up to CHAR_BIT (or something). Possible, though.
Also, if IDs are essentially random with uniform distribution, then you will find a difference in the first 8 bits about 255/256 of the time. If all you care about is average-case behaviour, not worst-case, then just do the stupid thing: it's very unlikely that your loop will run for long.
For reference, though, the first bit of difference between numbers
xandyis the first bit set inx ^ y. If you were programming in GNU C,__builtin_clzmight be your friend. Or possibly__builtin_ctz, I'm kind of sleepy...Your code looks like Java, though, so I guess the bitfoo you're looking for is integer log.