HashMap的实现原理、JDK1.7和JDK1.8的对比以及死锁问题

妖狐艹你老母 2021-09-30 15:58 358阅读 0赞

# 个人总结： #

HashMap实现通过数组加链表，JDK1.8在计算hashcode值时进行了优化，同时也把链表进行升级为红黑二叉树加快结点遍历速度，程序有时执行HashMap的get()方法时会出现卡死（死锁发生）问题，原因是因为扩容时链表部分的指针产生了循环指向引用，导致执行get()遍历到此结点时发生死循环，JDK1.7在扩容时是直接头插法倒叙排一遍，JDK1.8是打乱顺序排一遍，但是如果恰好打乱后的数据某一段顺序和之前一样，还是会出现死锁问题！

# 实际使用： #

平时在Service层中使用，一般都是直接在方法中new HashMap()，不会产生问题，对于一些场景，比如写一个工具类或者一个单例bean注入IOC，然后在其他各个场景使用这个类的同一个集合，就会有线程安全性问题，所以一般都是ConCurrentHashMap作为多线程下的集合。

\-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

###    1、HashMap是存储键值对的数据结构； ###

### 2、几个重要参数：  ###

容量，默认为16  
负载因子，默认为0.75  
扩容极限（暂不十分了解）  
说明：当我们不指定任何参数创建HashMap时，就会创建一个容量为16，负载因子为0.75的HashMap，当HashMap中实际的元素个数大于等于16\*0.75=12时，会触发HashMap的resize操作，HashMap的容量会自动扩展一倍。负载因子0.75被证明是性能比较好的取值，通常不会修改，那么只有初始同理会导致频繁扩容的行为，这是非常耗费资源的操作，所以如果能够事先估计出容器所需要存储的容量，就在初始化时修改默认值，即new HashMap(int initialCapacity)。

几个重要函数：hashCode() 和 equal()

hashCode()，计算key值对应的哈希值，然后确定存储的数组索引；  
equal()，确定存储索引后，在索引处单向链表上遍历比较key值，看是否已经存储。  
说明：这两个函数对实现HashMap的精确性和正确性至关重要。

### 3、jdk1.8 HashMap的底层实现：Entry数组 + 链表 + 红黑树。 ###

首先，在HashMap类中有一个Entry的内部类，这个Entry类包含了key-value作为实例变量。没当向HashMap中存放k-v对时，都会为其实例化一个Entry对象，则个Entry对象就会存储Entry数组中。而Entry在数组中的具体位置，会根据key的HashCode()方法计算出的哈希值来决定。如果哈希算法设计的足够好，是不会发生碰撞冲突的，但实际中肯定没有这么理想，所以在每个索引处，会有一个单向链表，来存储相同索引的Entry对象。

然后，当调用put方法向哈希表中存储键值对时，首先计算key的hashcode，定位到合适的数组索引，然后在该索引上的单向链表进行遍历，用equals函数比较key是否存在。如果存在，则新的value值覆盖原来的value值；如果不存在，则将新的Entry对象插入到链表头部。且当链表长度大于某个值（可能是8）时，链表会变为红黑树，链表的查询效率为O(n)，红黑树的查询效率为O(lgn)，可见后者的效率更高。

最后，当需要取出一个Entry对象时，也是根据key的hashCode值来找到其存储位置，直接取出该Entry。

### 4、jdk1.7 HashMap的resize在多线程环境下，可能会产生条件竞争和死循环。 ###

如果两个线程都发现HashMap需要重新调整大小，那么它们会同时试着去调整大小。在调整大小时，存储在链表中的元素的次序会反过来，因为在放入新的位置时，HashMap会将Entry对象不断的插入链表的头部。插入头部也主要是为了防止尾部遍历，否则这对key的HashCode相同的Entry每次添加还要定位到尾节点。如果条件竞争发送了，可能会出现环形链表，之后当我们get(key)操作时，就有可能发生死循环。形成循环的原因可参考连接http://www.cnblogs.com/andy-zhou/p/5402984.html。

此外，虽然HashTable使用synchronized来保证线程安全，但是它会锁住整个哈希表，在线程竞争激烈的情况下，效率非常低，所以并不在多线程中经常使用HashTable。

### 5、为什么String, Interger这样的wrapper类适合作为键？ ###

因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

下面让我们正式开始讲解jdk1.7 HashMap的死循环与jdk1.8 HashMap的优化

### 一、jdk1.7 HashMap在进行put操作时使用的是链表头部插入法 ###

addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是 HashMap 提供的一个包访问权限的方法，代码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
        // 获取指定 bucketIndex 索引处的 Entry 
        Entry<K,V> e = table[bucketIndex];
        // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry 
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        // 如果 Map 中的 key-value 对的数量超过了极限
        if (size++ >= threshold)
        // 把 table 对象的长度扩充到原来的2倍。
            resize(2 * table.length);
    }

###    二、jdk1.7 HashMap在进行resize扩容时使用的也是链表头部插入法 ###

扩容实现

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        ...
     
        Entry[] newTable = new Entry[newCapacity];
        ...
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

这里会新建一个更大的数组，并通过transfer方法，移动元素。

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

transfer()使用的头插法关键代码是：

e.next = newTable\[i\]; newTable\[i\] = e;

transfer方法的实现逻辑是：

1、原来的table进行两层遍历，外层遍历table，内层遍历table索引处的链表，从链头遍历到链尾。

2、从原来的链表取出头节点e,计算e的hash值以及在新的table中的bucketIndex值i。newTable\[i\]指向数组下标对应的元素，也就是指向数组bucketIndex对应链表的头节点。用e.next指向原先的头节点引用newTable\[i\]，newTable\[i\]再指向e，把e作为新的头节点。

3、不要忘了我们要不断从原来的链表取出头节点e，直到遍历到链尾为止。所以我们要在2操作开始之前， Entry<K,V> next = e.next; 用next变量指向原来链表的下一个头节点，在2操作执行完后， e = next;使e重新成为原来链表的头节点。

###    案例分析 ###

假设HashMap初始化大小为4，插入个3节点，不巧的是，这3个节点都hash到同一个位置，如果按照默认的负载因子的话，插入第3个节点就会扩容，为了验证效果，假设负载因子是1.

![70][]  
对HashMap依次插入c、b、a三个节点，假设3个节点都hash到同一个位置，则如上图所示。  
插入第4个节点时，发生rehash。

![70 1][]  
在新的table和链表中，a、b、c三个节点在链表中的顺序如上。注意，顺序与原来的链表是反过来的。

### 三、jdk1.7 HashMap在多线程下扩容时可能 产生死循环 ###

接着上面的案例，假如有2个线程：线程1和线程2，线程1在执行扩容时如上图所示，在newTable\[7\]处依次插入了a、b、c三个节点，这时切换到线程2执行扩容插入节点操作。若线程2此时只进行到了插入b节点的操作，

Entry<K,V> next = e.next;  
int i = indexFor(e.hash, newCapacity);  
e.next = newTable\[i\];  
newTable\[i\] = e;    <——  假设线程2刚执行完这行代码，当前节点e是b节点

e = next;

则如下图所示：

![20180523163617870][]

ps:上图如果拆分2个图则很容易理解，拆分第一个图为线程 1插入了a、b、c三个节点，第二个图为线程2插入了a、b节点。

两图结合，即为上图。

若在单线程下，线程2接着应该插入c节点，但是因为线程1的缘故，b的下一个节点不是c节点，反而是a节点

Entry<K,V> next = e.next;  
int i = indexFor(e.hash, newCapacity);  
e.next = newTable\[i\];   <——  线程2执行这行代码，当前节点是a， newTable\[i\] 指向节点b，那就是把a的next指向了节点b，这样a和b就相互引用了，形成了一个环；  
newTable\[i\] = e;    <—— 线程2执行这行代码， newTable\[i\] 指向节点a  
e = next;

如下图所示：

![70 2][]

### 四、jdk1.8 HashMap在扩容时保持了原来链表中的顺序 ###

JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞，如下:

1 final Node<K,V>[] resize() {
     2     Node<K,V>[] oldTab = table;
     3     int oldCap = (oldTab == null) ? 0 : oldTab.length;
     4     int oldThr = threshold;
     5     int newCap, newThr = 0;
     6     if (oldCap > 0) {
     7         // 超过最大值就不再扩充了，就只好随你碰撞去吧
     8         if (oldCap >= MAXIMUM_CAPACITY) {
     9             threshold = Integer.MAX_VALUE;
    10             return oldTab;
    11         }
    12         // 没超过最大值，就扩充为原来的2倍
    13         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    14                  oldCap >= DEFAULT_INITIAL_CAPACITY)
    15             newThr = oldThr << 1; // double threshold
    16     }
    17     else if (oldThr > 0) // initial capacity was placed in threshold
    18         newCap = oldThr;
    19     else {               // zero initial threshold signifies using defaults
    20         newCap = DEFAULT_INITIAL_CAPACITY;
    21         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    22     }
    23     // 计算新的resize上限
    24     if (newThr == 0) {
    25 
    26         float ft = (float)newCap * loadFactor;
    27         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    28                   (int)ft : Integer.MAX_VALUE);
    29     }
    30     threshold = newThr;
    31     @SuppressWarnings({"rawtypes"，"unchecked"})
    32         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    33     table = newTab;
    34     if (oldTab != null) {
    35         // 把每个bucket都移动到新的buckets中
    36         for (int j = 0; j < oldCap; ++j) {
    37             Node<K,V> e;
    38             if ((e = oldTab[j]) != null) {
    39                 oldTab[j] = null;
    40                 if (e.next == null)
    41                     newTab[e.hash & (newCap - 1)] = e;
    42                 else if (e instanceof TreeNode)
    43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    44                 else { // 链表优化重hash的代码块
    45                     Node<K,V> loHead = null, loTail = null;
    46                     Node<K,V> hiHead = null, hiTail = null;
    47                     Node<K,V> next;
    48                     do {
    49                         next = e.next;
    50                         // 原索引
    51                         if ((e.hash & oldCap) == 0) {
    52                             if (loTail == null)
    53                                 loHead = e;
    54                             else
    55                                 loTail.next = e;
    56                             loTail = e;
    57                         }
    58                         // 原索引+oldCap
    59                         else {
    60                             if (hiTail == null)
    61                                 hiHead = e;
    62                             else
    63                                 hiTail.next = e;
    64                             hiTail = e;
    65                         }
    66                     } while ((e = next) != null);
    67                     // 原索引放到bucket里
    68                     if (loTail != null) {
    69                         loTail.next = null;
    70                         newTab[j] = loHead;
    71                     }
    72                     // 原索引+oldCap放到bucket里
    73                     if (hiTail != null) {
    74                         hiTail.next = null;
    75                         newTab[j + oldCap] = hiHead;
    76                     }
    77                 }
    78             }
    79         }
    80     }
    81     return newTab;
    82 }

\---------------------   
版权声明：本文为CSDN博主「zhifeng687」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/qq\_26222859/article/details/46124265

[70]: /images/20210720/418deb29863e428298bef5231d959f22.png
[70 1]: /images/20210720/b7b0029a24a14d9d9400dca25a8a692c.png
[20180523163617870]: /images/20210720/21b7d299d08f4623a5395d184f55ceab.png
[70 2]: /images/20210720/f6c3bf7e881e467cb204795b4c261e99.png