找到正確的kademlia桶的最簡單的方法

在Kademlia protocol節點ID是160位數字。節點存儲在桶中，桶0存儲與該節點具有相同ID的所有節點，除了最後一位之外，桶1存儲與該節點具有相同ID的除最後2位之外的所有節點，所以在所有160個桶上。找到正確的kademlia桶的最簡單的方法

什麼是最快的方法來找到哪個桶我應該把一個新的節點？

我有我的水桶簡單地存儲在陣列中，並且需要像這樣的方法：

Bucket[] buckets; //array with 160 items 

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

最明顯的方法是從最顯著位下工作，通過位比較位，直到我找到一個差異，我希望有一個更好的方法圍繞聰明的位置旋轉。

實用說明：我的Int160存儲在一個包含20個項目的字節數組中，這種結構的解決方案將會是首選。

來源

2010-04-16 Martin

你願意考慮一個由5個32位整數組成的數組嗎？（或3個64位整數）？使用整個單詞可能會比使用字節提供更好的性能，但該方法在任何情況下都可以工作。

XOR兩個節點ID的相應字，從最重要的開始。如果異或結果爲零，請繼續閱讀下一個最重要的單詞。

否則，使用constant time method from Hacker's Delight.找到在此異或結果中設置的最高有效位。如果設置了最高有效位，則該算法產生32（64），如果設置最低有效位則產生1，依此類推。該索引與當前單詞的索引相結合，會告訴你哪一位不同。

來源

2010-04-17 00:31:29 erickson

字節似乎是最自然的事情，正如你所說的，整數可能會更快 – Martin 2010-04-17 02:57:07

對於初學者，您可以逐字節（或逐字）比較，以及在第一位差異中發現該字節（或字）內的差異搜索。

對我來說，添加一個節點到一個桶陣列將會如此之快以至於不管你是否聰明地在一個字節（或單詞）中尋找差異的第一個位，在CHAR_BIT（或其他）中循環。雖然可能。另外，如果ID本質上是隨機的且均勻分佈，那麼你會發現在大約255/256的時間的前8位中存在差異。如果你關心的只是平均情況的行爲，而不是最壞的情況，那麼就幹這件愚蠢的事情吧：你的循環很可能不會長時間運行。

儘管如此，x和y之間的差異的第一位是在x^y中設置的第一位。如果你在GNU C編程，__builtin_clz可能是你的朋友。或者可能__builtin_ctz，我有點困...

雖然你的代碼看起來像Java，所以我猜你正在尋找的bitfoo是integer log。

來源

2010-04-17 00:17:35

C＃，接近java。正如你所說，這種算法的速度可能不重要，我主要是出於興趣問這個問題。有關位混亂的以前的問題已經提出了一些巧妙的技巧，這些技巧很有趣，揭示了它們的工作原理 – Martin 2010-04-17 02:52:03

找到正確的kademlia桶的最簡單的方法

回答

相關問題