我正在编写一个能够解决单词谜题的程序。本质上，我通过 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 类，而是我需要编写自己的类。这是一个练习。
最佳答案
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 - 避免退化溢出特性，并且由于良好的裸机实现。
(针对存储桶计数的模不是哈希函数的一部分。)
关于java - 我的哈希表应该使用什么大小的存储桶？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22872456/