关于hash表的一个有关问题
关于hash表的一个问题
一般算法教材中都会提到hash表的大小应该选择素数
这是为什么捏？
如果关键字完全是平均分布的，是不是素数没什么区别吧？
------解决方案--------------------
如果完全平均分布的确不需要的，但是确定会这样嘛
------解决方案--------------------
素数冲突更少,平均分布就无所谓了
------解决方案--------------------
的确，hash表关键在key的平均分布，冲突越多hash表效率越低。至于大小的选择主要两个参考因素：hash表最终所存储元素的数量和key分布。其目的是尽量提高效率降低存储浪费。同时还要考虑hash函数本身的效率。
我曾经做个一个试验，大数据量的url查找。在10万数量级以内的时候体现不出来hash查找的性能，还不如二分查找来的快呢。
曾经看过网上一片帖子转述了一个暴雪曾经用过的双路hash函数，说是冲突率极低，不过测试过以后发现这个hash函数本身效率就不高了。
------解决方案--------------------
平均分布固然最好。但是不能拿最好情况来衡量哈希函数的效率。
根据具体情况设计哈希函数，才能使哈希函数高效。
线性同余法[也就是：f(x)=(a*x+b) mod m]，应该是比较好的通用哈希方法。
至于哈希表的大小为什么是素数就比较好，有理论解释，但更多的是试验证明。
《计算机程序设计艺术》中也只是给了总结性的理论解释，也没有什么详细讨论。
况且，对于通用哈希函数，理论解释也不一定可靠。
比如，理论上认为：二阶同余法[也就是：f(x)=(a*x*x+b*x+c) mod m] 比线性同余法更随机，应当是更好的哈希函数。但大量实践却显示：线性同余法的表现要优于二阶同余法。
------解决方案--------------------
若关键字完全是平均分布的，用素数还是合数效果差别不大。
一般算法教材中都会提到hash表的大小应该选择素数
这是为什么捏？
如果关键字完全是平均分布的，是不是素数没什么区别吧？
------解决方案--------------------
如果完全平均分布的确不需要的，但是确定会这样嘛
------解决方案--------------------
素数冲突更少,平均分布就无所谓了
------解决方案--------------------
的确，hash表关键在key的平均分布，冲突越多hash表效率越低。至于大小的选择主要两个参考因素：hash表最终所存储元素的数量和key分布。其目的是尽量提高效率降低存储浪费。同时还要考虑hash函数本身的效率。
我曾经做个一个试验，大数据量的url查找。在10万数量级以内的时候体现不出来hash查找的性能，还不如二分查找来的快呢。
曾经看过网上一片帖子转述了一个暴雪曾经用过的双路hash函数，说是冲突率极低，不过测试过以后发现这个hash函数本身效率就不高了。
------解决方案--------------------
平均分布固然最好。但是不能拿最好情况来衡量哈希函数的效率。
根据具体情况设计哈希函数，才能使哈希函数高效。
线性同余法[也就是：f(x)=(a*x+b) mod m]，应该是比较好的通用哈希方法。
至于哈希表的大小为什么是素数就比较好，有理论解释，但更多的是试验证明。
《计算机程序设计艺术》中也只是给了总结性的理论解释，也没有什么详细讨论。
况且，对于通用哈希函数，理论解释也不一定可靠。
比如，理论上认为：二阶同余法[也就是：f(x)=(a*x*x+b*x+c) mod m] 比线性同余法更随机，应当是更好的哈希函数。但大量实践却显示：线性同余法的表现要优于二阶同余法。
------解决方案--------------------
若关键字完全是平均分布的，用素数还是合数效果差别不大。