补补HashCode，毕竟菜乃原醉

大家好，我是沉默王二。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：空间域名、网络空间、营销软件、网站建设、孟连网站维护、网站推广。

假期结束了，需要快速切换到工作的状态投入到新的一天当中。放假的时候痛快地玩耍，上班的时候积极的工作，这应该是我们大多数“现代人”该有的生活状态。

我之所以费尽心思铺垫了前面这段话，就是想告诉大家，技术文虽迟但到，来吧，学起来~

今天我们来谈谈 Java 中的 hashCode() 方法。众所周知，Java 是一门面向对象的编程语言，所有的类都会默认继承自 Object 类，而 Object 的中文意思就是“对象”。

Object 类中就包含了 hashCode() 方法：

 
 
 
 
    
  
  
  
  
  1. @HotSpotIntrinsicCandidate
    2. 
  
  
  
  
  2. public native int hashCode();
    3.

意味着所有的类都会有一个 hashCode() 方法，该方法会返回一个 int 类型的值。由于 hashCode() 方法是一个本地方法(native 关键字修饰的方法，用 C/C++ 语言实现，由 Java 调用)，意味着 Object 类中并没有给出具体的实现。

具体的实现可以参考 jdk/src/hotspot/share/runtime/synchronizer.cpp(源码可以到 GitHub 上 OpenJDK 的仓库中下载)。get_next_hash() 方法会根据 hashCode 的取值来决定采用哪一种哈希值的生成策略。

并且 hashCode() 方法被 @HotSpotIntrinsicCandidate 注解修饰，说明它在 HotSpot 虚拟机中有一套高效的实现，基于 CPU 指令。

那大家有没有想过这样一个问题：为什么 Object 类需要一个 hashCode() 方法呢?

在 Java 中，hashCode() 方法的主要作用就是为了配合哈希表使用的。

哈希表(Hash Table)，也叫散列表，是一种可以通过关键码值(key-value)直接访问的数据结构，它最大的特点就是可以快速实现查找、插入和删除。其中用到的算法叫做哈希，就是把任意长度的输入，变换成固定长度的输出，该输出就是哈希值。像 MD5、SHA1 都用的是哈希算法。

像 Java 中的 HashSet、Hashtable(注意是小写的 t)、HashMap 都是基于哈希表的具体实现。其中的 HashMap 就是最典型的代表，不仅面试官经常问，工作中的使用频率也非常的高。

大家想一下，如果没有哈希表，但又需要这样一个数据结构，它里面存放的数据是不允许重复的，该怎么办呢?

要不使用 equals() 方法进行逐个比较?这种方案当然是可行的。但如果数据量特别特别大，采用 equals() 方法进行逐个对比的效率肯定很低很低，最好的解决方案就是哈希表。

拿 HashMap 来说吧。当我们要在它里面添加对象时，先调用这个对象的 hashCode() 方法，得到对应的哈希值，然后将哈希值和对象一起放到 HashMap 中。当我们要再添加一个新的对象时：

  • 获取对象的哈希值;
  • 和之前已经存在的哈希值进行比较，如果不相等，直接存进去;
  • 如果有相等的，再调用 equals() 方法进行对象之间的比较，如果相等，不存了;
  • 如果不等，说明哈希冲突了，增加一个链表，存放新的对象;
  • 如果链表的长度大于 8，转为红黑树来处理。

就这么一套下来，调用 equals() 方法的频率就大大降低了。也就是说，只要哈希算法足够的高效，把发生哈希冲突的频率降到最低，哈希表的效率就特别的高。

来看一下 HashMap 的哈希算法：

 
 
 
 
    
  
  
  
  
  1. static final int hash(Object key) {
    2. 
  
  
  
  
  2.     int h;
    3. 
  
  
  
  
  3.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    4. 
  
  
  
  
  4. }
    5.

先调用对象的 hashCode() 方法，然后对该值进行右移运算，然后再进行异或运算。

通常来说，String 会用来作为 HashMap 的键进行哈希运算，因此我们再来看一下 String 的 hashCode() 方法：

 
 
 
 
    
  
  
  
  
  1. public int hashCode() {
    2. 
  
  
  
  
  2.     int h = hash;
    3. 
  
  
  
  
  3.     if (h == 0 && value.length > 0) {
    4. 
  
  
  
  
  4.         hash = h = isLatin1() ? StringLatin1.hashCode(value)
    5. 
  
  
  
  
  5.                 : StringUTF16.hashCode(value);
    6. 
  
  
  
  
  6.     }
    7. 
  
  
  
  
  7.     return h;
    8. 
  
  
  
  
  8. }
    9. 
  
  
  
  
  9. public static int hashCode(byte[] value) {
    10. 
  
  
  
  
  10.     int h = 0;
    11. 
  
  
  
  
  11.     int length = value.length >> 1;
    12. 
  
  
  
  
  12.     for (int i = 0; i < length; i++) {
    13. 
  
  
  
  
  13.         h = 31 * h + getChar(value, i);
    14. 
  
  
  
  
  14.     }
    15. 
  
  
  
  
  15.     return h;
    16. 
  
  
  
  
  16. }
    17.

可想而知，经过这么一系列复杂的运算，再加上 JDK 作者这种大师级别的设计，哈希冲突的概率我相信已经降到了最低。

当然了，从理论上来说，对于两个不同对象，它们通过 hashCode() 方法计算后的值可能相同。因此，不能使用 hashCode() 方法来判断两个对象是否相等，必须得通过 equals() 方法。

也就是说：

  • 如果两个对象调用 equals() 方法得到的结果为 true，调用 hashCode() 方法得到的结果必定相等;
  • 如果两个对象调用 hashCode() 方法得到的结果不相等，调用 equals() 方法得到的结果必定为 false;

反之：

  • 如果两个对象调用 equals() 方法得到的结果为 false，调用 hashCode() 方法得到的结果不一定不相等;
  • 如果两个对象调用 hashCode() 方法得到的结果相等，调用 equals() 方法得到的结果不一定为 true;

来看下面这段代码。

 
 
 
 
    
  
  
  
  
  1. public class Test {
    2. 
  
  
  
  
  2.     public static void main(String[] args) {
    3. 
  
  
  
  
  3.         Student s1 = new Student(18, "张三");
    4. 
  
  
  
  
  4.         Map scores = new HashMap<>();
    5. 
  
  
  
  
  5.         scores.put(s1, 98);
    6. 
  
  
  
  
  6.         System.out.println(scores.get(new Student(18, "张三")));
    7. 
  
  
  
  
  7.     }
    8. 
  
  
  
  
  8. }
    9. 
  
  
  
  
  9.  class Student {
    10. 
  
  
  
  
  10.     private int age;
    11. 
  
  
  
  
  11.     private String name;
    12. 
  
  
  
  
  12. 
  
  
  
  
  13.      public Student(int age, String name) {
    14. 
  
  
  
  
  14.          this.age = age;
    15. 
  
  
  
  
  15.          this.name = name;
    16. 
  
  
  
  
  16.      }
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.      @Override
    19. 
  
  
  
  
  19.      public boolean equals(Object o) {
    20. 
  
  
  
  
  20.          Student student = (Student) o;
    21. 
  
  
  
  
  21.          return age == student.age &&
    22. 
  
  
  
  
  22.                  Objects.equals(name, student.name);
    23. 
  
  
  
  
  23.      }
    24. 
  
  
  
  
  24.  }
    25.

我们重写了 Student 类的 equals() 方法，如果两个学生的年纪和姓名相同，我们就认为是同一个学生，虽然很离谱，但我们就是这么草率。

在 main() 方法中，18 岁的张三考试得了 98 分，很不错的成绩，我们把张三和成绩放到了 HashMap 中，然后准备输出张三的成绩：

 
 
 
 
    
  
  
  
  
  1. null
    2.

很不巧，结果为 null，而不是预期当中的 98。这是为什么呢?

原因就在于重写 equals() 方法的时候没有重写 hashCode() 方法。默认情况下，hashCode() 方法是一个本地方法，会返回对象的存储地址，显然 put() 中的 s1 和 get() 中的 new Student(18, "张三") 是两个对象，它们的存储地址肯定是不同的。

HashMap 的 get() 方法会调用 hash(key.hashCode()) 计算对象的哈希值，虽然两个不同的 hashCode() 结果经过 hash() 方法计算后有可能得到相同的结果，但这种概率微乎其微，所以就导致 scores.get(new Student(18, "张三")) 无法得到预期的值 18。

怎么解决这个问题呢?很简单，重写 hashCode() 方法。

 
 
 
 
    
  
  
  
  
  1. @Override
    2. 
  
  
  
  
  2. public int hashCode() {
    3. 
  
  
  
  
  3.     return Objects.hash(age, name);
    4. 
  
  
  
  
  4. }
    5.

Objects 类的 hash() 方法可以针对不同数量的参数生成新的 hashCode() 值。

 
 
 
 
    
  
  
  
  
  1. public static int hashCode(Object a[]) {
    2. 
  
  
  
  
  2.  if (a == null)
    3. 
  
  
  
  
  3.      return 0;
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.  int result = 1;
    6. 
  
  
  
  
  6. 
  
  
  
  
  7.  for (Object element : a)
    8. 
  
  
  
  
  8.      result = 31 * result + (element == null ? 0 : element.hashCode());
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.  return result;
    11. 
  
  
  
  
  11. }
    12.

代码似乎很简单，归纳出的数学公式如下所示(n 为字符串长度)。

注意：31 是个奇质数，不大不小，一般质数都非常适合哈希计算，偶数相当于移位运算，容易溢出，造成数据信息丢失。

这就意味着年纪和姓名相同的情况下，会得到相同的哈希值。scores.get(new Student(18, "张三")) 就会返回 98 的预期值了。

《Java 编程思想》这本圣经中有一段话，对 hashCode() 方法进行了一段描述。

设计 hashCode() 时最重要的因素就是：无论何时，对同一个对象调用 hashCode() 都应该生成同样的值。如果在将一个对象用 put() 方法添加进 HashMap 时产生一个 hashCode() 值，而用 get() 方法取出时却产生了另外一个 hashCode() 值，那么就无法重新取得该对象了。所以，如果你的 hashCode() 方法依赖于对象中易变的数据，用户就要当心了，因为此数据发生变化时，hashCode() 就会生成一个不同的哈希值，相当于产生了一个不同的键。

也就是说，如果在重写 hashCode() 和 equals() 方法时，对象中某个字段容易发生改变，那么最好舍弃这些字段，以免产生不可预期的结果。

好。有了上面这些内容作为基础后，我们回头再来看看本地方法 hashCode() 的 C++ 源码。

 
 
 
 
    
  
  
  
  
  1. static inline intptr_t get_next_hash(Thread* current, oop obj) {
    2. 
  
  
  
  
  2.   intptr_t value = 0;
    3. 
  
  
  
  
  3.   if (hashCode == 0) {
    4. 
  
  
  
  
  4.     // This form uses global Park-Miller RNG.
    5. 
  
  
  
  
  5.     // On MP system we'll have lots of RW access to a global, so the
    6. 
  
  
  
  
  6.     // mechanism induces lots of coherency traffic.
    7. 
  
  
  
  
  7.     value = os::random();
    8. 
  
  
  
  
  8.   } else if (hashCode == 1) {
    9. 
  
  
  
  
  9.     // This variation has the property of being stable (idempotent)
    10. 
  
  
  
  
  10.     // between STW operations.  This can be useful in some of the 1-0
    11. 
  
  
  
  
  11.     // synchronization schemes.
    12. 
  
  
  
  
  12.     intptr_t addr_bits = cast_from_oop(obj) >> 3;
    13. 
  
  
  
  
  13.     value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
    14. 
  
  
  
  
  14.   } else if (hashCode == 2) {
    15. 
  
  
  
  
  15.     value = 1;            // for sensitivity testing
    16. 
  
  
  
  
  16.   } else if (hashCode == 3) {
    17. 
  
  
  
  
  17.     value = ++GVars.hc_sequence;
    18. 
  
  
  
  
  18.   } else if (hashCode == 4) {
    19. 
  
  
  
  
  19.     value = cast_from_oop(obj);
    20. 
  
  
  
  
  20.   } else {
    21. 
  
  
  
  
  21.     // Marsaglia's xor-shift scheme with thread-specific state
    22. 
  
  
  
  
  22.     // This is probably the best overall implementation -- we'll
    23. 
  
  
  
  
  23.     // likely make this the default in future releases.
    24. 
  
  
  
  
  24.     unsigned t = current->_hashStateX;
    25. 
  
  
  
  
  25.     t ^= (t << 11);
    26. 
  
  
  
  
  26.     current->_hashStateX = current->_hashStateY;
    27. 
  
  
  
  
  27.     current->_hashStateY = current->_hashStateZ;
    28. 
  
  
  
  
  28.     current->_hashStateZ = current->_hashStateW;
    29. 
  
  
  
  
  29.     unsigned v = current->_hashStateW;
    30. 
  
  
  
  
  30.     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    31. 
  
  
  
  
  31.     current->_hashStateW = v;
    32. 
  
  
  
  
  32.     value = v;
    33. 
  
  
  
  
  33.   }
    34. 
  
  
  
  
  34. 
  
  
  
  
  35.   value &= markWord::hash_mask;
    36. 
  
  
  
  
  36.   if (value == 0) value = 0xBAD;
    37. 
  
  
  
  
  37.   assert(value != markWord::no_hash, "invariant");
    38. 
  
  
  
  
  38.   return value;
    39. 
  
  
  
  
  39. }
    40.

如果没有 C++ 基础的话，不用细致去看每一行代码，我们只通过表面去了解一下 get_next_hash() 这个方法就行。其中的 hashCode 变量是 JVM 启动时的一个全局参数，可以通过它来切换哈希值的生成策略。

  • hashCode==0，调用操作系统 OS 的 random() 方法返回随机数。
  • hashCode == 1，在 STW(stop-the-world)操作中，这种策略通常用于同步方案中。利用对象地址进行计算，使用不经常更新的随机数(GVars.stw_random)参与其中。
  • hashCode == 2，使用返回 1，用于某些情况下的测试。
  • hashCode == 3，从 0 开始计算哈希值，不是线程安全的，多个线程可能会得到相同的哈希值。
  • hashCode == 4，与创建对象的内存位置有关，原样输出。
  • hashCode == 5，默认值，支持多线程，使用了 Marsaglia 的 xor-shift 算法产生伪随机数。所谓的 xor-shift 算法，简单来说，看起来就是一个移位寄存器，每次移入的位由寄存器中若干位取异或生成。所谓的伪随机数，不是完全随机的，但是真随机生成比较困难，所以只要能通过一定的随机数统计检测，就可以当作真随机数来使用。

至于更深层次的挖掘，涉及到数学知识和物理知识，就不展开了。毕竟菜是原罪。

参考资料：

https://zhuanlan.zhihu.com/p/121555725 https://www.cnblogs.com/dolphin0520/p/3681042.html

本文标题：补补HashCode，毕竟菜乃原醉
文章源于：http://www.shufengxianlan.com/qtweb/news2/211202.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

软件开发知识

各行业网站

成都手机网站建设　　 　app制作　　 　大足网站建设　　 　邛崃网站建设　　 　江油网站建设　　 　成都响应式网站建设　　 　广西弘博建站　　 　格蓝特设备　　 　网络推广　　 　网络推广外包　　 　网站优化排名　　 　成都网站推广　　 　德阳服务器托管　　 　短视频拍摄　　 　泸州做网站　　 　四川成都网站设计　　 　成都营销型网站建设　　 　广安网站建设　　 　绵阳电信机房　　 　温江网站设计