HashMap及ConcurrentHashMap源码分析

发表于

HashMap

继承 接口

1
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

实现了Map的接口

常数

1
2
3
4
5
6
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
  • default initial capacity必须是2的幂次
  • bin中元素数量默认超过8时从链表转换成红黑树

内部类

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;
    V value;
    Node<K,V> next;
    ......
    public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
}

hash和key由final修饰；hashCode值由key和value的hashCode值异或获得。

1
2
3
final class KeySet extends AbstractSet<K> { ... }
final class Values extends AbstractCollection<V> { ... }
final class EntrySet extends AbstractSet<Map.Entry<K,V>> { ... }
1
2
3
4
5
6
7
8
static final class TreeNode<K,V> extends LinkedHashMap.Entry<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;
	....
}

补充红黑树：自平衡二叉查找树，O(logn)时间内查找插入和删除

性质

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色（叶子是NIL节点）。
  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

hash

1
2
3
4
static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

计算key的hash值时，16位右位移异或混合即混合高位与低位，加大随机性

Fields

1
2
3
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;

table被allocate时，长度总是2的幂次

构造函数

1
2
3
public HashMap(int initialCapacity, float loadFactor) { ...}
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR;}

构造函数可传入参数有初始大小和负载因子，默认值分别为16和0.75。

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public V get(Object key) {
	Node<K,V> e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		if ((e = first.next) != null) {
			if (first instanceof TreeNode)
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			do {
				if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

table不为null，长度大于0且Node映射所在bin不为null时进行操作：

get(key)返回null值并不一定代表map不包含key的映射，也可能有key对于null的映射

使用(n-1)&hash计算到key映射的bin的下标（n-1为全1，与后即可对应到bin的位置），first指向bin中第一结点并比较key是否相等；不相等则依次比较next结点直到链表尾部，比较时需先判断时红黑树结点，相等即返回指向结点；比较都不相等则返回null

put

1
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
    else {
		Node<K,V> e; K k;
		if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		else {
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	if (++size > threshold)
		resize();
	afterNodeInsertion(evict);
	return null;
}

table为null或者table长度为0时先扩容resize

Node映射所在bin为null时，直接新建赋值新的Node；否则则bin的第一个结点存在

当第一个结点存在且key相同时，将value替换为新Node的value，并返回旧的value；当第一个结点存在且key不同且结点为红黑树的结点时，put为红黑树结点；当第一个结点存在且key相同且不为红黑树结点时，遍历链表上结点并比较key，同时记录链表上结点数量；当链表中某一结点key相同时，记录下该结点并跳出循环替换value；当遍历至链表尾部，以新的结点插入；如果结点数量超过树化阈值时，转化为红黑树

resize

table为null时，初始化为DEFAULT_INITIAL_CAPACITY大小；否则，扩容为2倍大小，每个bin中的元素要么仍然位于原来的位置，要么在新的table中以2的幂次位移进行移动

ConcurrentHashMap

继承 接口

1
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable

常数

基本同HashMap

内部类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	volatile V val;
	volatile Node<K,V> next;
	...
}
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;    
    ... 
}
static final class TreeBin<K,V> extends Node<K,V> { ... }

hash和key由final修饰，val和next由volatile修饰

Spread

1
2
3
static final int spread(int h) {
	return (h ^ (h >>> 16)) & HASH_BITS;
}

访问table

1
2
3
4
5
6
7
8
9
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);
}
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);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

volatile访问table[i]

CAS更新table[i]的首结点

volatile设置table[i]

构造函数

1
2
3
4
5
public ConcurrentHashMap() { }
public ConcurrentHashMap(int initialCapacity) { ... }
public ConcurrentHashMap(int initialCapacity, float loadFactor) { 
    this(initialCapacity, loadFactor, 1); 
}

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

使用spread计算key的hash值

当table不为null，长度大于0且元素所在table处不为null时继续操作：

当第一个结点key相同时，返回value；否则遍历链表，key相同时返回value；直至遍历至链表尾部，返回null

put

1
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public V put(K key, V value) {
	return putVal(key, value, false);
}
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)
			tab = initTable();
		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
			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 = helpTransfer(tab, f);
		else {
			V oldVal = null;
			synchronized (f) {
				if (tabAt(tab, i) == f) {
					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;
						}
                    }
				}
			}
			if (binCount != 0) {
				if (binCount >= TREEIFY_THRESHOLD)
					treeifyBin(tab, i);
				if (oldVal != null)
					return oldVal;
				break;
			}
		}
	}
	addCount(1L, binCount);
	return null;
}

ConcurrentHashMap不允许key或者value为null

table为null或者table长度为0时初始化table

通过volatile访问到元素所在table的bin处若为null，则CAS更新table处bin为新的Node，bin为空时不需要加锁；

元素所在bin不为null时，对第一个元素进行synchronized操作，并再次volatile访问确认第一个结点是否发生了变化。遍历链表，如果key相同则替换value值并跳出遍历；直至遍历至链表尾部，插入新的Node；如果第一个结点是红黑树结点，则以红黑树结点插入。遍历链表时记录结点个数，如果大于TREEIFY_THRESHOLD则转换成红黑树。