HashMap和ConcurrentHashMap的实现原理和冲突解决 博客分类： java
本篇源码来自JDK1.8.
Java的位运算和取模取余操作说明：
位运算(&)效率要比取余运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。
X % 2^n = X & (2^n - 1)
2^n表示2的n次方，也就是说，一个数对2^n取余 == 一个数和(2^n - 1)做按位与运算 。
假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。
此时X & (2^3 - 1) 就相当于取X的2进制的最后三位数。
右移和取模
从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。
HashMap的初始化：
可以是无参数的初始化，也可以指定初始大小和加载因子。
第一次添加元素时，进行第一次扩容，设置一个大小为16的数组，其中包含的元素为Node<K,V>，扩容的临界值为0.75 * 16 = 12，即等到大小超过12时再次进行扩容。
Node<K,V>结点包含4个元素：
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;//next用于处理有冲突的情况，
}
扩容时，会把旧的数组中的元素，重新计算索引，放入新的数组中。
newTab[e.hash & (newCap - 1)] = e;//根据元素的hash值与当前的容量-1，进行位元素，相当于取余操作
扩容时，新的size计算，新的容量=旧的容量*2：
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
HashMap初始化时，如果指定了一个集合，或者指定了一个初始大小，则会自动计算出一个比它大的最近的2^n值作为初始化数组的大小。计算数组大小的方法如下：
static final int tableSizeFor(int cap) {
int n = cap - 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;
}
HashMap的put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);//通过key，获取一个hash值
}
获取hash值的算法，用key的hashcode值高16位于低16位进行异或操作。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashMap中解决冲突的方法, 先用线性链表来保存冲突，如果冲突链表长度超过8，则使用红黑树结构。
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)//put时，没有冲突，直接新建一个Node。
tab[i] = newNode(hash, key, value, null);
else { //如果此处有Node,则解决冲突
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;
}
put方法(新增元素)总结：
计算元素数组下标的方法：通过元素Key的hash值与数组容量取余。
hash值相同，则产生冲突。但是hash值相同，不一定key相同。
1，通过key值获取一个hash值。
2，判断当前是否达到临界值，确定是否扩容，扩容则会把当前的容量扩大一倍。扩容时，会重新根据元素的hash值和新的数组容量，计算元素的数组下标。
3，新建一个Node结点，计算数组下标，放入对应的位置，如果有冲突，则添加进链表或者红黑树。产生冲突时，如果新增的Node结点的key与之前的key相同，则返回之前的key对应的value值。
根据Key值获取对象：
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))))//判断hash和equals,都相等，则获取成功；
return first;
if ((e = first.next) != null) {//否则从链表中往下寻找。
if (first instanceof TreeNode) //如果是红黑树，则从红黑树中获取Node.
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;
}
由于HashMap的扩容需要重新计算各个已有元素的hash值，并重新调整数组下标，是一个耗时的操作，因此最好初始化时就指定HashMap的容量initialCapacity。
initicalCapacity = (需要存储的元素个数/负载因子) + 1。 负载因子默认为0.75。如果不确定存储的元素个数，设置初始大小为16(默认值)。
只有当HashMap中一次性添加一个集合putAll()，或者初始化指定容量大小时，才会通过算法计算容量大小，保证容量大小为2的n次幂。 put操作，如果容量为空，则初始化为16，容量不够，则只会简单的把当前容量扩大一倍。HashMap的容量因此能一直保持为2的N次幂大小。
ConcurrentHashMap:
ConcurrentHashMap的初始化时如果指定大小initialCapacity，
则以initialCapacity + (initialCapacity >>> 1) + 1 开始调整，计算出比它大的最近的2^n值作为初始大小
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;
}
JDK 8之后，ConcurrentHashMap的实现原理与之前有较大的变化：
它摒弃了Segment(锁段)的概念，改用了Synchronized 和 CAS原理来实现并发。它的底层与HashMap一致，仍然采用数组+链表+红黑树的结构。
第一次插入数据时，进行初始化数组initTable();
putVal方法中有一个无限循环：
for (Node<K,V>[] tab = table;;)，只有操作成功才会跳出循环。
这其实是因为并发操作时，有时需要不断自旋等待。
/** Implementation for put and putIfAbsent */
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) {
//利用CAS算法，设置位置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 = 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;
}
获取几个相关参数的内存地址，使用CAS操作直接进行修改。
// Unsafe mechanics
private static final sun.misc.Unsafe U;
private static final long SIZECTL;
private static final long TRANSFERINDEX;
private static final long BASECOUNT;
private static final long CELLSBUSY;
private static final long CELLVALUE;
private static final long ABASE;
private static final int ASHIFT;
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class<?> k = ConcurrentHashMap.class;
SIZECTL = U.objectFieldOffset
(k.getDeclaredField("sizeCtl"));
TRANSFERINDEX = U.objectFieldOffset
(k.getDeclaredField("transferIndex"));
BASECOUNT = U.objectFieldOffset
(k.getDeclaredField("baseCount"));
CELLSBUSY = U.objectFieldOffset
(k.getDeclaredField("cellsBusy"));
Class<?> ck = CounterCell.class;
CELLVALUE = U.objectFieldOffset
(ck.getDeclaredField("value"));
Class<?> ak = Node[].class;
ABASE = U.arrayBaseOffset(ak);//获取数组第一个元素在内存中的偏移位置
int scale = U.arrayIndexScale(ak);//获取数组中元素的增量地址
//将arrayBaseOffset和arrayIndexScale配合使用，可以获取数组中每个元素的偏移位置
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
} catch (Exception e) {
throw new Error(e);
}
}
相关的几个CAS操作的方法：
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);
}
EnumMap使用
EnumMap是专门为枚举类型量身定做的Map实现。
EnumMap要求其Key必须为Enum类型，它只能接收同一枚举类型的实例作为键值且不能为null。
EnumMap使用数组来存放与枚举类型对应的值，由于枚举类型实例的数量相对固定并且有限，所以使用EnumMap不会涉及到数组扩容，性能会更加高效。
上一篇： Android WebP 图片压缩与传输