如何选择哈希表的大小？

基于此,您需要至少约266,700个桶(75％)或285,700个桶(70％).这假设没有碰撞.

也就是说,您最好的选择是使用各种哈希表大小的一些示例数据运行测试,并查看您获得的冲突数.

你也可以考虑一个比hash * 33 word [i]更好的哈希函数. Jenkins hash及其变体需要更多的计算,但它们提供了更好的分布,因此通常会减少冲突并缩小所需的表大小.

你也可以在这个问题上抛出记忆.表大小为500,000可以为您提供40％的最小加载因子,这可以弥补您的哈希函数的缺点.但是,你很快就会达到收益递减的程度.也就是说,使表格大小为100万,可以给出20％的理论载荷因子,但几乎可以肯定的是,你实际上并没有意识到这一点.

长话短说：使用更好的哈希函数并在不同的表格大小上进行一些测试.

有一个东西,如minimal perfect hash.如果你知道你的输入数据是什么(即,它没有改变),那么你可以创建一个保证O(1)查找的哈希函数.它也非常节省空间.但是,我不知道为200,000个项目创建最小完美哈希是多么困难.