了解hashMap前，首先直到Object类中的两个方法。hashCode 和equals.

1
2
3
4
5
public native int hashCode();
public boolean equals(Object obj)
{	//直接比较对象
    return (this==obj);
}

String类中重写了equals方法，比较的是字符串的值。

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

当equals被重写时，通常有必要重写hashCode方法，以满足hashCode方法的常规规定，该规定声明相等的对象必须要具有相等的哈希码。

hashCode方法是为哈希家族的集合类框架（HashMap，HashSet，HashTable）提供的服务，hashCode协定：

在同一个对象上多次调用hashCode方法时，必须一致的返回相同的整数。

如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。

HashMap工作原理说明

工作原理：通过hash算法，通过put和get存储和获取对象。

  1. 存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Factor则resize为原来的2倍)。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来。如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
  2. 获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。

HashMap

HashMap是最常用的集合类框架之一，它实现了Map接口，所以存储的元素也是键值对映射的结构，并允许使用null值和null键，其内元素是无序的，如果要保证有序，可以使用LinkedHashMap。HashMap是线程不安全的。

HashMap中我们最长用的就是put(K, V)和get(K)。我们都知道，HashMap的K值是唯一的，那如何保证唯一性呢？我们首先想到的是用equals比较，没错，这样可以实现，但随着内部元素的增多，put和get的效率将越来越低，这里的时间复杂度是O(n)，假如有1000个元素，put时需要比较1000次。实际上，HashMap很少会用到equals方法，因为其内通过一个哈希表管理所有元素，也可以称为散列表，哈希算法可以快速的存取元素，当我们调用put存值时，HashMap首先会调用K的hashCode方法，获取哈希码，通过哈希码快速找到某个存放位置，这个位置可以被称之为bucketIndex，通过上面所述hashCode的协定可以知道，如果hashCode不同，equals一定为false，如果hashCode相同，equals不一定为true。所以理论上，hashCode可能存在冲突的情况，有个专业名词叫碰撞，当碰撞发生时，计算出的bucketIndex也是相同的，这时会取到bucketIndex位置已存储的元素，最终通过equals来比较，equals方法就是哈希码碰撞时才会执行的方法，所以前面说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出K是否已存在，如果已存在，则使用新V值替换旧V值，并返回旧V值，如果不存在 ，则存放新的键值对<K, V>到bucketIndex位置。

HashMap 中put方法的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public V put(K key, V value) {  
    // 处理key为null，HashMap允许key和value为null  
    if (key == null)  
        return putForNullKey(value);  
    // 得到key的哈希码  
    int hash = hash(key);  
    // 通过哈希码计算出bucketIndex  
    int i = indexFor(hash, table.length);  
    // 取出bucketIndex位置上的元素，并循环单链表，判断key是否已存在  
    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;  
        }  
    }  
    // key不存在时，加入新元素  
    modCount++;  
    addEntry(hash, key, value, i);  
    return null;  
}

HashMap的初始长度

首先明确，hashmap的默认初始长度是16，并且每次自动扩展或者手动扩展时，长度必须是2的幂。

之所以选择16，是为了服务于从key映射到index的hash算法。

从key映射到hashMap数组的对应位置，会用到一个hash函数，为了实现一个尽量均匀分布的hash函数，通过key的hashCode值来做运算。

为了实现高效的Hash算法，采用了位运算的方法。

index = HashCode(Key) & (Length-1)

以Book为key演示过程。

  • 计算book的hashCode,为10进制的3029737，二进制的1011100011101011101001
  • 假定HashMap长度默认16，计算Length-1 为10进制15，二进制1111
  • 两个结果做与运算，1011100011101011101001&1111 = 1001 十进制是9，所以index=9.
  • 所以Hash算法最终得到的index结果，完全取决于Key的HashCode的最后几位。

这样做不但效果上等同于取模，还大大提高了性能。

要是其他的话，就不平均了，

由于取16，这样index的结果完全等同于HashCode最后几位的值，只要输入的HashCode平均，Hash算法结果就是平均的。

高并发下的HashMap

首先要明白rehash，rehash是HashMap在扩容时候的一个步骤。

HashMap的容量是有限的，当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会越来越高，这时候，就需要扩展长度，resize。

Resize并不是简单的把长度扩大，而是经过下面两个步骤。

  • 扩容 创建一个新的Entry空数组，长度是原数组的2倍。
  • reHash 遍历原Entry数组，把所有Entry重新Hash到新数组。重新Hash是因为长度扩大后，Hash规则也随之改变。
多线程下HashMap的rehash操作带来的问题

可能会形成链表环。

https://mp.weixin.qq.com/s/dzNq50zBQ4iDrOAhM4a70A