2020-05-21—HashMap及concurrentHashMap原理分析

HashMap及concurrentHashMap原理分析

一、1.7HashMap原理分析

打开源码找到put方法中的addEntry()方法，点进去(下面我贴出主要部分源码)。

//addEntry方法    
void addEntry(int hash, K key, V value, int bucketIndex) {
  //判断size大小，与阈值大小，size大就调用扩容方法
  if ((size >= threshold) && (null != table[bucketIndex])) {
    //2倍扩充容量
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }
  createEntry(hash, key, value, bucketIndex);
}

//resize扩容方法
void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return;
  }

  Entry[] newTable = new Entry[newCapacity];
  //主要扩容的方法
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  table = newTable;
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
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;
    }
  }
}

HashMap一次扩容的过程：

1、取当前table的2倍作为新table的大小
2、根据算出的新table的大小new出一个新的Entry数组来，名为newTable
3、轮询原table的每一个位置，将每个位置上连接的Entry，算出在新table上的位置，并以链表形式连接
4、原table上的所有Entry全部轮询完毕之后，意味着原table上面的所有Entry已经移到了新的table上，HashMap中的table指向newTable

下面进行死循环分析

按照源码中的for循环：

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;
    }
  }

正常的单线程扩容过程应该这样（注意扩容时，采用头插法进行）

那么在并发环境下呢？情况就这样了（假如线程1执行一半被阻塞，线程2去执行扩容）：

线程2执行完后，线程1被CPU调度回来执行：
第一步：

第二步：

第三步：

          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;
            }
第四步:
执行到
e.next = newTable[i]; 
newTable[i] = e;  
后，线程1的table变成如果所示，循环链表产生！

这时候,e = next 导致 e = null，while条件不满足，循环终止。

二、ConcurrentHashMap原理分析

区别：除了Map系列应该有的线程安全的get，put等方法外，ConcurrentHashMap还提供了一个在并发下比较有用的方法 putIfAbsent

//putIfAbsent方法块
/**
     * {@inheritDoc}
     *
     * @return the previous value associated with the specified key,
                返回 与指定键key关联的先前value值
     *         or <tt>null</tt> if there was no mapping for the key
                或 null （如果键没有映射）
     * @throws NullPointerException if the specified key or value is null
     */
    @SuppressWarnings("unchecked")
    public V putIfAbsent(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
             (segments, (j << SSHIFT) + SBASE)) == null)
            s = ensureSegment(j);
        return s.put(key, hash, value, true);
    }

从源码明显可以看出，如果传入key对应的value已经存在，就返回存在的value，不进行替换。如果不存在，就添加key和value，返回null。

JDK1.7中的ConcurrentHashMap

JDK1.8中的ConcurrentHashMap

最后附上常见的这块的面试题？

1、HashMap 和 HashTable 有什么区别？
①、HashMap 是线程不安全的，HashTable 是线程安全的；
②、由于线程安全，所以 HashTable 的效率比不上 HashMap；
③、HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null， 而 HashTable 不允许；
④、HashMap 默认初始化数组的大小为 16，HashTable 为 11，前者扩容时， 扩大两倍，后者扩大两倍+1；
⑤、HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

2、Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？
ConcurrentHashMap 类（是 Java 并发包 java.util.concurrent 中提供的一 个线程安全且高效的 HashMap 实现）。
HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）； 而针对 ConcurrentHashMap，在 JDK 1.7 中采用分段锁(Segment内部类)的方式；JDK 1.8 中 直接采用了 CAS（无锁算法）+ synchronized，也采用分段锁的方式并大大缩小了 锁的粒度。

3、HashMap & ConcurrentHashMap 的区别？
除了加锁，原理上无太大区别。 另外，HashMap 的键值对允许有 null，但是 ConCurrentHashMap 都不允许。 在数据结构上，红黑树相关的节点类

4、为什么 ConcurrentHashMap 比 HashTable 效率要高？
HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程 竞争一把锁，容易阻塞； ConcurrentHashMap JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一 个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基 于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结 点）（实现 Map.Entry<K,V>）。锁粒度降低了。

5、ConcurrentHashMap 锁机制具体分析（JDK 1.7 VS JDK 1.8）？
JDK 1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表 的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。
①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶；
②、HashEntry 用来封装映射表的键-值对；
③、每个桶是由若干个 HashEntry 对象链接起来的链表。 JDK 1.8 中，采用 Node + CAS + Synchronized 来保证并发安全。取消类 Segment，直接用 table 数组存储键值对；当 HashEntry 对象组成的链表长度超 过 TREEIFY_THRESHOLD 时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。

6、ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？
1、JVM 开发团队在 1.8 中对 synchronized 做了大量性能上的优化，而且基 于 JVM 的 synchronized 优化空间更大，更加自然。
2、在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

7、1.8下ConcurrentHashMap 简单介绍？
①、重要的常量： private transient volatile int sizeCtl; 当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容； 当为 0 时，表示 table 还没有初始化； 当为其他正数时，表示初始化或者下一次进行扩容的大小。
②、数据结构： Node 是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据； TreeNode 继承 Node，但是数据结构换成了二叉树结构，是红黑树的存储 结构，用于红黑树中存储数据； TreeBin 是封装 TreeNode 的容器，提供转换红黑树的一些条件和锁的控制。
③、存储对象时（put() 方法）： 1.如果没有初始化，就调用 initTable() 方法来进行初始化； 2.如果没有 hash 冲突就直接 CAS 无锁插入； 3.如果需要扩容，就先进行扩容； 4.如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形 式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入； 5.如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一 次进入循环 6.如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容。
**④、扩容方法 transfer()**：默认容量为 16，扩容时，容量变为原来的两倍。 helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高。
⑤、获取对象时（get()方法）：
1.计算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；
2.如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法， 查找该结点，匹配就返回；
3.以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null。

8、ConcurrentHashMap 的并发度是什么？
1.7 中程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的 最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时， ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并发度（假如 用户设置并发度为 17，实际并发度则为 32）。
1.8 中并发度则无太大的实际意义了，主要用处就是当设置的初始容量小于 并发度，将初始容量提升至并发度大小。

9、synchronized 底层实现原理
synchronized (this)原理：涉及两条指令：monitorenter，monitorexit；再说同 步方法，从同步方法反编译的结果来看，方法的同步并没有通过指令 monitorenter 和 monitorexit 来实现，相对于普通方法，其常量池中多了 ACC_SYNCHRONIZED 标示符。
JVM 就是根据该标示符来实现方法的同步的：当方法被调用时，调用指令将 会检查方法的 ACC_SYNCHRONIZED 访问标志是否被设置，如果设置了，执行线 程将先获取 monitor，获取成功之后才能执行方法体，方法执行完后再释放 monitor。在方法执行期间，其他任何线程都无法再获得同一个 monitor 对象。 注意，这个问题可能会接着追问，java 对象头信息，偏向锁，轻量锁，重量 级锁及其他们相互间转化。