Java性能 -- 并发容器

并发场景下的Map容器

  1. 某电商系统需要统计销量TOP 10的商品,通常用哈希表来存储商品和销量的键值对,然后使用排序获取销量TOP 10的商品
  2. 并发场景下不能使用HashMap
    • JDK 1.7,在并发场景下使用HashMap会出现死循环,导致CPU使用率居高不下,而扩容是导致死循环的主要原因
    • JDK 1.8,虽然修复了HashMap扩容导致的死循环问题,但在高并发场景下,依然会有数据丢失不准确的情况
  3. 为了保证Map容器的线程安全,Java实现了HashTableConcurrentHashMapConcurrentSkipListMap
    • 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提供了线程安全容器:VectorCopyOnWriteArrayList
  2. Vector是基于synchronized同步锁实现的线程安全,synchronized关键字几乎修饰了所有对外暴露的方法
    • 读远大于写的操作场景下,Vector将会发生大量锁竞争,给系统带来性能开销
  3. CopyOnWriteArrayList:读操作无锁,写操作通过底层数组的新副本来实现,是一种读写分离的并发策略

小结

参考资料

  1. 老生常谈,HashMap的死循环
0%