[一 JDK 提供的并发容器总结]
JDK 提供的这些容器大部分在 java.util.concurrent
包中。
- ConcurrentHashMap: 线程安全的 HashMap
- CopyOnWriteArrayList: 线程安全的 List,在读多写少的场合性能非常好,远远好于 Vector.
- ConcurrentLinkedQueue: 高效的并发队列,使用链表实现。可以看做一个线程安全的 LinkedList,这是一个非阻塞队列。
优秀的判断力来自经验,但经验来自于错误的判断。
转自:https://zhuanlan.zhihu.com/p/21673805
HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的结构实现和功能原理。
HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的Java集合之一。
JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树),以减少搜索时间,具体可以参考 treeifyBin
方法。
LinkedList是一个实现了List接口和Deque接口的双端链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作,另外它实现了Deque接口,使得LinkedList类也具有队列的特性; LinkedList不是线程安全的,如果想使LinkedList变成线程安全的,可以调用静态类Collections类中的synchronizedList方法:
ConcurrentHshMap利用CAS+Synchronized来保证并发更新安全,底层依然使用数组+链表+红黑树的存储结构
* -1 代表table正在初始化
* -N 正有N-1个线程正在进行扩容操作
* N 下一次需要扩容的临界值,与HashMap中的临界值一样
final int hash;
final K key;
volatile Node<K,V> next;
ForwardingNode
final Node<K,V> [] nextTable;
super (-1,NULL,NULL,NULL,NULL) hash值为-1其它为NULL
// ForwardingNode 只在扩容是发挥作用,负责表示当前节点以被copy走了。
计算key的hashcode在hash得出index数组中存放的位置
检查数组是否初始化若未初始化则进行初始化
1若table[index]==null ,该节点为空 ,利用CAS操作插入数据
2若table[index]!=null ,该位置已有节点,发生碰撞
a . 检查该节点的hash值是否为-1 ,若为-1则说明有线程正在进行扩容操作 ,调用helpTransfer帮助其扩容
b . 该节点hash值不为-1 ,锁定hash值相同的链表头结点 ,进行插入或者更新操作,链表过长变为红黑树
CAS操作把sizeCtl变为-1,表示正在进行初始化 确保只有一个线程进行初始化。
创建nextTable 数组大小为table2倍 ,容量为原来1.5倍
调用transfer方法 把数据复制到新数组
1 在工作内存中每次使用变量必须从主内存刷新最新的值
2 每次修改后必须立刻同步会主内存
3 禁止指令从排序
compare and swap 比较并交换 有三个参数 1内存中的值 2预期的值 3 改变后的值
乐观锁的一种体现 先操作后检查。非阻塞式同步
如何保证操作和检测两个步骤具备原子性,如果用锁那就是去意义了
靠硬件来完成原子性,这两个操作通过一条处理器指令来完成保证了原子性。
缺点:造成ABA问题,初次读值为A,并且在准备赋值时检测到它仍为A,也不能保证它没有变过,可能在这段期间内变为B
版本号来解决ABA问题,AtomicStampedReference 给变量加上版本号改变一次版本加一
通过检查版本号来确定变量改变过没有。
版本号的原理在MySQL innodb引擎也有体现 innodb 通过MVCC多版本并发实现高并发。
作者:聚在散里
链接:https://www.jianshu.com/p/1dc086c2cf83
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
ArrayList 的底层是数组队列,相当于动态数组。与 Java 中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用ensureCapacity
操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。