[Map系列]HashMap、ConCurrentHashMap、LinkedHashMap深入理解

àì夳堔傛蜴生んèń 2022-05-11 12:33 329阅读 0赞

**自己思考+看源码+其他博客中整理，面试的时候答这一套还是很容易过关，但是TreeMap和weakHashMap还没整理，后面整理好了再发。**

### HashMap、ConcurrentHashMap、LinkedHashMap理解 ###

#### 一、HashMap ####

##### 1.底层是数组和链表 #####

![image][]

##### 2.参数 #####

容量：默认大小为16  
负载因子 ：0.75,即当 HashMap 的 size > 16\*0.75 时就会发生扩容(容量和负载因子都可以自由调整)。

##### 3.put() #####

1.  首先会将传入的 Key 做 hash 运算计算出 hashcode,
2.  然后根据数组长度取模计算出在数组中的 index 下标。

理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap数组的话
    2进制32位带符号的int表值范围从-2147483648~2147483648，前后加起来大概40亿的映射空间
    只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
    但问题是一个40亿长度的数组，内存是放不下的。HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。
    用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。源码中模运算是在这个indexFor( )函数里完成的。
      bucketIndex = indexFor(hash, table.length);

1.  所以存在不同的key计算得到的index相同，这种情况可以利用链表来解决，HashMap 会在 table\[index\]处形成链表，采用头插法将数据插入到链表中。
2.  在 JDK1.8 中对 HashMap 进行了优化： 当 hash碰撞之后写入链表的长度超过了阈值(默认为8)，链表将会转换为红黑树。假设 hash 冲突非常严重，一个数组后面接了很长的链表，此时重新的时间复杂度就是 O(n) 。  
    如果是红黑树，时间复杂度就是 O(logn) 。大大提高了查询效率。

##### 4.get() #####

get 和 put 类似，也是将传入的 Key 计算出 index ，如果该位置上是一个链表就需要遍历整个链表，通过 key.equals(k) 来找到对应的元素。

##### 5.线程不安全–死链 #####

1.  多线程put操作后，get操作导致死循环。
2.  多线程put非null元素后，get操作得到null值。
3.  多线程put操作，导致元素丢失。

举例：
    AB线程同时对Map进行操作：
    
     do {                   
         Entry<K,V> next = e.next;
         int i = indexFor(e.hash, newCapacity);
         e.next = newTable[i];
         newTable[i] = e;
        e = next;
        } while (e != null);
        
    A执行到链关系 3->7->5,执行到Entry<K,V> next = e.next;被cpu调度挂起
    B对Map进行put，并且扩充了数组空间
       导致关系变化成
       7->3
       5
    此时A程序被唤起，同样进行put，并且扩充了数组空间
      现在关系是7->3 ,继续Entry<K,V> next = e.next，3原来存的next是7
      1、e=next=7;
      2、e!=null,循环继续
      3、next=e.next=3
      4、e.next 7的next指向3
      导致死链

![image][image 1]

A线程执行后

![image][image 2]

#### 线程不安全 ->hashtable ####

1.  HashTable是可以序列化的。是线程安全的。
2.  HashTable之所以是线程安全的，是因为方法上都加了synchronized关键字。
3.  HashTable中hash数组默认大小是11，增加的方式是old\*2+1
4.  Hashtable既不支持Null key也不支持Null value。Hashtable的put()方法的注释中有说明。
    
    public synchronized V get(Object key) \{  
    Entry<?,?> tab\[\] = table;  
    int hash = key.hashCode();  
    int index = (hash & 0x7FFFFFFF) % tab.length;  
    for (Entry<?,?> e = tab\[index\] ; e != null ; e = e.next) \{  
    if ((e.hash == hash) && e.key.equals(key)) \{  
    return (V)e.value;  
    \}  
    \}  
    return null;  
    \}

**缺点**：  
HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法，其他线程也访问HashTable的同步方法时，会进入阻塞或轮询状态。如线程1使用put进行元素添加，线程2不但不能使用put方法添加元素，也不能使用get方法来获取元素，所以竞争越激烈效率越低。

#### ConcurrentMap ####

由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。

![image][image 3]

**Segment 数组**，存放数据时首先需要定位到具体的 Segment 中。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
       private static final long serialVersionUID = 2249069246763182397L;
       
       // 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
       transient volatile HashEntry<K,V>[] table;
       transient int count;
       transient int modCount;
       transient int threshold;
       final float loadFactor;
       }

**HashEntry**

和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。

**原理**

ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

**put**

首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put。

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
    }

1.  尝试自旋获取锁。
2.  如果重试的次数达到了 MAX\_SCAN\_RETRIES 则改为阻塞锁获取，保证能获取成功。
3.  将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
4.  遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
5.  不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
6.  最后会解除在 1 中所获取当前 Segment 的锁。

**get()**

1.  只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。
2.  由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
3.  ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。

**1.8优化**

1.  抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
2.  也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。
    
        static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        
        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }

**put**( )  
![image][image 4]

*  根据 key 计算出 hashcode
 *  判断是否需要进行初始化。
 *  f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
 *  如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
 *  如果都不满足，则利用 synchronized 锁写入数据。
 *  如果数量大于 TREEIFY\_THRESHOLD 则要转换为红黑树。

**get 方法**

![image][image 5]

1.  根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
2.  如果是红黑树那就按照树的方式获取值。
3.  不满足那就按照链表的方式遍历获取值。

### LinkedHashMap ###

*  HashMap 是一个无序的 Map，因为每次根据 key 的 hashcode 映射到Entry数组上，所以遍历出来的顺序并不是写入的顺序。
 *  因此 JDK 推出一个基于 HashMap 但具有顺序的 LinkedHashMap 来解决有排序需求的场景。
 *  LinkedHashMap继承于HashMap 所以一些 HashMap 存在的问题 LinkedHashMap也会存在，比如不支持并发等  
    **实现**
 *  hashcode实现唯一，双向链表实现有序
 *  LinkedHashMap 的排序方式有两种：
    
    1.  根据写入顺序排序。
    2.  根据访问顺序排序。

**顺序访问**

每次 get 都会将访问的值移动到链表末尾，这样重复操作就能得到一个按照访问顺序排序的链表。

![image][image 6]

public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

accessOrder 成员变量，默认是 false，默认按照插入顺序排序，为 true 时按照访问顺序排序

**put**()重写方法：recordAccess()

//就是判断是否是根据访问顺序排序，如果是则需要将当前这个 Entry 移动到链表的末尾
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

**put()重写方法：recordAccess**  
public V get(Object key) \{  
Entry<K,V> e = (Entry<K,V>)getEntry(key);  
if (e == null)  
return null;

//多了一个判断是否是按照访问顺序排序，是则将当前的 Entry 移动到链表头部。   
        e.recordAccess(this);
        return e.value;
    }
    
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            
            //删除
            remove();
            //添加到头部
            addBefore(lm.header);
        }
    }

[image]: https://ws1.sinaimg.cn/large/006tNc79gy1ftiv16vu4aj30i30k4q47.jpg
[image 1]: /images/20220505/4e749b63fbc841e8b6b14dadb79fa120.png
[image 2]: /images/20220505/738525852c4a489cb8877bd0239aa93f.png
[image 3]: https://ws4.sinaimg.cn/large/006tNc79gy1ftj0evlsrgj30dw073gm2.jpg
[image 4]: https://ws3.sinaimg.cn/large/006tNc79gy1fthrz8jlo8j30oc0rbte3.jpg
[image 5]: https://ws1.sinaimg.cn/large/006tNc79gy1fthsnp2f35j30o409hwg7.jpg
[image 6]: https://camo.githubusercontent.com/b4208f2e112aad3921f366fec61e1a34a5823064/68747470733a2f2f7773312e73696e61696d672e636e2f6c617267652f303036744b665463677931666f64676777633532336a33307a61306e3477676a2e6a7067