maa*_*ank 13 .net algorithm primes computer-science data-structures
根据这个问题,.Net字典将其分配的空间大小调整为至少是当前大小两倍的素数.为什么使用素数而不仅仅是当前大小的两倍是很重要的？(我试图用我的google-fu功能找到答案,但无济于事)
Cod*_*aos 16
放置元素的桶由下式确定(hash & 0x7FFFFFF) % capacity.这需要均匀分布.由此得出,如果多个条目是某个基数(hash1 = x1 * base,hash2 = x2 * base...)的倍数,其中base并且capacity不是互质(最大公约数> 1),则过度使用某些时隙,并且从不使用某些时隙.由于素数与除自身之外的任何数字都是互质的,因此它们具有相对较好的实现良好分布的机会.
一个特别好的属性是,capacity > 30每个位对哈希码的贡献是不同的.因此,如果散列的变化仅集中在几位中,那么它仍将导致良好的分布.这解释了为什么两个幂的容量都很差:它们掩盖了高位.只有高位不同的一组数字并非不太可能.
我个人认为他们选择的功能很糟糕.它包含一个昂贵的模运算,如果条目是素数容量的倍数,它的性能就会崩溃.但对大多数应用来说似乎已经足够了.