hashCode()方法对HashMap的性能影响

HashMap的put()方法会比较key的hash值，key的hash值获取方式如下：

//HashMap的put方法
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    //先获取key的hash值，如果key为null则hash值为0;如果key不为null，则获取key的hashCode值赋给h，然后求出h的(h向右移16位)次方，作为key的hash值
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    /**
     * 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}.
     */
    public native int hashCode();

可以看到，最后调用的还是hashCode()方法

实现一个好的hashCode()方法，能够尽可能地减少冲突，性能就会大大提高，下面举个栗子：

创建一个对象，让它重写hashCode方法，返回固定的值1

public class TestObject {
    public String name;

    @Override
    public int hashCode() {
        return 1;
    }

    public TestObject(String name) {
        this.name = name;
    }
}

然后创建10000个对象存入hashMap中，并用get方法取出来，计算耗时

public class Test {

    public static void main(String[] args) {
        HashMap<TestObject, String> hashMap = new HashMap<>();
        long currentTimeMillis = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            TestObject testObject1 = new TestObject("zhangsan");
            hashMap.put(testObject1, "abc");
        }
        for (TestObject testObject : hashMap.keySet()) {
            hashMap.get(testObject);
        }
        System.out.println(System.currentTimeMillis() - currentTimeMillis);
    }

}

输出结果为：

也就是一千多ms

如果不重写HashCode方法，用自己默认的hashCode方法

public class TestObject {
    public String name;

    public TestObject(String name) {
        this.name = name;
    }
}

再次运行，输出结果为：

几毫秒左右

另外说一下，发生冲突后数据的存放问题：

当put()操作有冲突时，新的Entry依然会被安放在对应的索引下标内，并替换原有的值。同时，
为了保证旧值不丢失，会将新的Entry的next指向旧值。这便实现了在一个数组索引空间内，存放多个值项。
此时，HashMap实际上是一个链表的数组。
如果hashCode()或者hash()方法实现较差，在大量冲突产生的情况下，HashMap事实上就退化为几个链表，对HashMap的操作等价于遍历链表，此时性能很差。