9.9ConcurrentHashMap设计

目录介绍

  • 01.HashMap和HashTable困境
  • 02.ConcurrentHashMap底层知识点
  • 03.JDK1.6和JDK1.8区分
  • 04.一些重要概念介绍
  • 05.ConcurrentHashMap 应用场景

01.HashMap和HashTable困境

1.1 效率低下的HashTable容器

  • HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。
    • 因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。
    • 如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。
  • Java中其实已经有了HashTable这个线程安全的Map，但是他是通过对整个table使用synchronized来保证线程安全的，当有多个线程对HashTable进行读写的时候，每次只能有一个线程会获取到HashTable的对象锁，别的只能处于等待状态，所以在高并发的情况下，它的效率是比较低的。

1.2 线程不安全的HashMap

  • HashMap是我们平时开发过程中用的比较多的集合，但它是非线程安全的，在涉及到多线程并发的情况，进行put操作有可能会引起死循环，导致CPU利用率接近100%。
    final HashMap<String, String> map = new HashMap<String, String>(2);
for (int i = 0; i < 10000; i++) {
    new Thread(new Runnable() {
        @Override
        public void run() {
            map.put(UUID.randomUUID().toString(), "");
        }
    }).start();
}
  • 解决方案有Hashtable和Collections.synchronizedMap(hashMap)
    • 不过这两个方案基本上是对读写进行加锁操作，一个线程在读写元素，其余线程必须等待，性能可想而知。

02.ConcurrentHashMap底层知识点

  • 并发安全的ConcurrentHashMap，它的实现是依赖于 Java 内存模型，所以我们在了解 ConcurrentHashMap 的之前必须了解一些底层的知识：
    • 1.java内存模型
    • 2.java中的CAS
    • 3.AbstractQueuedSynchronizer
    • 4.ReentrantLock

03.JDK1.6和JDK1.8区分

  • JDK1.6分析
    • ConcurrentHashMap采用 分段锁的机制，实现并发的更新操作，底层采用数组+链表+红黑树的存储结构。
    • 其包含两个核心静态内部类 Segment和HashEntry。
      • 1.Segment继承ReentrantLock用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶。
      • 2.HashEntry 用来封装映射表的键 / 值对；
      • 3.每个桶是由若干个 HashEntry 对象链接起来的链表。
    • 一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组，下面我们通过一个图来演示一下 ConcurrentHashMap 的结构：
  • JDK1.8分析
    • 1.8的实现已经抛弃了Segment分段锁机制，利用CAS+Synchronized来保证并发更新的安全，底层依然采用数组+链表+红黑树的存储结构。

04.一些重要概念介绍

  • 在开始之前，有些重要的概念需要介绍一下：
  • 1.table：默认为null，初始化发生在第一次插入操作，默认大小为16的数组，用来存储Node节点数据，扩容时大小总是2的幂次方。
  • 2.nextTable：默认为null，扩容时新生成的数组，其大小为原数组的两倍。
  • 3.sizeCtl
    • 默认为0，用来控制table的初始化和扩容操作，具体应用在后续会体现出来。
    • **-1 **代表table正在初始化
    • **-N **表示有N-1个线程正在进行扩容操作
    • 其余情况：
      • 1、如果table未初始化，表示table需要初始化的大小。
      • 2、如果table初始化完成，表示table的容量，默认是table大小的0.75倍，居然用这个公式算0.75（n - (n >>> 2)）。
  • 4.Node
    • 保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。
    class Node<K,V> implements Map.Entry<K,V> {
 final int hash;
 final K key;
 volatile V val;
 volatile Node<K,V> next;
 ... 省略部分代码
}
  • 5.ForwardingNode
    • 一个特殊的Node节点，hash值为-1，其中存储nextTable的引用。只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当前节点为null或则已经被移动。
    final class ForwardingNode<K,V> extends Node<K,V> {
  final Node<K,V>[] nextTable;
  ForwardingNode(Node<K,V>[] tab) {
      super(MOVED, null, null, null);
      this.nextTable = tab;
  }
}

05.ConcurrentHashMap应用场景

  • 当有一个大数组时需要在多个线程共享时就可以考虑是否把它给分层多个节点了，避免大锁。并可以考虑通过hash算法进行一些模块定位。
  • 其实不止用于线程，当设计数据表的事务时（事务某种意义上也是同步机制的体现），可以把一个表看成一个需要同步的数组，如果操作的表数据太多时就可以考虑事务分离了（这也是为什么要避免大表的出现），比如把数据进行字段拆分，水平分表等.

06.锁分段技术

  • HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁，在ConcurrentHashMap内部，段数组是final的，并且其成员变量实际上也是final的，但是，仅仅是将数组声明为final的并不保证数组成员也是final的，这需要实现上的保证。这可以确保不会出现死锁，因为获得锁的顺序是固定的。
  • ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。 image
贡献者: yangchong211