在 Kadmelia K-Bucket 算法中路由 Table，而不循环遍历节点 ID 中的每一位

Question

上下文

我正在尝试实施 Kadmelia 的 K-Bucket 算法来跟踪更近的节点。我在理论上理解算法的工作原理

当新节点added
如果桶大小没有超过 k（桶大小）我们将它添加到当前桶
否则我们拆分桶并通过遍历每个位来划分父桶中的联系人并将它们分成两个桶。
这也意味着对于给定的节点，将有 k * 8 个桶（或列表）

问题

问题参考了本例中采用的方法http://blog.notdot.net/2009/11/Implementing-a-DHT-in-Go-part-1

鉴于我们已将节点定义为长度为 20 的字节数组



const IdLength = 20
type NodeID [IdLength]byte

我正在尝试了解 PrefixLen 函数实际计算前缀和填充路由的作用 table。我了解该方法的每个组成部分的作用。我的意思是，我了解位移运算符的作用，并使用 AND 和 1 检查该位是否已设置。

我不明白的是 return 值以及为什么要这样设置。



func (node NodeID) PrefixLen() (ret int) {
  for i := 0; i < IdLength; i++ {
    for j := 0; j < 8; j++ {
      if (node[i] >> uint8(7 - j)) & 0x1 != 0 {
        return i * 8 + j;
      }
    }
  }
  return IdLength * 8 - 1;
}
</pre>

如何将return值suitable用作路由table的索引？


  ...
  prefix_length := contact.id.Xor(table.node.id).PrefixLen();
  bucket := table.buckets[prefix_length];
  ...
</pre>

这种方法与遍历每个位有何相同之处？作者如何使用PrefixLen方法达到相同的结果。

你能用例子帮助我理解这一点吗？提前致谢。

Answer 1

How is this approach identical to looping over each bit?

循环简单地遍历字节，然后对每个字节遍历位进行移位和掩码。所以实际上它确实遍历了所有位，这些位恰好被打包成字节，因为最小的可寻址内存单元通常是一个字节。

What I fail to understand is the return values and why they're set in that way.

它只是根据 i 完整字节和最后部分字节中的 j 位来计算位位置。

Context

这里的上下文实际上被误导了，因为您试图在查看具有固定数组布局的代码示例的同时解释 splittable 路由 table 设计。 .

在 Kadmelia K-Bucket 算法中路由 Table，而不循环遍历节点 ID 中的每一位

Routing Table in Kadmelia K-Bucket algorithm without looping over each bit in the Node ID

bit-manipulation

dht

go

kademlia