关于java中的hashcode和equals方法原理

时间:2022-06-16 16:09:50

关于java中的hashcode和equals方法原理

1、介绍

java编程思想和很多资料都会对自定义javabean要求必须重写hashcode和equals方法,但并没有清晰给出为何重写此两个方法,至少不是非常的明确。

首先要确定的一件事是并不是“必须”,估计跟中英文语言习惯有关。hashcode方法只有在和hash类型的集合(比如HashMap和HashSet)配合使用时才会进行调用,否则是没有必要重写该方法的。

所以很多人会迷惑,自己并没有重写这方法,程序跑起来也没有问题。要说明这个问题必须要搞懂hashcode的真正作用以及使用场景。

2、hashcode

hashcode是java中Objet类定义的方法,默认返回的是对象的内存地址。但该方法的本意是散列。散列的话就必然涉及到在一定的空间中进行散列,所以hashcode方法一定是和集合配合使用的时候才用得到。

对象在空间散列化存储之后,其优势在于检索,如果散列算法处理得好,也就是能够保证对象在空间中尽可能均匀分布,则在检索时,一旦确定桶的方位(即下标值),就可以排除(n-1)/n的数据量,所有在大型数据集合中,hash之后的对象检索性能是非常高的。

java中的HashMap集合的内部实现是数组+链表实现,即Node[]数组方式实现的。而Node的源代码如下:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

说明Node节点类是一种手拉手实现的链表方式,而Node[]在java编程思想中称为桶集合,数组中每个元素可以看成一个桶。HashMap集合在初始化时会先分配16个桶的空间,在进行put操作时,会先将KV封装成Node对象,再对key进行计算,判断应该划分到哪个桶中。

注意key在集合中是“不重复”的,因此如果key存在,就将新的value替换掉旧的value,如果key不存在,就在链表的末尾进行添加。如何判断key是否重复?HashMap类中的putVal方法源码如下:请注意注释地方的判断条件是

p.hash == hash 
            &&((k = p.key) == key || (key != null && key.equals(k))),

首先明确p是KV构成Node对象,该对象源码中可见含有四个属性,分别是int hash、K key、V value和Node<K,V> next,其中hash并不是key中的hashcode,是对key的hashcode计算之后生成的新hash值,我们称为新哈希,而生成新hash的算法是:

    int newhash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

翻译过来就是将旧哈希(我们称key对象的hashcode为就hash)向右移动16位之后和自身做异或运本意就是将高16位和低16位的值进行异或运算得到一个新的数值,这么做的意图非常明显,高位移位运算是想让更多的特征值参与进来,采用异或计算是想让数据更加分散。我们知道二进制位运算中有|、&、^和~,很明显~是单元运算,如果采用|运算记录计算结果很大比例偏大,而采用&很大比例计算结果偏小,^运算刚好高低比例相同。如此看来,设计也是非常巧妙的。

上面的判断条件翻译过来,就是:如果两个节点的新hash不同,则key一定不同。但如果新hash相同,还要判断key是否是同一对象,若是同一对象,则说明key相同,若不是同一对象,再判断equals方法是否相同。可以使用如下判断语句来描述获取更加清晰易懂:

if(newhash1 != newhash2){
        //不同
}
else{
    if(key1 == key2){
        //相同                            
    }
    else{
        if(key1.equals(key2)){
            //相同
        }
        else{
        //不同
        }
    }
}

桶的防止策略是对新hash对(桶数量-1)进行&运算产生的结果作为桶的下标值,由此可以看出,桶的数量一定是2的n次幂,默认是16只桶,即2^4次方,扩容以后会32,64以此类推下去。算法如下:

(n - 1) & hash      //(16 - 1) & hash与取摸操作是等效的。

3、equals方法

equals方法比较简单,就是判断对象内容是否相同,默认实现是判断内存地址。在java的集合中,List并不判断对象hashcode值,只判断equals方法。

4、总结

java集合中,HashMap和HashSet使用hashcode进行对象的散列存储,因此会用到hashcode方法,自然也会用到equals方法,List集合只使用equals方法判断对象是否相等。

在java的集合中,真正的集合只有数组和链表两种实现,HashMap是通过两者组合实现的,而HashSet内部是通过HashMap实现的,丢弃了HashMap中的value部分,使用了一个垃圾值(dummy)进行填充实现的。

所以究其根本,ArrayList和LinkedList应该是最基本的集合,数组列表内部封装数组,擅长读操作,大量写入时(尤其是在队首插入数据)性能较差,因为需要移动所有元素,而LinkdedList在写入时非常有优势,查询则较差,两者各有优缺点,在使用单机进行百万数据读写的评测中,数组列表读取能是列表是进10倍,而列表的写入能力是数组列表的10倍以上,差距还是非常明显的。