为什么使用质数31?
这可以分为两部分吗?
在这里,我们需要了解我们的目标是为对象获取 HashCode,这将有助于我们在O(1)时间内找到该对象。
这里的关键词是 。
素数
质数是唯一数字。它们的独特之处在于,由于使用了素数来构成素数,因此素数与任何其他数字的乘积具有唯一性的最大可能性(不像素数本身那样唯一)。此属性在哈希函数中使用。
。
为什么是31号?
从 有效的Java
这是完整的报价,
从项目9:重写等于时,始终重写hashCode:
选择值31是因为它是奇数质数。如果是偶数且乘法溢出,则信息将丢失,因为乘以2等于移位。使用质数的优势尚不清楚,但这是传统的。
31的一个不错的特性是乘法可以用移位(第15.19节)和减法代替,以获得更好的性能:
31 * i ==(i << 5)-i现代VM自动执行这种优化。
尽管此项目中的配方产生了相当不错的哈希函数,但它没有产生最新的哈希函数,Java平台库也没有提供1.6版以上的哈希函数。编写这样的哈希函数是一个研究主题,数学家和理论计算机科学家最好去做。
也许该平台的更高版本将为其类和实用程序方法提供最新的哈希函数,以允许普通程序员构造此类哈希函数。同时,此项中描述的技术应适合大多数应用。