She*_*Pro 24 c# arrays primes hashcode
当我点击这段时,我正在阅读Eric Lippert 关于GetHashCode指南和规则的最新博客帖子:
我们在这里可能更聪明; 就像List在它满了时调整自身大小一样,bucket set也可以自行调整大小,以确保平均bucket长度保持低位.此外,由于技术原因,通常最好将存储桶设置长度设为素数,而不是100.我们可以对此哈希表进行大量改进.但是这个哈希表的简单实现的快速草图现在可以做到.我想保持简单.
所以看起来我错过了一些东西.为什么将它设置为素数是一个好习惯？
Dav*_*eas 17
您可以找到建议频谱两个相反端的人.另一方面,为哈希表的大小选择素数将减少冲突的可能性,即使哈希函数不太有效地分配结果.注意,如果(在最简单的例子中争论)确定2个大小的幂,则只有较低位影响桶,而对于素数,将使用散列结果中的大多数位.
另一方面,通过选择更好的散列函数,甚至通过应用一些位操作来重新散列散列函数的结果,并使用2散列大小的幂来加速计算,您可以获得更多.
作为现实生活中的一个例子,Java HashTable最初是通过使用素数(或接近素数)实现的,但是从Java 1.4开始,设计被改为使用两个桶的功率并添加了第二个快速哈希函数应用于初始哈希的结果.可以在这里找到一篇评论这种变化的有趣文章.
所以基本上:
即使在不太好的散列函数的情况下,素数也有助于将输入分散到不同的桶中.
通过对散列函数的结果进行后处理,并使用2大小的幂来加速模运算(位掩码)并补偿后处理,可以实现类似的效果.
Dar*_*rov 15
因为这会产生更好的散列函数并减少可能的冲突次数.选择良好的散列函数中对此进行了解释:
基本要求是函数应提供散列值的均匀分布.非均匀分布增加了碰撞次数和解决它们的成本.
对于应用程序中出现的表大小,分布需要是统一的.特别是,如果使用动态调整大小并使s精确加倍和减半,则只有当s是2的幂时,散列函数才需要是均匀的.另一方面,只有当s是素数时,一些散列算法才提供均匀的散列.
Dam*_*ver 10
假设您的铲斗组长度是2的幂 - 这使得mod计算非常快.这也意味着桶选择仅由m哈希码的顶部位确定.(其中m = 32 - n,n是使用2的幂).所以就像你立即丢弃哈希码的有用位一样.
或者像2006年的博客文章中所说:
假设你的hashCode函数导致以下hashCodes以及其他{x,2x,3x,4x,5x,6x ...},那么所有这些将集中在m个桶中,其中m = table_length/GreatestCommonFactor( table_length,x).(验证/得出这个是微不足道的).现在,您可以执行以下操作之一以避免群集:
...
或者通过使GreatestCommonFactor(table_length,x)等于1来简单地使m等于table_length,即通过使table_length与x进行互操作.如果x可以是任何数字,那么请确保table_length是素数.