使用质数表示哈希表的大小 [英] Using a prime number for the size of a HashTable

问题描述

我一直在阅读关于HashTables的教科书，它说在重新散列它时使用一个素数来表示数组的大小，但是它没有解释为什么。我也用谷歌搜索了一下，我找到的最好的答案是"出于技术原因"，为什么哈希表的大小应该使用质数？

推荐答案

取决于哈希函数。具体地说，为散列表大小选择素数可以弥补所使用的散列函数很差的事实，并且经常返回在执行期间自然出现的值的同余散列。哈希表大小的质数提高了哈希函数可能具有的任何"周期"相对于哈希表的大小是相对质数的可能性。

如果使用优秀的散列函数，例如加密散列函数，则可以使用任意大小的散列表，无需担心。2的幂很便宜，因为除法变成了位掩码。

这篇关于使用质数表示哈希表的大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！