language-agnostic - 找到正确的 kademlia 桶的最简单方法

Question

在Kademlia protocol节点 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 个项目的字节数组中，将优先使用适合这种结构的解决方案。

Answer 1

您愿意考虑一个包含 5 个 32 位整数的数组吗？ (或 3 个 64 位整数)？使用整个单词可能会比使用字节提供更好的性能，但该方法应该适用于任何情况。

异或两个节点 ID 的对应词，从最重要的开始。如果异或结果为零，则继续处理下一个最重要的字。

否则，使用 constant time method from Hacker's Delight. 找到在此异或结果中设置的最高有效位.如果设置了最高有效位，则该算法的结果为 32 (64)，如果设置了最低有效位，则为 1，依此类推。这个索引，结合当前单词的索引，会告诉你哪一位是不同的。