假设我有200.000个单词,并且我将使用hash * 33 word [i]作为哈希函数,应该是用于优化的表的大小,以获得最小的内存/分页问题？
使用平台 – C(c99版),
单词是英文字符,ASCII值
一次初始化哈希表(链表样式的桶),
碰撞后,该单词将作为新节点添加到存储桶中.
解决方法
一个好的经验法则是将负载系数保持在75％或更低(有些人会说70％)以维持(非常接近)O(1)查找.假设你有一个很好的哈希函数.
基于此,您需要至少约266,700个桶(75％)或285,700个桶(70％).这假设没有碰撞.
也就是说,您最好的选择是使用各种哈希表大小的一些示例数据运行测试,并查看您获得的冲突数.
你也可以考虑一个比hash * 33 word [i]更好的哈希函数. Jenkins hash及其变体需要更多的计算,但它们提供了更好的分布,因此通常会减少冲突并缩小所需的表大小.
你也可以在这个问题上抛出记忆.表大小为500,000可以为您提供40％的最小加载因子,这可以弥补您的哈希函数的缺点.但是,你很快就会达到收益递减的程度.也就是说,使表格大小为100万,可以给出20％的理论载荷因子,但几乎可以肯定的是,你实际上并没有意识到这一点.
长话短说：使用更好的哈希函数并在不同的表格大小上进行一些测试.
有一个东西,如minimal perfect hash.如果你知道你的输入数据是什么(即,它没有改变),那么你可以创建一个保证O(1)查找的哈希函数.它也非常节省空间.但是,我不知道为200,000个项目创建最小完美哈希是多么困难.
