Java 7、8下的HashMap分析

￡神魔★判官ぃ 2021-08-26 21:18 219阅读 0赞

## 1、hashMap结构： ##

我们先来看下hashmap的结构

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70][]

*  hashmap默认大小（capacity）是16个元素（必须是2的幂）；
 *  加载因子（loadfactory）为0.75：即当元素个数超过容量长度的0.75倍时，进行扩容，扩容大小是原大小的一倍（左移1位操作： <<1）；
 *  hashMap的结构是：索引数组（table）+ 链表组成；

### 1.1）put方法： ###

1）put方法分为以下两个步骤：

1.  先对key进行hash操作，int hash = hash(key);
2.  hash之后结合数组的长度进行一个&操作得到得到数组的下标，int i = indexFor(hash, table.length);
3.  找到数组对应小标的链表，判断链表中是否存在该元素？存在则更新、并返回，否则创建新的entiry，采用头插法插入；（创建新entiry时会判断是否resize）

jdk1.7中put的核心代码：

public V put(K key, V value) {
    	//校验key是否为空
    	if (key == null)
    		return putForNullKey(value);
    	int hash = hash(key);	//获取key对应的hash值
    	int i = indexFor(hash, table.length);	//得到该KV对应的table的index
    	//这个for循环就是在校验table[i]对应的链表中要插入的K key有没有存在:
    	//如果有，那么就用put的 value替换,然后返回该key对应的老的value,否则创建新的entry
        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++;//修改次数+1
    	addEntry(hash, key, value, i); //确定key没有重复之后，插入(K,V)
    	return null;
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
    	//判断是否需要扩容
    	if ((size >= threshold) && (null != table[bucketIndex])) {
    		resize(2 * table.length);//扩容
    		hash = (null != key) ? hash(key) : 0; //扩容后，对应的hash需要重新计算
    		bucketIndex = indexFor(hash, table.length);//扩容后，对应的bucketIndex需要重新计算
    	}
    	//判读是否需要扩容后，插入
    	createEntry(hash, key, value, bucketIndex);
    }

void createEntry(int hash, K key, V value, int bucketIndex) {
    	///多个线程操作数组的同一个位置
    	Entry<K,V> e = table[bucketIndex];
    	table[bucketIndex] = new Entry<>(hash, key, value, e);
    	size++;
    }

注：new Entry<>()的构造方法，将key-value键值对赋给table\[bucketIndex\]，并将其next指向元素e，这便将key-value放到了头结点中，并将之前的头结点接在了它的后面。（头插法）

### 1.2）get方法： ###

根据key的hashcode算出元素在数组中的下标，之后遍历Entry对象链表，直到找到元素为止。

// 获取key对应的value 
     public V get(Object key) {
            if (key == null)
                //如果key为null,调用getForNullKey()
                return getForNullKey();
            //key不为null,调用getEntry(key);
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
    }
     //当key为null时,获取value
        private V getForNullKey() {
            if (size == 0) {
                return null;//链表为空,返回null
            }
        //链表不为空,将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }
    
    //key不为null,获取value
    final Entry<K,V> getEntry(Object key) {
            if (size == 0) {//判断链表中是否有值
             //链表中没值,也就是没有value
                return null;
            }
           //链表中有值,获取key的hash值 
            int hash = (key == null) ? 0 : hash(key);
            // 在“该hash值对应的链表”上查找“键值等于key”的元素 
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                //判断key是否相同
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;//key相等,返回相应的value
                 }
            return null;//链表中没有相应的key
        }

注：key为null的键值对永远放在table\[0\]的链表中。

### 1.3）扩容： ###

根据上面的put方法源码可以知道，每次put元素时会判断：元素个数size >= threshold(capacity \* loadFactor)，并且对应数组下表不为空时，开始扩容：

*  申请一个大的数组，capacity是原来的2倍；
 *  遍历原数组，以及遍历每个数组下的链表元素，重新计算位置，采用头插法更新到新数组中；

jdk1.7扩容核心代码：

void resize(int newCapacity) {   //传入新的容量
        Entry[] oldTable = table;    //引用扩容前的Entry数组
        int oldCapacity = oldTable.length;         
        if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            return;
        }
     
        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
        transfer(newTable);                         //！！将数据转移到新的Entry数组里
        table = newTable;                           //HashMap的table属性引用新的Entry数组
        threshold = (int)(newCapacity * loadFactor);//修改阈值
    }

void transfer(Entry[] newTable) {
        Entry[] src = table;                   //src引用了旧的Entry数组
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
            Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
            if (e != null) {
                src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                    e.next = newTable[i]; //标记[1]
                    newTable[i] = e;      //将元素放在数组上
                    e = next;             //访问下一个Entry链上的元素
                } while (e != null);
            }
        }
    }

经过resize（扩容）后，原来一个链表中的元素，有些元素可能换到了数组其他位置上，剩下的元素按照倒序（因为头插法）组成了新的链表。具体过程如下；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 1][]

注：以上都是基于jdk1.7的代码。在1.8中做了优化：

*  引入了红黑数结构，当链表长度超过8时改为红黑树；
 *  在resize时，不需要像JDK1.7的实现那样重新计算hash，从而避免了链表倒序的问题，进而解决了死循环；（详见下文）

参考：

[https://tech.meituan.com/2016/06/24/java-hashmap.html][https_tech.meituan.com_2016_06_24_java-hashmap.html]

[https://blog.csdn.net/bushanyantanzhe/article/details/79182880][https_blog.csdn.net_bushanyantanzhe_article_details_79182880]

## 2、线程安全问题： ##

### 2.1）多线程put后可能导致get死循环： ###

根据上面分析，在put方法中会判断是否需要扩容，扩容代码transfer方法采用循环的方式进行rehash，以及头插法组装新链表。如果在并发情况下， 就会造成链表形成环，这是在进行get操作时，就会出现死循环，导致cpu飙升。

举一个简单的例子：假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。多线程中可能会造成链表形成环，即：1->2的同时2->1。

**1）jdk1.8中resize（扩容）优化：**

每次扩容我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 2][]

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 3][]

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 4][]

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。

注：虽然jdk1.8中做了上述优化避免了链表循环，但是hashmap仍然是线程不安全的！！！

### 2）jdk1.8另一个优化（红黑树）： ###

这个优化主要是针对性能，和线程安全性无关！

HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，那样所有的键值对都集中在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化，总体性能优于JDK1.7，下面我们从两个方面用例子证明这一点。

在hash均匀情况下二者性能对比：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 5][]

上面由于hash均匀，所以jdk1.8中的mash红黑树无法发挥作用，那么下面在hash不均匀情况下，二者性能对比：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 6][]

### 2.2）多线程put的时候可能导致元素丢失 ###

考虑在多线程下put操作时，都会执行addEntry(hash, key, value, i)，此时如果有产生哈希碰撞，导致两个线程得到同样的bucketIndex去存储，就可能会出现覆盖丢失的情况：

可以看到，如果两个线程都同时取得了e，则他们下一个元素都是e，然后赋值给table元素的时候有一个成功有一个丢失。

### 2.3）put非null元素后get出来的却是null ###

考虑在多线程读写的时候，如果发生了resize（扩容），这时就会进入transfer方法，如下：

在这个方法里，将旧索引数组赋值给src，遍历src，当src的元素非null时，就将src中的该元素置null（释放旧的引用），即将旧数组中的元素置null了，也就是这一句，此时若有get方法访问这个key，它取得的还是旧数组，当然就取不到其对应的value了。

注：由于jdk1.8对扩容做了优化，所以这个问题在jdk1.8上也是不存在的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70]: /images/20210511/17ad9608c0864b6185a28ecf0b6977e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 1]: /images/20210511/138844212efe406aa0eed6c7301ea9fa.png
[https_tech.meituan.com_2016_06_24_java-hashmap.html]: https://tech.meituan.com/2016/06/24/java-hashmap.html
[https_blog.csdn.net_bushanyantanzhe_article_details_79182880]: https://blog.csdn.net/bushanyantanzhe/article/details/79182880
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 2]: /images/20210511/bc81e3cff5c54ec0b41dd3ff561c94a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 3]: /images/20210511/c47dacd852594e6bbec07878b620a25c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 4]: /images/20210511/c0563ab101d749ceb0608dd3bb39ee63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 5]: /images/20210511/0b630b3f65b14e9a9d95ea6c751f34a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXhpYW83MjM4NDY_size_16_color_FFFFFF_t_70 6]: /images/20210511/436222113cce42c3940a2cbceb8eb506.png