数组大小为可伸缩散列

如果我想使用可扩展散列到最高的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

回答