java - 我的哈希表应该使用什么大小的存储桶？

Question

我正在编写一个能够解决单词谜题的程序。本质上，我通过 Infile.txt 获取字典并用它创建哈希表。我将使用单独的链接，并将 java LinkedList 类作为哈希表的第二层(使用一个指向链接列表的简单数组)。请随意提出更好的解决方案，因为我是一名数据结构新手。获取字典后，我将根据内文件中的困惑字符串列表在哈希表中搜索单词。我现在并不担心搜索。

字典的大小为109530。这是输入数据的恒定大小。您认为哈希表的最佳大小是多少？我读过有关此问题的相互矛盾的内容，所以我想我应该在这里问，所以请解释一下你的推理。

最后，我将使用以下函数作为哈希函数:

Hash(string) = ( SumOf(AsciiValOfChar() * CharPosInString()) ) mod TableSize;

示例:字符串“abc”将为97('a'的ascii值)* 1 + 98 * 2 + 99 * 3 mod tablesize。因此，如果表大小为 10 "abc"将 = 0 = 590 mod 0。

关于这个哈希函数有什么想法吗？

非常感谢大家，非常感谢您的宝贵时间。

编辑:我没有使用 Java hastable/hashmap 类，而是我需要编写自己的类。这是一个练习。

Answer 1

tldr; 1) 使用 >= 109530 * 1.33 作为最终容量，2) 哈希函数“将起作用”，即使不理想

<小时/>

存储桶计数选择取决于特定的 hash table implementation使用、数据和哈希函数质量。

由于影响因素有很多，我的建议是简单地编写哈希表，以便它可以适本地重新增长/调整大小。只需提供配置选项来控制初始容量、填充因子 ( 0.75 is a good start ) 和增长因子(加倍是一个好的开始)。在运行一些测试后，可以对哈希表进行简单的调整。

使用桶大小的二的幂有效地导致余数运算“减少为屏蔽[并且可能]增加不良散列函数的问题”，这就是为什么有时建议不要这样做。然而，关键字是“糟糕的哈希函数”，一些实现require a power of two and use an internal hash to mitigate this situation 。由于这是一个简单的实现，只需选择足够大小的奇数，例如二减一的幂。

就哈希函数本身而言，有几个目标，例如 providing uniform distribution并避免聚集。然而，建议的哈希并不能很好地做到这一点，特别是对于小或相似的字符串。这样的散列仍然有效 - 即使它比更好的对应物导致更多的冲突/聚类。

相反，请考虑 Java 的 String.hashCode ，它使用一个复合乘数，因为它应用于先前的哈希值。 ( The .NET version is more complicated ，但使用了类似的复合/运行哈希值的想法。)

for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
}

乘数 31 并不是唯一的“好”值，但它是 chosen carefully - 避免退化溢出特性，并且由于良好的裸机实现。

(针对存储桶计数的模不是哈希函数的一部分。)