哈希表斗阵

如果我有50 000个，并有发言权，10个可用的哈希表。如果不使用LinkedLists以便数组永远不会溢出，那么为每个索引选择适当的桶数组大小的最佳方式是什么？多余的30％是否合适？哈希表斗阵

2011-05-10 Markus O

一个就够了我想，最好的也 – 2011-05-10 10:28:05

一些语言支持阵列（无需声明数组的大小）动态大小。数据决定动态数组的大小。并且需要大小的语言也支持动态数组。

2011-05-10 10:27:59 Ishu

我不知道你在哪里得到的“大多是”从。当然，在我使用的语言（Java，C＃，C，C++）中，数组在创建后的大小是固定的。当一种语言支持通常涉及复制的“动态大小调整”时，所以仍然值得尝试获得适当的大小。 – 2011-05-10 10:30:13

在obj-c数组是动态的，我也使用java，c＃，c和C++，但没有使用动态数组的概念，但我想我读了大学水平的c和C++。当然，我在obj-c工作，这就是为什么我给了这种类型的答案。我已经从你的书看到C＃，所以我不能说别的任何事情，所以我要删除主要单词。 – Ishu 2011-05-10 10:43:59

肯定更好:) – 2011-05-10 10:51:01

如果您使用的是固定大小的数组为你的水桶，再有就是小于50,000没有桶的大小，可以保证永远不会溢出，除非你对键在50000分布的附加信息（例如，如果你知道他们是整数1 ... 50,000，那么它将是微不足道的）。

但一般你不希望依靠大水桶，因为这是O（n）搜索桶。相反，使用可变大小的表和可变大小的桶是更好的主意。桶可以简单地是数组，每次填满时您的大小就会增加一倍。类似地，哈希表的大小每增加90％就可以加倍。这是一种标准类型的方法。由以前的海报提到

为，无论是通过数组或链表列表的大多数实现你当列表已满自动重新分配存储。

来源

2011-05-10 10:35:38

如果您知道密钥先验，您可以计算minimal perfect hash。因此，如果你知道密钥并且可以定制哈希函数，那么一个桶的大小就足够了。

如果您事先不知道密钥 - 或者知道密钥，但不能改变哈希函数 - 那么攻击者可以选择最差情况下的一组密钥（即密钥所有哈希到同一个桶）。为了保证桶不溢出，你需要一个桶大小等于桶的数量。如果您愿意容忍溢出的机会，则可以进行更复杂的分析来选择涵盖大多数情况的桶大小。

来源

2011-09-27 02:08:52

回答

相关问题