深入 Java 源码来剖析 hashCode,从此菜不再是原罪(2)-阿里云开发者社区

开发者社区> 沉默王二> 正文

深入 Java 源码来剖析 hashCode,从此菜不再是原罪(2)

简介: 深入 Java 源码来剖析 hashCode,从此菜不再是原罪
+关注继续查看

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


也就是说:


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

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

反之:


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

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

来看下面这段代码。


public class Test {
    public static void main(String[] args) {
        Student s1 = new Student(18, "张三");
        Map<Student, Integer> scores = new HashMap<>();
        scores.put(s1, 98);
        System.out.println(scores.get(new Student(18, "张三")));
    }
}
 class Student {
    private int age;
    private String name;
     public Student(int age, String name) {
         this.age = age;
         this.name = name;
     }
     @Override
     public boolean equals(Object o) {
         Student student = (Student) o;
         return age == student.age &&
                 Objects.equals(name, student.name);
     }
 }



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


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


null


很不巧,结果为 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() 方法。


@Override
 public int hashCode() {
     return Objects.hash(age, name);
 }
Objects 类的 hash() 方法可以针对不同数量的参数生成新的 hashCode() 值。
public static int hashCode(Object a[]) {
 if (a == null)
     return 0;
 int result = 1;
 for (Object element : a)
     result = 31 * result + (element == null ? 0 : element.hashCode());
 return result;
}


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




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


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


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


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

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


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


static inline intptr_t get_next_hash(Thread* current, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    // This form uses global Park-Miller 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 addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
  } else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
  } else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
  } else if (hashCode == 4) {
    value = cast_from_oop<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 = current->_hashStateX;
    t ^= (t << 11);
    current->_hashStateX = current->_hashStateY;
    current->_hashStateY = current->_hashStateZ;
    current->_hashStateZ = current->_hashStateW;
    unsigned v = current->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    current->_hashStateW = v;
    value = v;
  }
  value &= markWord::hash_mask;
  if (value == 0) value = 0xBAD;
  assert(value != markWord::no_hash, "invariant");
  return value;
}



如果没有 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 算法,简单来说,看起来就是一个移位寄存器,每次移入的位由寄存器中若干位取异或生成。所谓的伪随机数,不是完全随机的,但是真随机生成比较困难,所以只要能通过一定的随机数统计检测,就可以当作真随机数来使用。

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


我最近花了近一周的时间整理了一份纯 Java 版的刷题笔记,一共 300 道题解!


图文并茂,截图如下,不只是干巴巴的题解代码,很多题都给出了多种解题思路,真的会提高大家刷题的幸福指数~


image.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
(周期计划-8)常用集合的源码分析:HashMap
写在前面 感兴趣的看官,可以看看我的其他文章:1、从公司代码看Notification2、Java反射实践:从反射中理解class3、从公司项目配置看Gradle 上一篇博客,我们分析了ArrayList的源码实现,ArrayList吊起来观察一番之后,那么下一个被吊起来的肯定就是HashMap了。
813 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12070 0
Java集合之HashMap源码解析
HashMap HashMap 是 Map 的一个实现类,它代表的是一种键值对的数据存储形式。 大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。
695 0
Java集合源码学习(四)HashMap分析
ArrayList、LinkedList和HashMap的源码是一起看的,横向对比吧,感觉对这三种数据结构的理解加深了很多。 数据结构中有数组和链表来实现对数据的存储,这两者有不同的应用场景, 数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,插入和删除容易; 哈希表的实现结合了这两点,哈希表的实现方式有多种,在HashMap中使用的是链地址法,也就是拉链法。
1509 0
绝了!这是我见过最详细的HashMap源码解析(上)
HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长. HashMap是非线程安全的,只适用于单线程环境,多线程环境可以采用并发包下的concurrentHashMap HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆 HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键.此类不保证映射的顺序,特别是它不保证该顺序恒久不变.
10 0
HashSet及LinkedHashSet源码分析(基于JDK1.6)
Java容器类的用途是“保存对象”,分为两类:Map——存储“键值对”组成的对象;Collection——存储独立元素。Collection又可以分为List和Set两大块。List保持元素的顺序,而Set不能有重复的元素。
723 0
HashMap源码分析(基于JDK1.6)
在Java集合类中最常用的除了ArrayList外,就是HashMap了。本文尽自己所能,尽量详细的解释HashMap的源码。一山还有一山高,有不足之处请之处,定感谢指定并及时修正。     在看HashMap源码之前先复习一下数据结构。
498 0
细读源码之-HashMap
大家开发中用得最多的工具类就是JAVA的集合框架了,今天我们来从源码的角度剖析Map集合的实现之一HashMap。
274 0
+关注
沉默王二
微信搜索「沉默王二」,回复关键字「00」获取硬核计算机基础资料。
1084
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载