没有合适的资源?快使用搜索试试~ 我知道了~
(1)关键属性 (2)关键类 (3)CAS关键操作 (1)实例构造器方法 (2)initTable方法
资源详情
资源评论
资源推荐
并发容器
一、ConcurrentHashMap
在多线程情况下,使用HashMap扩容时会出现CPU接近100%的情况,因为HashMap不是线程安全的;对于
HashTable该类基本上所有的方法都采用synchronized进行线程安全控制的,在高并发的情况下,每次只有一个线程
能够获取对象监视器锁,这样的并发性能的确不令人满意。另外一种方式是通过Collections的Map<k,v>
synchronizedMap(Map<k,v> m)将hashmap包装成一个线程安全的map,比如synchronizedMap的put方法的源码
为:
实际上SynchronizedMap实现依然是采用synchronized独占式锁进行线程安全的并发控制的。同样,这种方案的性
能也是令人不太满意的。相对于hashmap来说,ConcurrentHashMap就是线程安全的map,其中利用了锁分段的
思想提高了并发度,首先将数据分成一段一段存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段
数据的时候,其他段的数据也能被其他线程访问。
JDK 1.8的ConcurrentHashMap就有了很大的变化,光是代码量就足足增加了很多。1.8版本舍弃了segment,并且
大量使用了synchronized,以及CAS无锁操作以保证ConcurrentHashMap操作的线程安全性。至于为什么不用
ReentrantLock而是Synchronzied呢?实际上,synchronzied做了很多的优化,包括偏向锁,轻量级锁,重量级
锁,可以依次向上升级锁状态,但不能降级,因此,使用synchronized相较于ReentrantLock的性能会持平甚至在某
些情况更优。
1、关键属性及类
(1)关键属性
table :transient volatile Node<K,V>[] table;装载Node的数组,作为ConcurrentHashMap的数据容器,采用
懒加载的方式,直到第一次插入数据的时候才会进行初始化操作,数组的大小总是为2的幂次方。
nextTable:transient volatile Node<K,V>[] nextTable;扩容时使用,平时为null,只有在扩容的时候才为非null
sizeCtl:transient volatile int sizeCtl;该属性用来控制table数组的大小,根据是否初始化和是否正在扩容有几
种情况: 当值为负数时:如果为-1表示正在初始化,如果为-N则表示当前正有N-1个线程进行扩容操作; 当值
为正数时:如果当前数组为null的话表示table在初始化过程中,sizeCtl表示为需要新建数组的长度; 若已经初
始化了,表示当前数据容器(table数组)可用容量也可以理解成临界值(插入节点数超过了该临界值就需要扩
容),具体指为数组的长度n 乘以 加载因子loadFactor; 当值为0时,即数组长度为默认初始值。
U:sun.misc.Unsafe U;在ConcurrentHashMapde的实现中可以看到大量的U.compareAndSwapXXXX的方
法去修改ConcurrentHashMap的一些属性。这些方法实际上是利用了CAS算法保证了线程安全性,这是一种乐
观策略,假设每一次操作都不会产生冲突,当且仅当冲突发生的时候再去尝试。而CAS操作依赖于现代处理器指
令集,通过底层CMPXCHG指令实现。CAS(V,O,N)核心思想为:若当前变量实际值V与期望的旧值O相同,则表
明该变量没被其他线程进行修改,因此可以安全的将新值N赋值给变量;若当前变量实际值V与期望的旧值O不
相同,则表明该变量已经被其他线程做了处理,此时将新值N赋给变量操作就是不安全的,在进行重试。而在大
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
1
2
3
量的同步组件和并发容器的实现中使用CAS是通过sun.misc.Unsafe类实现的,该类提供了一些可以直接操控内
存和线程的底层操作,可以理解为java中的“指针”。该成员变量的获取是在静态代码块中:
(2)关键类
Node:Node类实现了Map.Entry接口,主要存放key-value对,并且具有next域,另外可以看出很多属性都是
用volatile进行修饰的,也就是为了保证内存可见性。
TreeNode 树节点,继承于承载数据的Node类。而红黑树的操作是针对TreeBin类的,从该类的注释也可以看
出,也就是TreeBin会将TreeNode进行再一次封装
TreeBin 这个类并不负责包装用户的key、value信息,而是包装的很多TreeNode节点。实际的
ConcurrentHashMap“数组”中,存放的是TreeBin对象,而不是TreeNode对象。
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class<?> k = TreeBin.class;
LOCKSTATE = U.objectFieldOffset
(k.getDeclaredField("lockState"));
} catch (Exception e) {
throw new Error(e);
}
}
1
2
3
4
5
6
7
8
9
10
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
......
}
1
2
3
4
5
6
7
/**
* Nodes for use in TreeBins
*/
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
......
}
1
2
3
4
5
6
7
8
9
10
11
ForwardingNode 在扩容时才会出现的特殊节点,其key,value,hash全部为null。并拥有nextTable指针引用新
的table数组。
(3)CAS关键操作
ConcurrentHashMap中会大量使用CAS修改它的属性和一些操作。因此,在理解ConcurrentHashMap的方法前我
们需要了解下面几个常用的利用CAS算法来保障线程安全的操作。
tabAt:该方法用来获取table数组中索引为i的Node元素
casTabAt:利用CAS操作设置table数组中索引为i的元素
setTabAt:该方法用来设置table数组中索引为i的元素
2、重点方法
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
volatile Thread waiter;
volatile int lockState;
// values for lockState
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock
static final int READER = 4; // increment value for setting read lock
......
}
1
2
3
4
5
6
7
8
9
10
11
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
......
}
1
2
3
4
5
6
7
8
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);
}
1
2
3
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);
}
1
2
3
4
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
1
2
3
(1)实例构造器方法
对于第二种,传入指定大小时的情况:
这段代码的逻辑请看注释,很容易理解,如果小于0就直接抛出异常,如果指定值大于了所允许的最大值的话就取最
大值,否则,在对指定值做进一步处理。最后将cap赋值给sizeCtl,关于sizeCtl的说明请看上面的说明,当调用构造器
方法之后,sizeCtl的大小应该就代表了ConcurrentHashMap的大小,即table数组长度。tableSizeFor做了哪些事情
了?源码为:
通过注释就很清楚了,该方法会将调用构造器方法时指定的大小转换成一个2的幂次方数,也就是说
ConcurrentHashMap的大小一定是2的幂次方,比如,当指定大小为18时,为了满足2的幂次方特性,实际上
concurrentHashMapd的大小为2的5次方(32)。另外,需要注意的是,调用构造器方法的时候并未构造出table数
组(可以理解为ConcurrentHashMap的数据容器),只是算出table数组的长度,当第一次向
ConcurrentHashMap插入数据的时候才真正的完成初始化创建table数组的工作。
(2)initTable方法
// 1. 构造一个空的map,即table数组还未初始化,初始化放在第一次插入数据时,默认大小为16
ConcurrentHashMap()
// 2. 给定map的大小
ConcurrentHashMap(int initialCapacity)
// 3. 给定一个map
ConcurrentHashMap(Map<? extends K, ? extends V> m)
// 4. 给定map的大小以及加载因子
ConcurrentHashMap(int initialCapacity, float loadFactor)
// 5. 给定map大小,加载因子以及并发度(预计同时操作数据的线程)
ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel)
1
2
3
4
5
6
7
8
9
10
public ConcurrentHashMap(int initialCapacity) {
// 小于0抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException();
// 判断是否超过了最大值
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
1
2
3
4
5
6
7
8
9
10
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
1
2
3
4
5
6
7
8
9
private final Node<K,V>[] initTable() {1
代码的逻辑请见注释,有可能存在一个情况是多个线程同时走到这个方法中,为了保证能够正确初始化,在第1步中
会先通过if进行判断,若当前已经有一个线程正在初始化即sizeCtl值变为-1,这个时候其他线程在If判断为true从而调
用Thread.yield()让出CPU时间片。正在进行初始化的线程会调用U.compareAndSwapInt方法将sizeCtl改为-1即正在
初始化的状态。另外还需要注意的事情是,在第四步中会进一步计算数组中可用的大小即为数组实际大小n乘以加载
因子0.75.可以看看这里乘以0.75是怎么算的,0.75为四分之三,这里n - (n >>> 2)是不是刚好是n-(1/4)n=(3/4)n,挺
有意思的吧:)。如果选择是无参的构造器的话,这里在new Node数组的时候会使用默认大小为
DEFAULT_CAPACITY(16),然后乘以加载因子0.75为12,也就是说数组的可用大小为12。
(3)put方法
构造哈希函数的方法有:
直接定址法:当关键字是整型数时,可以取关键字本身或它的线性函数作为它的哈希地址。即
或 为 常 数
。但是该方法会造成空间的大量浪费。
除留余数法:选取一个合适的不大于哈希表长的正整数m,用m去除关键字K,所得的余数作为其哈希地址,
即: ,这种方法称为除留余数法,该方法的优劣取决于m值的选取。若m取某个偶数值,其
结果是将奇数关键字的记录映射到奇数地址上,将偶数关键字的记录映射到偶数地址上,因此产生的哈希地址
很可能不均匀分布。若m取关键字的基数的幂次值,那么产生的哈希地址是关键字的某几个低位值。这种方法
是一种简单而且行之有效的构造哈希函数的方法。
数字分析法:关键字有d位数,选取其中若干位的值构造哈希地址的方法称为数字分析法。这种方法要事先知道
所有关键字或大多数关键字的值,对这些关键字的各位值做分析,丢掉不均匀的位值,留下分布较均匀的位值
构造器哈希函数。
平方取中法:取关键字平方后的中间若干位作为其哈希地址。即:
的 中 间 几 位
。因为关键字平
方后使得它的中间几位和组成关键字的各位值均有关,从而使哈希地址的分布较均匀,减少了发生冲突的可能
性。所取的位数取决于哈希表的表长。
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
// 1.保证只有一个线程在创建
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// 2.得出数组的大小,默认为16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// 3.创建数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 4.计算出数组中的可用大小:实际大小*0.75(加载因子)
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
剩余34页未读,继续阅读
豆瓣时间
- 粉丝: 22
- 资源: 329
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0