并发场景下的Map容器

  1. 某电商系统需要统计销量TOP 10的商品，通常用哈希表来存储商品和销量的键值对，然后使用排序获取销量TOP 10的商品
  2. 并发场景下不能使用HashMap
    • JDK 1.7，在并发场景下使用HashMap会出现死循环，导致CPU使用率居高不下，而扩容是导致死循环的主要原因
    • JDK 1.8，虽然修复了HashMap扩容导致的死循环问题，但在高并发场景下，依然会有数据丢失和不准确的情况
  3. 为了保证Map容器的线程安全，Java实现了HashTable、ConcurrentHashMap、ConcurrentSkipListMap
    • HashTable、ConcurrentHashMap是基于HashMap实现的，适用于小数据量存取的场景
    • ConcurrentSkipListMap是基于TreeMap的设计原理实现的
      • ConcurrentSkipListMap是基于跳表实现的，而TreeMap是基于红黑树实现的
      • ConcurrentSkipListMap最大的特点是存取平均时间复杂度为O(log(n))，适用于大数据量存取的场景

HashTable / ConcurrentHashMap

  1. 在数据不断地写入和删除，且不存在数据累积以及数据排序的场景下，可以选用HashTable或者ConcurrentHashMap
  2. HashTable使用synchronized同步锁修饰了put、get、remove等方法
    • 在高并发场景下，读写操作都会存在大量锁竞争，给系统带来性能开销
  3. 相比于HashTable，ConcurrentHashMap在保证线程安全的基础上兼具了更好的并发性能
    • JDK 1.7中，ConcurrentHashMap使用了分段锁Segment减少了锁粒度，优化了锁的并发操作
    • JDK 1.8中，ConcurrentHashMap做了大量的改动，摒弃了Segment的概念
      • synchronized同步锁在JDK 1.6的性能已经得到了很大的提升
      • 在JDK 1.8中，重启了synchronized同步锁，通过synchronized实现Node作为锁粒度
      • put方法：没有哈希冲突时，使用CAS进行添加元素操作；有哈希冲突时，通过synchronized将链表锁定
  4. 在统计销量TOP 10的场景下，首选ConcurrentHashMap
  5. ConcurrentHashMap的整体性能要优于HashTable，但某些场景下ConcurrentHashMap不能替代HashTable
    • 例如强一致性的场景，ConcurrentHashMap的get、size等方法都没有加锁，ConcurrentHashMap是弱一致性的

ConcurrentHashMap / ConcurrentSkipListMap

  1. ConcurrentHashMap在数据量比较大的时候，链表会转换为红黑树
    • 红黑树在并发情况下，删除和插入过程有个平衡的过程，会涉及到大量结点，竞争锁资源的代价相对较高
    • 而跳跃表的操作针对局部，需要锁住的结点少，在并发场景下性能会更好一些
  2. 在非线程安全的Map中，基于红黑树实现的TreeMap在单线程中的性能表现并不比跳跃表差
  3. 因此
    • 在非线程安全的Map容器中，使用TreeMap来存取大数据
    • 在线程安全的Map容器中，使用ConcurrentSkipListMap来存取大数据

跳跃表

  1. 跳跃表是基于链表扩展实现的一种特殊链表，类似于树的实现
  2. 跳跃表不仅实现了横向链表，还实现了垂直方向的分层索引
  3. 一个跳跃表由若干层链表组成，每一层都实现了一个有序链表索引，只有最底层包含所有数据
    • 每一层由下往上依次通过一个指针指向上层相同值的元素，每层数据依次减少，到最顶层只会保留部分数据
  4. 跳跃表利用了空间换时间的方法来提高查询效率，程序总是从最顶层开始查询访问，通过判断元素值来缩小查询范围

初始化的跳跃表

查询Key值为9的结点

  1. 新增Key值为8的结点，首先新增一个结点（CAS操作）到最底层的链表中
  2. 根据概率算出level值，再根据level值新建索引层，最后链接索引层的新结点（CAS操作）
  1. 删除Key值为7的结点，首先找到待删除结点，将其value值设置为null
  2. 之后再向待删除结点的next位置新增一个标记结点，以便减少并发冲突
  3. 然后让待删除结点的前驱结点直接越过本身指向的待删除结点，直接指向后继结点，中间要被删除的结点最终会被垃圾回收
  4. 最后判断此次删除后是否导致某一索引层没有其他节点了，并视情况删除该层索引

使用场景

  1. HashTable：数据强一致性
  2. ConcurrentHashMap：（大部分情况）数据弱一致性
  3. ConcurrentSkipListMap：数据量在千万级别，且存在大量的增删改操作

并发场景下的List容器

  1. ArrayList并非线程安全容器，Java提供了线程安全容器：Vector、CopyOnWriteArrayList
  2. Vector是基于synchronized同步锁实现的线程安全，synchronized关键字几乎修饰了所有对外暴露的方法
    • 在读远大于写的操作场景下，Vector将会发生大量锁竞争，给系统带来性能开销
  3. CopyOnWriteArrayList：读操作无锁，写操作通过底层数组的新副本来实现，是一种读写分离的并发策略

小结

参考资料

  1. 老生常谈，HashMap的死循环
  2. Java性能调优实战