equals和hashCode源码解析
equals和hashCode源码解析
乒乓狂魔 发表于3年前
equals和hashCode源码解析
  • 发表于 3年前
  • 阅读 521
  • 收藏 5
  • 点赞 0
  • 评论 1

新睿云服务器60天免费使用,快来体验!>>>   

equals和hashCode网上也有很多的资料。这里只是记录下我目前的理解与认识。
大家会经常听到这样的话,当你重写equals方法时,尽量要重写hashCode方法,有些人却并不知道为什么要这样,待会就会给出源码说明这个原因。

首先来介绍下Object的equals和hashCode方法。如下:

public native int hashCode();
public boolean equals(Object obj) {
        return (this == obj);
    }

这里挺简单的,equals(obj)默认比较的是内存地址,hashCode()方法默认是native方法,看下它的文档说明:
/**
* 关注点1
     * Returns a hash code value for the object. This method is
     * supported for the benefit of hash tables such as those provided by
     * {@link java.util.HashMap}.
     * <p>
     * The general contract of {@code hashCode} is:
     * <ul>
     * <li>Whenever it is invoked on the same object more than once during
     *     an execution of a Java application, the {@code hashCode} method
     *     must consistently return the same integer, provided no information
     *     used in {@code equals} comparisons on the object is modified.
     *     This integer need not remain consistent from one execution of an
     *     application to another execution of the same application.
* 关注点2
     * <li>If two objects are equal according to the {@code equals(Object)}
     *     method, then calling the {@code hashCode} method on each of
     *     the two objects must produce the same integer result.
     * <li>It is <em>not</em> required that if two objects are unequal
     *     according to the {@link java.lang.Object#equals(java.lang.Object)}
     *     method, then calling the {@code hashCode} method on each of the
     *     two objects must produce distinct integer results.  However, the
     *     programmer should be aware that producing distinct integer results
     *     for unequal objects may improve the performance of hash tables.
     * </ul>
     * <p>
* 关注点3
     * As much as is reasonably practical, the hashCode method defined by
     * class {@code Object} does return distinct integers for distinct
     * objects. (This is typically implemented by converting the internal
     * address of the object into an integer, but this implementation
     * technique is not required by the
     * Java<font size="-2"><sup>TM</sup></font> programming language.)
     *
     * @return  a hash code value for this object.
     * @see     java.lang.Object#equals(java.lang.Object)
     * @see     java.lang.System#identityHashCode
     */
    public native int hashCode();

这里有三个关注点。
关注点1:主要是说这个hashCode方法对哪些类是有用的,并不是任何情况下都要使用这个方法(此时是根本没有必要来复写此方法),而是当你涉及到像HashMap、HashSet(他们的内部实现中使用到了hashCode方法)等与hash有关的一些类时,才会使用到hashCode方法。

关注点2:推荐按照这样的原则来设计,即当equals(object)相同时,hashCode()的返回值也要尽量相同,当equals(object)不相同时,hashCode()的返回没有特别的要求,但是也是尽量不相同以获取好的性能。

关注点3:默认的hashCode实现一般是内存地址对应的数字,所以不同的对象,hashCode()的返回值是不一样的。

java世界里的相同:
如Person类,含有name和age属性:

public class Person {

	private String name;
	private int age;
	
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	@Override
	public boolean equals(Object obj) {
		if(!(obj instanceof Person)){
			return false;
		}
		Person tmp=(Person)obj;
		return name.equals(tmp.getName()) && age==tmp.getAge();
	}

}

我们认为当name和age值都相同时就是一个相同的person,所以我们可以重写equals方法如上所述,这样我们就可以调用perosn1.equals(person2)来判断他们是否相同。然而这样就完了吗?如果你不涉及其他有关hash方面的内容,这样的确可以满足你的需求了,也就是说这样做仅仅是针对部分情况是可以的,并没有针对全部情况,如若使用HashMap、HashSet等还想实现person1和person2相同,仅仅重写equals方法肯定是不够的,必须要重写hashCode方法。

为什么会有Hash类型的Map?
简单理解:Map本身是存放key和value信息的地方,若想获取某个key1对应的value,即map.get(key1),常规思维就是拿key1和所有的key一个一个去比较,若相同,则返回对应的value。假如有10000个key,要比较10000次吗?这样的效率难道不是很低下的吗?所以要改进,假如我们对key1进行某种运算直接能得到对应value的存储位置,来直接获取到value,这样不是最爽的吗?不再和其他key进行比较了,而是得到位置,直接获取对应的value。这就是HashMap等的基本原理,同时hashCode方法在得到位置信息上发挥着巨大的作用。

接下来HashMap的源码分析这一具体过程:

static final Entry<?,?>[] EMPTY_TABLE = {};
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

HashMap内部是由Entry<K,V>类型的数组table来存储数据的。来看下Entry<K,V>的代码:
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        //略
}

Entry<K,V>有四个重要的属性,是一对key和value的结合,同时包含下一个Entry<K,V>,就像链表一样,最后一个就是哈希值h(这个哈希值就是key的hashCode方法的返回值经过hash运算得到的值)。
所以我们可以画出HashMap的存储结构:


图中的每一个方格就表示一个Entry<K,V>对象,其中的横向则构成一个Entry<K,V>[] table数组,而竖向则是由Entry<K,V>的next属性形成的链表。
假入我们想找编号为2的value,如果我们能直接找到它所在数组中的索引便可以快速找到它,假如我们想找编号为73的value,如果我们能直接找到编号7然后再继续沿着链表寻找,便可以快速找到它。

首先看下它HashMap是如何来添加的,即 put(K key, V value)方法:

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

现在先不管HashMap扩容的事情,我们重点关注它的存的过程,首先就是计算key的hash值,这个hash计算的过程便用到了key对象的hashCode方法,如下:
final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

先不用看懂这个方法是怎么计算的,它的内容就是对key的hashCode方法返回值进行一系列的运算得到一个最终的值,这个值就是hash值,就是上文所说的Entry<K,V>中的h属性的值。
得到这个hash值后,紧接着执行了int i = indexFor(hash, table.length);就是找到这个hash值在table数组中的索引值,具体方法indexFor(hash, table.length)为:

static int indexFor(int h, int length) {
        return h & (length-1);
    }

就是拿刚才生成的hash值和(table数组的长度减一)进行了相&操作,可以看到我们得到的hash值是一个很大很大的数字,和length-1相&之后的值,必然是在0到length-1之内,即在table数组的范围之内。得到的这个索引之后,接下来针对这个索引值对应的链表便进行放入或者替换操作。遍历这个链表,拿要放进来的key和这个链表上的每一对象的key进行下对比,看是否一致,若一致则进行替换操作,若都不一致则进行新的插入操作。

判断是否一致的条件是:e.hash == hash && ((k = e.key) == key || key.equals(k)),一定要牢牢记住这个条件。

必须满足的条件1:hash值一样,hash值的来历就是根据key的hashCode再进行一个复杂的运算,当两个key的hashCode一致的时候,计算出来的hash也是必然一样的。

必须满足的条件2:两个key的引用一样或者equals相同。

综上所述,HashMap对于key的重复性判断是基于两个内容的判断,一个就是hash值是否一样(会演变成key的hashCode是否一样),另一个就是equals方法是否一样(引用一样则肯定一样)。它依据的是两个条件,所以对于上文的Person类,若想在HashMap中以person对象作为key,要满足person1对象和person2对象一样,则我们必须要重写equals方法和hashCode方法。若没有重写hashCode方法,则使用系统默认的本地hashCode方法,不同的对象的hashCode是不一样的,所以HashMap在判断时就会认为person1和person2是不一样,造成了我们事与愿违的结果。
HashMap为什么要多引入key的hash是否一致的判断条件呢?为什么不仅仅判断equals方法是否一样?
我认为原因如下

好处1:当这个table数组特别大的时候,如长度为10000,根据hash&length-1这个计算的索引值,便很快的定位某一个链表下,过滤了很大一批数据,不需要一个一个遍历。仅仅依靠equals是无法实现这样的快速过滤的。

好处2:不同的hash值得出的索引位置很可能是一样的,所以在这个链表下仍要进一步判断,此时就需要一个一个进行遍历。Entry<K,V>对象中hash值是已经保存的数据,新的key的hash也已经计算出来,所以在遍历对比的过程中判断hash值是否一致是相当快的,如果不一致,则认为不相同继续下一个判断,就不会调用费时的equals方法。假如这个链表的数据也特别多,判断过程也是相当快的。也就是说,判断hash是否一致加快了在链表上的遍历的速度,减少了相对费时的equals调用次数。

综上所述,为了实现HashMap的上述高效的存储操作,引入了hash这个重要的东西。同时带给我们的附加操作就是要满足key一致除了equals返回true外,还必须让hashCode一样。所以我们重写equals方法的时候尽量的重写hashCode方法,当用到HashMap或者HashSet等时必须要重写hashCode方法。
hashCode的重写的原则:当equals方法返回true,则两个对象的hashCode必须一样。
如String、Integer等类都重写了equals方法和hashCode方法,都是遵循上述原则。所以我们在重写hashCode时也要遵循上述原则。

接下来看下get(Object key)源代码的具体寻找过程:

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

就是找到对应key的Entry<K,V>对象,有了这个对象我们便可以获取到value。继续看下是如何来找到key对应的Entry<K,V>对象的:
final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

看到这里就会明白了这个过程,和上面put的过程类似的。

hash&length-1结果相同我们称为冲突
同时要思考什么样的情况下,get(key)过程是最快的?当然是hash&length-1的结果所在的数组索引下只有一个对象,还没有其他对象插入进来。也就是当所有的数据均匀分布在table上,而不是集中在table某个索引对应的连表上的时候此时get操作的效率是相当高的,为了达到这一个操作,就是要满足hash&length-1要尽可能的不同,减少冲突。

首先看length-1:它的原因是因为要限制在table数组内,同时还有一个重要的作用就是减少冲突。首先要知道length的长度是2的幂级数,这个是HashMap来保证的,下一篇文章再说HashMap的大小及扩容。假如length为7,3&(7-1) 即二进制的11&110等于10,2&(7-1),即二进制的10&110即10,这就是说2和3这两个值不一样,却造成了一样的索引值,即产生了冲突,当length=8时,11&111为11,10&111为10所以避免了冲突。所以当length-1的二进制为全1时,会起到避免冲突的作用。

接着看hash值,hash值是由key的hashCode经过hash运算得到的,为了让hash&length-1的结果尽量不产生冲突,hash的值也要尽量均匀,这就对hash算法提出了很高的要求,一个好的hash算法,会让不同的hashCode计算出来的hash值更加均匀分布。hash算法不在本文的范围之内,感兴趣的可以去研究。

接下来顺便看看HashSet的原理:
Set与List相比是无序的,不允许元素重复。元素重复的依据和HashMap对key的要求是一样的。即所存元素的hash值一样并且equals相同才是一样的元素。看下代码:

private transient HashMap<E,Object> map;

    private static final Object PRESENT = new Object();

看到了没有,HashSet内部是有一个HashMap的,这个key就是HashSet的元素,而value始终是一个固定的值PRESENT。
看下HashSet的add方法:

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

看到没有,HashSet就是依托HashMap中的key不能重复来实现HashSet中自身的元素不能重复的。

下一篇文章就要讲讲HashMap的扩容。
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 926
博文 104
码字总数 265075
评论 (1)
今秋
写得真详细,赞一个
×
乒乓狂魔
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: