數組大小爲可伸縮散列

如果我想使用可擴展散列到最高的100條記錄存儲，那麼什麼是我需要的最小數組的大小？數組大小爲可伸縮散列

我猜測的100數組就足夠了，但我可能是錯的。我也懷疑我可以使用更小的陣列。

我忘了補充一點，桶大小爲4，這很重要。 – neuromancer 2010-05-23 02:22:39

你認爲如何使用小於100的數組來存儲100條不同的記錄？ – Stephen 2010-05-23 02:26:07

每個數組入口指向一個存儲桶。桶大小爲4，意味着最多4個記錄可以放入桶中。所以一個數組入口可以指向4條記錄。 – neuromancer 2010-05-23 02:29:25

你對散列函數有什麼瞭解？

你提到了可擴展哈希。
通過可擴展散列，您可以將散列看作位串，並且通常通過一個trie實現存儲桶查找。雖然我假設你將它轉換爲數組中的索引，但不是基於特里查找。

你提到你最多隻有100個元素。如果你想要所有不同的哈希值，你會有128個可能性，因爲這是7位最接近的位組合。

如果您的哈希函數可以散列每個元素以擁有7個（或更多）不同的位中的7個，那麼您將擁有最優解決方案，並且存儲桶大小爲1個。請留下128個葉節點或128個數組。

如果散列函數可以散列每個元件具有6 7（或更多）不同的位，那麼你有爲2的桶大小你將不得不64葉節點/組合/數組大小。

如果散列函數可以散列每個元件具有的7（或更多）不同的位5，則你必須爲4的桶大小你將不得不32葉節點/組合/數組大小。

既然你說你想要一個桶大小爲4我認爲你的答案是32，你有一個很好的要求，你有一個很好的散列函數，可以給你至少5個不同的第一位。

2010-05-23 02:16:55

即使它是唯一鍵，那麼在除以100之後就會得到餘數。並且它可能不會總是唯一的。所以，我認爲很難確定哈希算法會給你相對於數組的唯一索引:) – vodkhang 2010-05-23 02:21:47

@vodkhang：完全有可能具有1：1和跨越映射。 – 2010-05-23 02:24:46

我錯過了這一點：完全改變答案的可擴展哈希。我重新寫了我的答案。 – 2010-05-23 02:38:17

我認爲這取決於你是否需要很高的性能或節省存儲。你可以將元素保存爲100個數組。我對擴展哈希不太瞭解，但是我對哈希的一般理解是它會有某種碰撞，如果你使用一個更大的數組來存儲它，碰撞次數可以減少，增加/刪除和查詢的性能也會更快。我想你應該至少使用128（正好是2^K，我不是在哈希專家）:)

2010-05-23 02:19:52 vodkhang

回答