HashMap的创建
指定参数时:
/**
* 根据容量参数initialCapacity计算sizeCtrl，值为：
* （1.5 * initialCapacity + 1），然后向上取近的2次幂。
* @param initialCapacity
* @throws IllegalArgumentException 如果initialCapacity为负时，抛出该异常；
*/
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
不指定参数时:
public ConcurrentHashMap() {
}
数组的初始化发生在initTable()中。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
//如果sizeCtrl<0, 则表示有其他线程正在执行初始化操作且未成功,
//调用Thread.yield()使其失去CPU的执行权,等待初始化的完成;
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //当sizeCtrl的值为sc时, 将sizeCtrl更新为-1;
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY; //如果没有指定过sizeCtrl, 则使用默认值DEFAULT_CAPACITY(16);
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc; //执行成功以后, 将sizeCtrl更新为原来的0.75倍.
}
break;
}
}
return tab;
}
元素访问操作
//获取i位置的元素
@SuppressWarnings("unchecked")
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);
}
//利用CAS算法设置i位置上的元素值（将c和v比较，如果不相同则插入v到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);
}
//设置i位置的值为v
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
插入操作
插入<K,V>类型的键值对<key, value>, 具体方法：
- 计算key的hash值，为spread(key.hashCode());
- 如果table为null, 则创建大小为sizeCtrl的Node<K,V>[]数组table, 并更新sizeCtrl；
- 根据hash值, 确定要插入的位置: (n - 1) && hash;
- 如果table中待插入位置为null, 则插入新创建的Node实例;
- 如果table待插入位置的Node实例hash值>=0, 从Node链表中找出hash和key都相等的元素; 如果找到, 则直接更新；如果没有找到,则将新的Node插入到链表末尾;
- 如果待插入位置的Node实例的hash值<0, 则判断是否为红黑树节点。
/**
* @param key
* @param value
* @param onlyIfAbsent onlyIfAbsent为true时, 仅当table中不存在该key时, 才会进行插入操作;
* @return
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//initTable()创建大小为sizeCtrl的Node<K,V>[]数组table, 并更新sizeCtrl.
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //tab[i]为null.
//在位置i处插入新建的Node实例.
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null)))
break; // no lock when adding to empty bin
} else if ((fh = f.hash) == MOVED) //tab[i]的Node实例hash值为MOVED(-1)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
//tab[i]的Node实例hash值>=0, 从Node链表中找出hash和key都相等的元素;
// 如果找到,如果没有找到,则将新的Node插入到链表末尾.
if (fh >= 0) {
binCount = 1;
for (Node<K, V> e = f; ; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K, V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
break;
}
}
} else if (f instanceof TreeBin) { //红黑树
Node<K, V> p;
binCount = 2;
if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
} else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
获取操作
获取参数key所对应的Value，具体方法：
- 计算hash值h:spread(key.hashCode());
- 根据hash值确定table数组位置: (n - 1) & h;
- (1) 如果该位置为null, 返回null;
(2) 如果该位置不为null, 记首节点为e; 如果e.hash == h && e.key == key,则直接返回e.val, 否则进入(3)
(3) 如果e.hash < 0, 说明正在扩容，或者是红黑树;
(4) 如果以上3条都不满足, 说明是链表, 按顺序进行遍历.
public V get(Object key) {
Node<K, V>[] tab;
Node<K, V> e, p;
int n, eh;
K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
} else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
