常用的数据结构


跳跃表

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

ConcurrentSkipListMap

ConcurrentSkipListMap是基于 TreeMap 的设计原理实现的,略有不同的是前者基于跳表实现,后者基于红黑树实现,ConcurrentSkipListMap 的特点是存取平均时间复杂度是**O(log(n)),适用于大数据量存取的场景,最常见的是基于跳跃表实现的数据量比较大的缓存。**

Hashtable

Hashtable 使用 Synchronized 同步锁修饰了 put、get、remove 等方法。

ConcurrentHashMap

该容器在数据量比较大的时候,链表会转换为红黑树。红黑树在并发情况下,删除和插入过程中有个平衡的过程,会牵涉到大量节点,因此竞争锁资源的代价相对比较高。
在 JDK1.7 中,ConcurrentHashMap 就使用了分段锁 Segment 减小了锁粒度,最终优化了锁的并发操作。
JDK1.8 中 ConcurrentHashMap 做了大量的改动,摒弃了 Segment 的概念。由于 Synchronized 锁在 Java6 之后的性能已经得到了很大的提升,所以在 JDK1.8 中,Java 重新启用了 Synchronized 同步锁,通过 Synchronized 实现**HashEntry**作为锁粒度。
与 JDK1.7 的 put 方法一样,JDK1.8 在添加元素时,在没有哈希冲突的情况下,会使用CAS 进行添加元素操作;如果有冲突,则通过 Synchronized 将链表锁定,再执行接下来的操作。

Vector

Vector 也是基于 Synchronized 同步锁实现的线程安全,Synchronized 关键字几乎修饰了所有对外暴露的方法,所以在读远大于写的操作场景中,Vector 将会发生大量锁竞争,从而给系统带来性能开销。

CopyOnWriteArrayList

CopyOnWriteArrayList是 java.util.concurrent 包提供的方法,它实现了读操作无锁,写操作则通过操作底层数组的新副本来实现,是一种读写分离的并发策略。


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
jvm 命令 jvm 命令
jstat S1C:年轻代中 From Survivor 的容量(单位 KB); S0U:年轻代中 To Survivor 目前已使用空间(单位 KB); S1U:年轻代中 From Survivor 目前已使用空间(单位 KB); EC:
2020-09-04 future
下一篇 
jvm参数 jvm参数
-XX:+DoEscapeAnalysis 开启逃逸分析(jdk1.8 默认开启,其它版本未测试)-XX:-DoEscapeAnalysis 关闭逃逸分析-XX:+EliminateLocks 开启锁消除(jdk1.8 默认开启,其它版本未
2020-09-04 future
  目录