Object类中的hashcode方法

- 日理万妓 2023-02-22 07:57 3阅读 0赞

## 转自：[https://mp.weixin.qq.com/s/qjEEU7nWo3xJXLjo\_apjww][https_mp.weixin.qq.com_s_qjEEU7nWo3xJXLjo_apjww] ##

## 引言 ##

> 这两天有个学弟问过我这个问题：对象的 hashCode 到底是怎么实现的？  
> 在深挖之前，我可能只能说：如果没有被重载，代表的是对象的地址通过某种 hash 算法计算后在 hash 表中的位置。  
> 回答后，仔细一想，不对呀，这个 hash 值具体是怎么计算的，我终究还是没有答到点上，而是绕开话题，回答了含义。  
> 脑壳一热，忽然想起去年虐我的阿里面试题，hashCode 是怎么得到的呢？

## 一、问题定义 ##

hashCode 真的只是通过地址计算的吗？如果对象地址变化了，比如经历的 GC，hashCode 是不是也跟着变了呢？如果此时刚好在进行锁升级，对于 hashCode 的计算会有影响吗？多线程的情况下会不会生成一样的 hashCode 呢？具体通过什么样的 hash 算法得到的呢？相比之下，我真的是太皮毛了～

首先看下一个简单的实现类，这里先别使用 lombok 注解，原因后文会解释：

public class Student {
    
        private int no;
        private String name;
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public static void main(String[] args) {
            Student student1=new Student();
            student1.setName("张三");
            student1.setNo(12);
            System.out.println(student1.hashCode());
        }
    }

多次运行后，可以大胆假设 hashCode 的计算是稳定的。只要对象的引用不变，每次运行都是相同的结果，所以网上说使用随机数计算的回答，这个先打一个问号。..

大家可能印象比较深刻，当你打开源码时，会发现 native 修饰的方法会挡住你的去路。C++ 实现的方法难道就该让我们止步了吗？这次打算死磕到底。

## 二、源码揭秘 ##

2.1 Object.hashCode () 注释解读

简单归纳一下 JDK 团队的注释：

*  hashCode 表示对象在 hash 表中的位置，对于同一个对象来说，多次调用，返回相同的 hashCode。
 *  如果 Object.equal () 相等，Object.hashCode () 也必然相等。重写时也建议保证此特性。
 *  如果 Object.equal () 相等，这并不要求 Object.hashCode () 也返回不同值。如果真出现这种情况，最好优化代码，充分利用 hash 表的性能。

2.2 hashCode 生成源码

下面是 C++ 对应的实现，这里拷贝一下网上其他大佬发的 hashCode 实现核心源码：

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
      intptr_t value = 0 ;
      if (hashCode == 0) {
         // This form uses an unguarded global Park-Miller RNG,
         // so it's possible for two threads to race and generate the same RNG.
         // On MP system we'll have lots of RW access to a global, so the
         // mechanism induces lots of coherency traffic.
         value = os::random() ;
      } else
      if (hashCode == 1) {
         // This variation has the property of being stable (idempotent)
         // between STW operations.  This can be useful in some of the 1-0
         // synchronization schemes.
         intptr_t addrBits = intptr_t(obj) >> 3 ;
         value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
      } else
      if (hashCode == 2) {
         value = 1 ;            // for sensitivity testing
      } else
      if (hashCode == 3) {
         value = ++GVars.hcSequence ;
      } else
      if (hashCode == 4) {
         value = intptr_t(obj) ;
      } else {
         // Marsaglia's xor-shift scheme with thread-specific state
         // This is probably the best overall implementation -- we'll
         // likely make this the default in future releases.
         unsigned t = Self->_hashStateX ;
         t ^= (t << 11) ;
         Self->_hashStateX = Self->_hashStateY ;
         Self->_hashStateY = Self->_hashStateZ ;
         Self->_hashStateZ = Self->_hashStateW ;
         unsigned v = Self->_hashStateW ;
         v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
         Self->_hashStateW = v ;
         value = v ;
      }
     
      value &= markOopDesc::hash_mask;
      if (value == 0) value = 0xBAD ;
      assert (value != markOopDesc::no_hash, "invariant") ;
      TEVENT (hashCode: GENERATE) ;
      return value;
    }

源码中的 hashCode 其实就是 JVM 启动的一个参数，每一个分支对应一个生成策略。通过 -XX:hashCode，可以任意切换 hashCode 的生成策略。  
首先解释一下入参 oop obj 就是对象的逻辑地址。所以与地址相关的生成策略有两条，在 hashCode 等于 1 或 4 的时候。

*  hashCode==1：这种方式具有幂等的性质，在 STW（stop-the-world）操作中，这种策略通常用于同步方案中。利用对象地址计算，使用不经常更新的随机数参与运算。
 *  hashCode==4：与创建对象的内存位置有关，原样输出。

其他情况：

*  hashCode==0：简单地返回随机数，与对象的内存地址没有联系。然而根据随机数生成并全局地读写在多处理器下并不占优势。
 *  hashCode==2：始终返回完全相同的标识，即 hashCode=1。这可用于测试依赖对象标识的代码。
 *  hashcode==3：从零开始计算哈希代码值。它看起来不是线程安全的，因此多个线程可以生成具有相同哈希代码的对象。
 *  hashCode>=5（默认）：在 jdk1.8 中，这是默认的 hashCode 生成算法，支持多线程生成。使用了 Marsaglia 的 xor-shift 算法产生伪随机数。

可以知道，hashCode 为 5 就是我们程序调用时的默认策略。其他的几个分支我的理解也只能到这里，如果有大佬了解的更细，可以在评论指出。这里先不管 Marsaglia 大佬是谁，为什么是伪随机数呢？

关于真随机数的生成，这里可能要牵扯到随机数生成的物理知识。Intel810RNG 的原理大概是：利用热噪声 (是由导体中电子的热震动引起的) 放大后，影响一个由电压控制的振荡器，通过另一个高频振荡器来收集数据... ...

我们实际应用的基本上都是通过数学公式产生的伪随机数。严格意义上讲，伪随机数不是完全随机的，但是真随机生成比较困难，所以只要能通过一定的随机数统计检测，就可以当作真随机数来使用。

有点离题了，下面来谈谈这个 xor-shift 算法～

Marsaglia 的 xor-shift 策略，支持多线程执行的状态，这可能是最好的整体实现 ，这种方式生成随机数执行起来很快。简单来说，看起来就是一个移位寄存器，每次移入的位由寄存器中若干位取异或生成。每次新生成的位看起来是随机的。如果要深究，可能会扯很多数学公式，这里就不探讨了（毕竟数学太深奥了，菜是原罪）。

从维基百科上粘的基本实现：

uint32_t xor128(void) {
     static uint32_t x = 123456789;
     static uint32_t y = 362436069;
     static uint32_t z = 521288629;
     static uint32_t w = 88675123;
     uint32_t t;
    
     t = x ^ (x <<11);
     x = y; y = z; z = w;
     return w = w ^ (w>> 19) ^ (t ^ (t>> 8));
    }

这里面的入参还是需要好好打磨的，才能通过随机数的严苛测试～

拓展阅读：zhihu.com/question/2795  
论文地址：jstatsoft.org/v08/i14/p

2.3 从局部到全局

了解了 hashCode 是怎么产生的，再看看上层，获取前需要做哪些准备？具体代码比较长，就不贴出了，简单概括。

如果处于偏向锁状态，就需要先撤销偏向锁。然后确保当前线程执行路径不在 safe point 上，并且是 java 线程，未阻塞状态。读取稳定的对象头，防止对象继续锁升级，如果是，就需要等待升级完。等到对象状态稳定了，从对象头中取出 hash，如果不存在，则执行上文代码，计算 hashCode。如果对象处于轻量级锁状态，并且当前线程持有，就从 线程的栈里取对象头。当升级为重量级锁时，就执行上文代码，计算 hashCode。

因此，hashCode 只会被计算一遍，之后就存在对象头中。

拓展阅读：zhihu.com/question/2997

至此，jdk 原生 hashCode 的生成过程梳理完了。

## 三、String、Lombok 对 hashCode 的实现 ##

3.1 Lombok 实现 hashCode

如果把实体类换成 Lombok 实现，又会怎么样呢？

@Data
    public class Student {
    
        private int no;
    
        private String name;
    
        public static void main(String[] args) {
            Student student1=new Student();
            student1.setName("张三");
            student1.setNo(12);
            System.out.println(student1.hashCode());
            Map<Student,String> map=new HashMap<>();
            map.put(student1,"student1");
            student1.setName("111");
            System.out.println(student1.hashCode());
            System.out.println(map.get(student1));
        }
    }

输出：

779078
    52846
    null

可以神奇地看到，hashCode 明显被修改了，并且 hashMap 也取不到值，这是怎么回事？  
原来，Lombok 的 @Data 注解相当于 5 个注解：

*  @Getter
 *  @Setter
 *  @RequiredArgsConstructor
 *  @ToString
 *  @EqualsAndHashCode

相当于重写了 hashCode，只要属性发生变化，再次输出时，hashCode 就会不同。

如果将代码反编译后，不难发现。

public class Student {
        private int no;
        private String name;
    
        public int hashCode() {
            int PRIME = true;
            int result = 1;
            int result = result * 59 + this.getNo();
            Object $name = this.getName();
            result = result * 59 + ($name == null ? 43 : $name.hashCode());
            return result;
        }
    }

3.2 String 实现 hashCode

public int hashCode() {
            int h = hash;
            if (h == 0 && value.length > 0) {
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) {
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }

可以看出，相同的字符串调用 hashCode () 方法，得到的值是一样的，与内存地址、进程、机器无关。代码似乎很简单，但是一定要归纳出来他的实现过程。  
注：n 为字符串长度。

如果字符串相等，hashCode 必然一样；如果 hashCode 一样，字符串不一定相等，因为计算时可能发生溢出。

为什么计算时选择 31？

1.  31 是个奇质数，不大不小，一般质数非常适合 hash 计算，偶数相当于移位运算，容易溢出，数据信息丢失。如果太小，则产生的哈希值区间小；太大则容易溢出，数据信息丢失。
2.  31 \* i == (i << 5) - i。非常易于维护，将移位代替乘除，会有性能的提升，并且 JVM 执行时能够自动优化成这个样子。
3.  通过实验计算，选用 31 后出现 hash 冲的概率相比于其他数字要小。

拓展阅读：segmentfault.com/a/1190

## 最后 ##

底层源码还是很深奥的，知识都是互通的。最后物理，数学都融合在一起哈哈，还是很微妙的～

参考文章：

blog.csdn.net/weixin\_30  
zhihu.com/question/2997  
segmentfault.com/a/1190  
it1352.com/958039.html  
zhihu.com/question/2795

[https_mp.weixin.qq.com_s_qjEEU7nWo3xJXLjo_apjww]: https://mp.weixin.qq.com/s/qjEEU7nWo3xJXLjo_apjww