一千萬個為什麽

搜索

最簡單的方法來找到正確的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
}

顯而易見的方法是從最重要的位開始,逐位比較,直到找到差異,我希望有一個更好的方法,基於聰明的位twiddling。

實用說明: 我的Int160存儲在一個包含20個項目的字節數組中,首選的解決方案適用於這種結構。

最佳答案

你願意考慮5個32位整數的數組嗎? (或3個64位整數)?使用整個單詞可能會比使用字節更好地提供性能,但該方法在任何情況下都應該起作用。

XOR兩個節點ID的相應單詞,從最重要的開始。如果XOR結果為零,則轉到下一個最重要的單詞。

否則,使用來自Hacker's Delight的恒定時間方法。。如果設置了最高有效位,則該算法產生32(64),如果設置最低有效位,則該算法產生1,依此類推。該索引與當前單詞的索引相結合,將告訴您哪個位不同。

轉載註明原文: 最簡單的方法來找到正確的kademlia桶