`

hashcode中选择31因子的原因

阅读更多

源自<<effective java 2nd>> Item9

 

The value 31 was chosen because it is
an odd prime. If it were even and the multiplication overflowed, information
would be lost, as multiplication by 2 is equivalent to shifting. The advantage of
using a prime is less clear, but it is traditional. A nice property of 31 is that the
multiplication can be replaced by a shift and a subtraction for better performance:
31 * i == (i < < 5) - i. Modern VMs do this sort of optimization automatically.

主要是关于 result = 31 * result + c 这个式子中为什么用31,他说31是奇数,不是偶数,如果是偶数且乘法造成溢出的话,信息就会丢失,因为乘以2就相当于移位,那我就有个疑惑了,乘31就 不会造成信息丢失了?乘2是移位,乘31的过程其实也是包含移位的

 

MT502回答说:乘31和2都会溢出造成信息丢失,但是乘2更容易导致低位都变成0从而导致hashcode一样的概率变大

 

我认为乘31也没有理由不造成溢出,看来原文描述确实有些语病。

 

选择31这个质数,至少是有意让hash值最大程度散布,降低碰撞可能~

 

For what it's worth, Effective Java 2nd Edition hand-waives around the mathematics issue and just say that the reason to choose 31 is:

  * Because it's an odd prime, and it's "traditional" to use primes
  * It's also one less than a power of two, which permits for bitwise optimization

Here's the full quote, from Item 9: Always override hashCode when you override equals:

  The value 31 was chosen because it's an odd prime. If it were even and multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional.

  A nice property of 31 is that the multiplication can be replaced by a shift (§15.19) and subtraction for better performance:

  31 * i == (i << 5) - i

  Modern VMs do this sort of optimization automatically.

  While the recipe in this item yields reasonably good hash functions, it does not yield state-of-the-art hash functions, nor do Java platform libraries provide such hash functions as of release 1.6. Writing such hash functions is a research topic, best left to mathematicians and theoretical computer scientists.

  Perhaps a later release of the platform will provide state-of-the-art hash functions for its classes and utility methods to allow average programmers to construct such hash functions. In the meantime, the techniques described in this item should be adequate for most applications.

Rather simplistically, it can be said that using a multiplier with numerous divisors will result in more hash collisions. Since for effective hashing we want to minimize the number of collisions, we try to use a multiplier that has fewer divisors. A prime number by definition has exactly two distinct, positive divisors.

 

http://stackoverflow.com/questions/3613102/why-use-a-prime-number-in-hashcode

 

其它相关信息stackoverflow上也有不少,如:

http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier

分享到:
评论

相关推荐

    定义hashcode时使用31系数的原因

    定义hashcode时使用31系数的原因 Hashcode是一个非常重要的概念在Java编程中,它是用于唯一标识对象的整数值。特别是在使用HashMap、HashSet等集合类时,hashcode的正确实现是非常重要的。本文将详细介绍为什么在...

    各种hash算法-hashcodeUtil

    3. **扰动函数**:在计算过程中加入扰动因子,进一步打乱哈希码的分布,降低碰撞概率。 4. **避免零值**:处理字段为零的情况,因为零可能导致较差的哈希码分布。 了解了`hashCodeUtil`的基本原理后,我们可以将其...

    源码解析jdk7.0集合:HashSet的底层实现原理.pdf

    加载因子是衡量HashMap满的程度,当HashMap中的元素数量达到初始容量和加载因子的乘积时,HashMap会进行扩容,将容量扩大为原来的两倍。加载因子越大,HashMap填满的几率就越大,但空间利用效率就越高;加载因子越小...

    阿里面试官必问21个刁钻的HashMap面试题,这次让你彻底搞懂.docx

    4. **重写hashCode和equals方法的原因** 为了确保键的唯一性,需要重写这两个方法,使具有相同意义的对象能正确地映射到相同的哈希值,并且equals方法可以确认两个对象是否相等。 5. **hash函数的实现** JDK1.8中,...

    hashmap实现原理

    哈希映射(HashMap)是Java编程语言中广泛使用的数据结构之一,主要提供键值对的存储和查找功能。...在实际编程中,应充分考虑哈希冲突的处理、负载因子的选择以及预估容量的设定,以提高HashMap的使用效率。

    2021最新版数据结构与算法面试题手册 1.pdf

    而加载因子决定了HashMap何时扩容,即当HashMap中的条目数超过了加载因子与当前容量的乘积时,HashMap会进行rehash操作,通常默认加载因子是0.75。 4. **一致性哈希算法**:一致性哈希算法通过构造一个长度为2^32的...

    Java中HashMap详解(通俗易懂).doc

    - 选择合适的初始容量(initialCapacity)和负载因子,以优化HashMap的性能。初始容量越大,扩容次数越少,但内存占用也会增加。 - 注意HashMap的并发问题,如果在多线程环境下,使用Collections.synchronizedMap()...

    阿里云、蚂蚁最新Java面试题.pdf

    Java编程语言在软件开发领域占据着重要地位,特别是在大型企业如阿里云和蚂蚁集团中...在实际使用中,根据需求选择合适的数据结构,考虑线程安全问题,并了解其底层实现原理,可以帮助我们编写出更高效、更稳定的代码。

    补充资料(HashMap红黑树).rar

    - 哈希函数:HashMap使用键对象的hashCode()方法生成哈希值,再通过取模运算确定在数组中的位置。 - 链表与碰撞:当多个键的哈希值相同,它们会被链接到同一个数组槽位形成链表,解决哈希冲突。 - 负载因子:...

    hashmap_use_in_JDK7.zip

    2. **哈希函数**:HashMap通过键对象的`hashCode()`方法计算哈希值,然后使用`indexFor(int hash, int length)`方法确定元素在数组中的位置。这个过程是为了尽量使不同的键分散在数组的不同位置,减少哈希冲突。 3....

    源码解析jdk7.0集合(3):HashMap的底层实现原理.pdf

    - **容量和负载因子的选择**:容量和负载因子的大小直接影响HashMap的性能。过高的负载因子会导致链表过长,影响性能;过低则会造成空间的浪费。通常推荐使用默认值。 - **键的equals和hashCode方法**:由于HashMap...

    2022年Java中对HashMap的深度分析Java教程.docx

    在Java编程语言中,HashMap是Java集合框架的重要组成部分,它提供了高效的存储和检索对象的能力,实现了"键-值"对的映射。本教程将深入分析2022年Java中HashMap的内部机制、关键属性和操作。 HashMap的核心属性包括...

    Java面试题-哈希.docx

    在Java中,`HashMap`作为最常用的数据结构之一,其内部实现选择红黑树而非其他数据结构(如链表或AVL树)有着深刻的考虑。 **主要原因:** 1. **更快的搜索和插入速度:** - 红黑树是一种自平衡二叉搜索树,因此...

    哈希表学习笔记.docx

    - **定义**:负载因子是哈希表中已存在的元素数量与哈希桶数量的比值,即 \(\text{负载因子} = \frac{\text{元素数量}}{\text{哈希桶数量}}\)。 - **作用**:负载因子直接影响哈希表的冲突率。通常,当负载因子过...

    Java HashMap高难度面试题集锦解析Java HashMap面试题及答案解析-高难度

    5. **负载因子选择**: 0.75是一个折衷的选择,它在查找效率和内存使用之间取得平衡。较低的负载因子减少冲突,提高查找效率,但占用更多内存;较高的负载因子节省内存,但可能导致更多的冲突和查找时间。 6. **...

    阿里云Java实习生面试真题

    阿里云Java实习生面试真题涉及了Java集合框架中的一些核心概念,主要集中在HashSet、...在面试中,深入理解这些数据结构的内部工作原理以及如何根据需求选择合适的集合类型,将有助于展示你的专业技能和问题解决能力。

    Java_Datastructure.rar_java 哈希_java 哈希表

    在Java中,`hashCode()`方法就是用于计算对象的哈希值,通常在实现`equals()`方法时需要一起考虑。 哈希表,又称为散列表,是基于哈希函数实现的一种数据结构,它允许我们以近乎常数的时间复杂度进行插入、删除和...

    java面试 集合中知识点 HashMap(JDK1.8)源码+底层数据结构分析 整理.pdf

    - **get方法**:获取值时,同样根据key的hashCode()和hash()方法定位到数组的相应位置,然后在链表或红黑树中查找对应的键值对。 - **resize方法**:当HashMap需要扩容时,会创建一个新的更大的数组,并将旧数组中...

    HashMap底层原理

    HashMap是Java编程语言中最常用的集合类之一,它提供了一种基于键值对(key-value pair)的数据存储方式,允许我们快速...在设计和优化数据结构时,也应考虑到哈希冲突的处理和负载因子的选择,以达到最佳的运行效果。

Global site tag (gtag.js) - Google Analytics