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