jdk1.7 分段锁
1、HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁
2、假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术
a、首先将数据分成一段一段的存储
b、然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问
c、有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁
d、在ConcurrentHashMap内部，段数组是final的，并且其成员变量实际上也是final的，但是，仅仅是将数组声明为final的并不保证数组成员也是final的，这需要实现上的保证。这可以确保不会出现死锁，因为获得锁的顺序是固定的。
3、ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成
4、Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色
5、HashEntry则用于存储键值对数据
6、一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构
7、一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。
jdk1.8 concurrentHashMap原理分析
1.8版本的ConcurrentHashMap的实现与1.7版本有很大的差别，放弃了段锁的概念，借鉴了HashMap的数据结构：数组＋链表＋红黑树
-
ConcurrentHashMap不接受nullkey和nullvalue
-
数据结构：数组＋链表＋红黑树
-
并发原理：cas乐观锁+synchronized锁
-
加锁对象：数组每个位置的头节点
concurrentHashMap数据结构
ConcurrentHashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树是为了提高查找效率
构造函数
1、对于构造函数而言，会根据输入的initialCapacity的大小来确定一个最小的且大于等于initialCapacity大小的2的n次幂，如initialCapacity为15，则sizeCtl为16，若initialCapacity为16，则sizeCtl为16
2、若initialCapacity大小超过了允许的最大值，则sizeCtl为最大值
3、值得注意的是，构造函数中的concurrencyLevel参数已经在JDK1.8中的意义发生了很大的变化，其并不代表所允许的并发数 只是用来确定sizeCtl大小
4、在JDK1.8中的并发控制都是针对具体的桶而言，即有多少个桶就可以允许多少个并发数。
- ConcurrentHashMap()
该构造函数用于创建一个带有默认初始容量 (16)、加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射
- ConcurrentHashMap(int)
该构造函数用于创建一个带有指定初始容量、默认加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射
- ConcurrentHashMap(Map<? extends K, ? extends V>)
该构造函数用于构造一个与给定映射具有相同映射关系的新映射
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
// 将集合m的元素全部放入
putAll(m);
}- ConcurrentHashMap(int, float)
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}- ConcurrentHashMap(int, float, int)
putVal函数
V putVal(K key, V value, boolean onlyIfAbsent)
put函数底层调用了putVal进行数据的插入，对于putVal函数的流程大体如下。
① 判断存储的key、value是否为空，若为空，则抛出异常，否则，进入步骤②
② 计算key的hash值，随后进入无限循环，该无限循环可以确保成功插入数据，若table表为空或者长度为0，则初始化table表，否则，进入步骤③
③ 根据key的hash值取出table表中的结点元素，若取出的结点为空（该桶为空），则使用CAS将key、value、hash值生成的结点放入桶中。否则，进入步骤④
④ 若该结点的的hash值为MOVED，则对该桶中的结点进行转移，否则，进入步骤⑤
⑤ 对桶中的第一个结点（即table表中的结点）进行加锁，对该桶进行遍历，桶中的结点的hash值与key值与给定的hash值和key值相等，则根据标识选择是否进行更新操作（用给定的value值替换该结点的value值），若遍历完桶仍没有找到hash值与key值和指定的hash值与key值相等的结点，则直接新生一个结点并赋值为之前最后一个结点的下一个结点。进入步骤⑥
⑥ 若binCount值达到红黑树转化的阈值，则将桶中的结构转化为红黑树存储，最后，增加binCount的值
初始化table
Node<K,V>[] initTable()
对于table的大小，会根据sizeCtl的值进行设置，如果没有设置szieCtl的值，那么默认生成的table大小为16，否则，会根据sizeCtl的大小设置table大小
获取table指定元素
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}此函数返回table数组中下标为i的结点，可以看到是通过Unsafe对象通过反射获取的，getObjectVolatile的第二项参数为下标为i的偏移地址
比较并交换
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}此函数用于比较table数组下标为i的结点是否为c，若为c，则用v交换操作。否则，不进行交换操作。
协助转移
Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f)
此函数用于在扩容时将table表中的结点转移到nextTable中
添加节点到红黑树
TreeNode<K,V> putTreeVal(int h, K k, V v)
此函数用于将指定的hash、key、value值添加到红黑树中，若已经添加了，则返回null，否则返回该结点
转换成红黑树
void treeifyBin(Node<K,V>[] tab, int index)
此函数用于将桶中的数据结构转化为红黑树，其中，值得注意的是，当table的长度未达到阈值时，会进行一次扩容操作，该操作会使得触发treeifyBin操作的某个桶中的所有元素进行一次重新分配，这样可以避免某个桶中的结点数量太大。
查询
V get(Object key)
get函数根据key的hash值来计算在哪个桶中，再遍历桶，查找元素，若找到则返回该结点，否则，返回null
删除
replaceNode
此函数对remove函数提供支持，remove函数底层是调用的replaceNode函数实现结点的删除
1、计算hash值
2、进入无限循环 确保删除成功
3、若table表为空或者表长度为0或者key所对应的桶为空 跳出循环
4、若桶中第一个结点的hash值为MOVED 则转移数据
5、删除操作
准备对桶中的第一个节点进行枷锁处理 但看看是否满足前提条件
a、判断桶中的第一个节点是否没有变化
a-1、节点hash值是否大于0
a-2、无限循环链表
a-3、判断 结点的hash值与指定的hash值相等，并且key也相等
a-4、进行替换或删除
b、判断是否为红黑树
b-1、 转换为treeNode结构
b-2、根节点不为空并且存在与指定hash和key相等的结点
b-3、进行替换或删除
网友评论