代码之家 › 专栏 › 技术社区 › Martin

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

bitfoo dht bit-manipulation language-agnostic

Martin · 技术社区 · 15 年前

在 Kademlia protocol 节点ID是160位数字。节点存储在bucket中,bucket 0存储除最后一位外与该节点具有相同id的所有节点,bucket 1存储除最后2位外与该节点具有相同id的所有节点,依此类推,存储所有160个bucket。

找到应该将新节点放入哪个bucket的最快方法是什么?

我的bucket只是存储在一个数组中,需要这样的方法:

Bucket[] buckets; //array with 160 items

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

最明显的方法是从最重要的一点开始,一点一点地比较,直到我发现不同,我希望有一个更好的方法,基于聪明的一点旋转。

实用说明: 我的int160存储在一个有20个项的字节数组中,最好使用这种结构的解决方案。

2 回复 | 直到 12 年前

Community CDub 8 年前

您愿意考虑一个由5个32位整数组成的数组吗?(或3个64位整数)?使用整词可能比使用字节更好,但无论如何,该方法都应该有效。

异或两个节点id的对应字,从最重要的开始。如果异或结果为零,则转到下一个最有意义的单词。

否则,使用 constant time method from Hacker's Delight. . 如果设置了最高有效位,则该算法将产生32(64)个结果;如果设置了最低有效位,则产生1个结果,依此类推。这个索引,结合当前单词的索引,将告诉您哪个位不同。

Steve Jessop 15 年前

首先,您可以逐字节(或逐字)进行比较,当您在该字节(或逐字)内找到差异时,就可以搜索第一个差异位。

对我来说,向存储桶数组中添加一个节点的速度如此之快,以至于无论您是通过巧妙的比特旋转来查找一个字节(或单词)内的第一个差异位,还是仅仅在循环中搅动到char_位(或其他什么),都显得有些不可思议。不过,有可能。

另外,如果id本质上是随机的,分布是均匀的,那么您会发现前8位的差异大约是255/256。如果你只关心一般的案例行为,而不是最坏的案例,那么就做愚蠢的事情:你的循环不太可能运行很长时间。

不过,作为参考,数字之间的第一位差异 x 和 y 第一位是 x ^ y . 如果你用GNUC编程, __builtin_clz 可能是你的朋友。或者可能 __builtin_ctz ,我有点困…

但是,您的代码看起来像Java,所以我猜您正在寻找的BITFoO是 integer log .