關於散列表中的輔助羣集

Question

儘管二次探測消除了主羣集，但散列到相同位置的元素 將探測相同的備用單元。 這被稱爲輔助羣集。仿真結果表明， 它通常會導致每個搜索少於一個額外的探測。

以上是來自Mark Allen Wessis書中算法書的文本片段。

我的問題可以通過例如有人解釋什麼是次要clustring又是什麼筆者通過「仿真結果表明，它通常會導致小於每搜索一個額外的探測器」的意思。

謝謝！

Answer 1

二次聚類的一段文字，你報的定義：不是插入點附近，探測器將周圍的其他點集羣。

「仿真結果表明，它通常會導致小於每搜索一個額外的探頭」是指有人試圖在二次探測哈希表中插入或找到大量的數據，結果發現，平均，不到兩年探測器需要在散列表中找到正確的位置。 （一個探測器當然是在散列表中插入或查找任何東西所需的最小數量。）

Answer 2

術語主要和次要集羣可能​​相當標準，因爲它們也在Knuth Vol 3的6.4節中。在這裏，他認爲在一個關鍵的哈希函數來獲得第一散列值h（K）和工作在什麼地方去，如果用h（K）建議在表中的槽充滿，然後不同的方式。問題是 - 當表格接近完整時會發生什麼情況，以致表格的某些部分已經滿了。

如果備用插槽依賴於一個完全獨立的函數g（K），那麼你會得到相當不錯的表現，沒有集羣，但你必須計算克（K）的成本。

如果備用槽是H（K）+ 1，對於某個i，這種情況發生的哈希表的再鄰接的部分獲得了大量的命中形成完全充滿上行槽中的相鄰區域中。事實上，附近的地區將分散並相互碰撞。 Knuth將此描述爲主聚類。

如果交替插槽是類似於h（K）+ i^2的東西，那麼您不會在附近區域發生碰撞以形成大型全部連續區域（主聚類），但您的行爲並不好如你用兩個完全分離的散列函數，因爲在這種情況下做，如果H（K1）= H（K2），則設定爲兩個鍵可能時隙是完全一致的，所以它們會彼此碰撞到某種程度。

如果你有興趣在散列的細節

PS，你可能想知道，有更多的近期工作，以及 - http://en.wikipedia.org/wiki/Cuckoo_hashing