yeskery

详解 Java 中的 hashcode() 和 equals() 方法及在 HashMap 中的应用

继承自 Object 类

hashcode() 和 equals() 均是 Object 类中定义的方法,这意味着所有的 Java 实例对象均继承了这两个方法。其中 hashcode() 方法是一个 native 的方法,用来产生该对象的哈希值;而 equals() 方法是用来比较两个对象是否相同,在 Object 中的实现是直接进行了内存地址比较。equals() 方法在实际使用中是使用频率非常高的方法之一,而 hashcode() 方法却不是常用的方法。hashcode() 方法的主要使用用途是在 Java 的 集合(Collection)体系中,在集合中采用了 Hash 命令的集合类都使用了这个方法。用来快速定位两个对象是否不相等,可以说 hashcode() 方法就是为了 Java 集合体系而准备的。

下面是 hashcode() 和 equals() 在 Java 中的源代码:

  1. public native int hashCode();
  2. public boolean equals(Object obj) {
  3. return (this == obj);
  4. }

重写 equals() 方法

当使用 String、Math、Integer 或 Double 等这些类的时候,这些类已经覆盖了默认的 equals() 方法以便能正确反应两个对象是否相等。如下是 String 中对 equals() 的覆盖:

  1. public boolean equals(Object anObject) {
  2. if (this == anObject) {
  3. return true;
  4. }
  5. if (anObject instanceof String) {
  6. String anotherString = (String)anObject;
  7. int n = value.length;
  8. if (n == anotherString.value.length) {
  9. char v1[] = value;
  10. char v2[] = anotherString.value;
  11. int i = 0;
  12. while (n-- != 0) {
  13. if (v1[i] != v2[i])
  14. return false;
  15. i++;
  16. }
  17. return true;
  18. }
  19. }
  20. return false;
  21. }

很明显,这是在进行内容比较,已经不再是简单的内存地址的比较了。依次类推Double、Integer、Math 等等这些类都是重写了 equals() 方法的。

我们还应该注意,Java 语言对 equals() 的要求如下:

  • 对称性:如果 x.equals(y) 返回的是 true,那么 y.equals(x) 也应该返回 true
  • 反射性x.equals(x) 必须返回 true
  • 类推性:如果 x.equals(y) 返回的是 true,而且 y.equals(z) 返回的也是 true,那么 z.equals(x) 也应该返回 true
  • 一致性:如果 x.equals(y) 返回的是 true,只要 x 和 y 内容一直不便,不管重复多少次 x.equals(y),返回值都应该是 true
  • 任何情况下:x.equals(null),返回值永远都为 falsex.equals(和x不同类型的对象),返回值永远都为 false

以上这五点是重写 equals() 方法时必须要遵守的准则,如果违反会出现意想不到的错误。

重写 hashcode() 方法

下面是 String 类中重写的 hashcode() 方法:

  1. public int hashCode() {
  2. int h = hash;
  3. if (h == 0 && value.length > 0) {
  4. char val[] = value;
  5. for (int i = 0; i < value.length; i++) {
  6. h = 31 * h + val[i];
  7. }
  8. hash = h;
  9. }
  10. return h;
  11. }

上面的代码实际在执行如下算式:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

s 代表字符串,s[i] 代表字符串的第 i 个字符,n 代表字符串长度。^ 代表求幂(空字符串的哈希码为 0)。

hashcode() 与 equals() 方法的区别

equals() 相等的两个对象,hashcode() 一定相等;equals() 不相等的两个对象,却并不能证明它们的 hashcode() 不相等。换句话说,equals() 方法不相等的两个对象,hashcode() 有可能相等。反过来,hashcode() 不相等,equals() 也一定不相等;hashcode() 相等,equals() 不一定相等。

在 Object 类中,hashcode() 是默认的是根据内存地址来计算的,而 equals() 方法是直接比较两个对象的内存地址,但因为 hashcode() 在计算哈希码时候又可能会产生冲突,造成两个不同地址的哈希码一致,因此仅仅通过 hashcode() 相等,是无法判断出两个对象是相等的;但反过来,如果 两个对象 equals() 是相等的,那么其对应的 hashcode() 也是相等的。而其子类,例如 String、Integer、Double 等在重写这两个方法时候也都遵守了这些原则。

在集合体系中的应用

在 HashSet 中不允许出现重复对象,而在 HashMap 中则不允许出现重复的 key 值,在 HashSet 中和 HashMap 中是如何确定对象是否重复的呢?

我们可以直接通过 equals() 方法来判断两个对象是否相等,因为所有重写的子类应该遵循了 equals() 方法的原则,从而来判断是否对象是否重复。但是如果每两个对象都通过 equals() 来判断是否重复,那么效率会大大降低,例如在 String 重写的 equals() 方法中,会循环判断每个字符是否相等。为了提高程序的运行的效率,Java 在两个判断两个对象是否相等的时候,先通过 hashcode() 方法来判断两个对象是否相等,如果 hashcode() 不相等,就没有进行 equals() 方法的必要,因为两个对象肯定不相等;而如果 hashcode() 相等,那么再进行 equals() 判断,就能确定两个对象是否相等了,因为 hashcode() 方法相等,其 equals() 方法返回值不一定相等。所以需要完全确定两个对象是否相等,需要 hashcode() 与 equals() 方法结合来使用。

下面是 HashMap 中 put(K key, V value) 方法中确定 key 是否重复的局部代码片段:

  1. Node<K,V> e; K k;
  2. //判断需要添加的Node是否和原来的Node一致,并且key不会null
  3. if (p.hash == hash &&
  4. ((k = p.key) == key || (key != null && key.equals(k))))
  5. e = p;

扰动函数

在 JDK1.7 中,HashMap 的 hash(int h) 方法的源代码如下:

  1. static int hash(int h) {
  2. h ^= (h >>> 20) ^ (h >>> 12);
  3. return h ^ (h >>> 7) ^ (h >>> 4);
  4. }

而在 JDK1.8 中,HashMap 的 hash(Object key) 方法的源代码如下:

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

我们知道,在 Object 类中默认提供的 hashcode() 方法,返回的是一个 int 类型的哈希码。int 类型带符号对象可以储存范围在 -21474836482147483648,这总共有四十亿个数字。如果在 HashMap 中直接用这个数组来作为数组的下标,可能最多的时候需要四十亿的映射内存空间,这显然不是内存中可以存放下的。所以这个哈希码并不能直接用在 HashMap 中数据数组的中,而需要进一步运算才能在高效合理的情况下使用哈希码。

在使用之前先要对数组的长度做取模运算,得到的余数,就是 HashMap 中数据数组的下标。

在 JDK1.7 中与这一步骤有关的是 indexFor() 方法,其源代码如下:

  1. bucketIndex = indexFor(hash, table.length);
  2. static int indexFor(int h, int length) {
  3. return h & (length-1);
  4. }

而在 JDK1.8 中去掉了这个方法,因为该方法比较简单,所以直接放在具体要访问数组的方法内部中了,下面是 HashMap 的 put(K key, V value) 中调用的 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 的局部代码片段:

  1. public V put(K key, V value) {
  2. return putVal(hash(key), key, value, false, true);
  3. }
  4. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  5. boolean evict) {
  6. Node<K,V>[] tab; Node<K,V> p; int n, i;
  7. if ((tab = table) == null || (n = tab.length) == 0)
  8. n = (tab = resize()).length;
  9. if ((p = tab[i = (n - 1) & hash]) == null)
  10. tab[i] = newNode(hash, key, value, null);
  11. //...
  12. //省略部分代码
  13. }

可以看到在使用中,也仅仅是把哈希码和数组长度-1 做了一个与运算。

我们知道,在 HashMap 中,如果创建对象时没有指定其初始容量,HashMap 默认的数据数组的大小是 16;如果创建对象时指定了初始容量,如果初始容量会被指定成大于等于这个初始容量的最小 2 的整次幂。之所以需要这么设定,是因为 (length-1) 和哈希码进行与运算之后,其结果的高位全部归零,只保留了低位值,而保留的低位值数值较小,可以用来作为 HashMap 的数据数组下标。而 (leng-1) 就相对于是一个“低位掩码”。

下面以 HashMap 的初始数据数组的默认长度 16 为例:

  1. public class HashTest {
  2. //定义一个将int类型转换为二进制并打印出来的方法
  3. private static String printNum(int n){
  4. String num = Integer.toBinaryString(n);
  5. if(num.length() == 32){
  6. return num;
  7. }else{
  8. StringBuilder sb = new StringBuilder("");
  9. for(int i =0;i < 32 - num.length(); i ++){
  10. sb.append("0");
  11. }
  12. return sb.toString() + num;
  13. }
  14. }
  15. public static void main(String[] args) {
  16. //定义HashMap中key
  17. String key = new String("哈希测试分析");
  18. //打印该key值的哈希码的二进制
  19. System.out.println(" " + printNum(key.hashCode()));
  20. //打印HashMap中默认的数据数组长度-1的二进制
  21. System.out.println("& " + printNum(16-1));
  22. System.out.println("-----------------------------------");
  23. //打印其求与运算结果
  24. System.out.println(" " + printNum(key.hashCode() & (16-1)));
  25. }
  26. }

运行上面的程序,其结果为:

  1. 00001101011011011010101111111000
  2. & 00000000000000000000000000001111
  3. -----------------------------------
  4. 00000000000000000000000000001000

根据上面的结果可以看出,其结果的高位全部为 0,只留下低位的值,其转换为十进制结果为 8,此时作为 HashMap 的数据数组下标是可以的。但是这样也出现了一个问题,就算在计算哈希码时散列值再松散,在运行行与运算之后,只剩下低位的数据,这样碰撞出现的频率就会增高。另外一个问题是,如果在做散列的时候出现了类似低位呈现规律性重复出现,那么碰撞出现的频率就更高了。

为了解决上面的问题,就需要“扰动函数”,来扰动原来的哈希码,以增大随机性,减小碰撞出现的频率。
下面以 JDK1.8 中的 hash(Object key) 来进行举例:

  1. public static void main(String[] args) {
  2. //定义HashMap中key
  3. String key = new String("哈希测试分析");
  4. int hash = key.hashCode();
  5. //打印该key值的哈希码的二进制
  6. System.out.println(" " + printNum(hash));
  7. //下面进行hash(Object key)方法中的运算
  8. //将key值的哈希码右移16位
  9. System.out.println("^ " + printNum(hash >>> 16));
  10. System.out.println("-----------------------------------");
  11. hash = hash ^ (hash >>> 16);
  12. //打印hash与hash右移16位数值的或运算结果
  13. System.out.println(" " + printNum(hash));
  14. System.out.println();
  15. System.out.println(" " + printNum(hash));
  16. //打印HashMap中默认的数据数组长度-1的二进制
  17. System.out.println("& " + printNum(16-1));
  18. System.out.println("-----------------------------------");
  19. //打印其求与运算结果
  20. System.out.println(" " + printNum(hash & (16-1)));
  21. System.out.println(hash & (16-1));
  22. }

上面的程序运算结果是:

  1. 00001101011011011010101111111000
  2. ^ 00000000000000000000110101101101
  3. -----------------------------------
  4. 00001101011011011010011010010101
  5. 00001101011011011010011010010101
  6. & 00000000000000000000000000001111
  7. -----------------------------------
  8. 00000000000000000000000000000101

上面的程序可以用如下的简化形式表示:

  1. h=hashCode():00001101011011011010101111111000 //调用"哈希测试分析"字符串的hashCode()方法
  2. h:00001101011011011010101111111000
  3. h>>>16:00000000000000000000110101101101 //将哈希码右移16位
  4. ------------------------------------------------
  5. hash=h^(h>>>16):00001101011011011010011010010101 //计算后的哈希码
  6. hash:00001101011011011010011010010101
  7. (16-1):00000000000000000000000000001111 //HashMap默认的数据数组长度-1
  8. ------------------------------------------------
  9. 00000000000000000000000000000101 //计算后的结果,转换为十进制等于5

将原来的哈希码右移16位,正好是32位的一半,刚好将原来哈希码的高位移动到了低位,再用原来哈希码的高位和低位做异或,这样就扰动了原来哈希码的高位和低位,以及来增大随机性。混合后的哈希码掺杂了部分高位码的特征,换句话说,混淆后的哈希码也保留也原来哈希码部分高位码。

而在 JDK1.7 中,进行了 4 次扰动,其原理和 JDK1.8 中的一致,都是为了增大随机性。但经过测试,扰动四次的碰撞次数并没有比扰动一次减少太多,反而运算四次增加了程序的运算量,所以在 JDK1.8 中改为了一次,这也是在性能和算法策略中寻求的一种平衡。

本文部分内容来自:

  1. java中hashcode()和equals()的详解
  2. JDK 源码中 HashMap 的 hash 方法原理是什么?

评论

发表评论 点击刷新验证码

提示

该功能暂未开放