Java性能 -- 并发容器

  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:数据量在 千万 级别,且存在 大量的增删改 操作
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章