collection-hashmap
collection-hashmap
特性：
- 自动扩容
- 初始化与懒加载
- 哈希计算
- 位运算与并发
自动扩容
- 扩容是通过resize方法实现的
- 扩容是在putval之后，也就是写入元素之后才判断是否需要扩容。
当自增后的size大于之前所计算好的阈值threshold，即执行resize操作。
通过位运算<<1进行容量扩充，即扩容1倍，同时新的阈值newThr也扩容为老阈值的1倍。
3种情况的扩容：
- 哈希桶数组中某个位置只有一个元素-不发生哈希冲突，直接添加进链表
- 哈希桶数组中某个位置的元素为树节点，进行红黑树扩容
- 哈希桶数组中某个位置的元素为普通节点，进行链表扩容。在JDK1.8中，为了避免之前版本中并发扩容所导致的死链问题，引入了高低位链表辅助进行扩容操作
当hashmap在声明时赋予的容量太小，会导致过早或频繁的进行扩容，影响使用性能
在日常开发过程中，一定要充分评估好HashMap的大小，尽可能保证扩容的阈值大于存储元素的数量，减少其扩容次数。
初始化与懒加载
初始化的时候只会设置默认的负载因子，并不会进行其他初始化的操作，在首次使用的时候才会进行初始化。
当new一个新的HashMap的时候，不会立即对哈希数组进行初始化，而是在首次put元素的时候，通过resize()方法进行初始化。
resize()中会设置默认的初始化容量DEFAULT_INITIAL_CAPACITY为16，扩容的阈值为0.75*16 = 12，即哈希桶数组中元素达到12个便进行扩容操作。
最后创建容量为16的Node数组，并赋值给成员变量哈希桶table，即完成了HashMap的初始化操作。
哈希计算
hashmap和concurrenthashmap中，Object的native方法返回的hashCode作为最终的哈希值，而是使用了扰动函数。
扰动函数
将高16位与低16位进行异或的操作
目的是将高位的特征融入到低位之中，降低哈希冲突的概率
在hashmap和concurrenthashmap的hashcode计算逻辑中，使用key对应的hashCode与其hashCode右移16位的结果进行异或操作，作为扰动函数。
使用扰动函数减少hash冲突这种增益会随着HashMap容量的减少而增加。《An introduction to optimising a hashing strategy》文章中随机选取了哈希值不同的352个字符串，当HashMap的容量为2^9时，使用扰动函数可以减少10%的碰撞，可见扰动函数的必要性。
除了扰动函数，concurrenthashmap还需要做进一步处理：与HASH_BITS做与运算。
HASH_BITS为0x7ffffff，即只有最高位为0，这样运算的结果使hashCode永远为正数。
在ConcurrentHashMap中，预定义了几个特殊节点的hashCode，如：MOVED、TREEBIN、RESERVED，它们的hashCode均定义为负值。因此，将普通节点的hashCode限定为正数，也就是为了防止与这些特殊节点的hashCode产生冲突。
哈希冲突
解决哈希冲突的两种方式：
- 避免冲突
- 发生冲突时合理解决冲突
要避免哈希冲突可以使用扰动函数，而发生冲突时，hashmap有两种解决方案：
- 拉链表
- 红黑树
拉链表
参考拉链法
死链
在jdk1.8之前，hashmap在并发下扩容会发生死链，导致get该位置元素的时候，会死循环，使CPU利用率高居不下，这也是为什么hashmap线程不安全的原因之一。
为了解决该问题，在JDK1.8之中，引入了高低位链表（双端链表）。
高低位链表
在扩容时，哈希桶数组buckets会扩容一倍，以容量为8的HashMap为例，原有容量8扩容至16，将[0, 7]称为低位，[8, 15]称为高位，低位对应loHead、loTail，高位对应hiHead、hiTail。
红黑树
除了拉链表，在jdk1.8引入了红黑树来解决hash冲突。
有了拉链表，为什么还要引入红黑树呢？问题可以转化为链表vs红黑树。链表的查询性能为O(n),当数据量大的时候性能较差，而红黑树在增加删除或查询时性能比较稳定，都是O(logN),所以当链表容量达到一定阈值时，将会发生树化，使用红黑树结构来代替链表结构。
树化
在JDK1.8中，如果冲突链上的元素数量大于8，并且哈希桶数组的长度大于64时，会使用红黑树代替链表来解决哈希冲突。
反树化
突链上的元素数量小于6时
位运算
确定哈希桶数组大小
threshold-->hashmap需要触发扩容的阈值
在构造hashmap时，需要通过tableSizeFor计算threshold大小。tableSizeFor根据输入容量大小cap来计算最终哈希桶数组的容量大小，找到大于等于给定值cap的最小2的整数次幂。
最小2的整数次幂
为什么一定是最小2的整数次幂？
- 加快哈希计算
- 减少哈希冲突
为了提高计算与存储效率，使每个元素对应hash值能够准确落入哈希桶数组给定的范围区间内。确定数组下标采用的算法是 hash & (n - 1)，n即为哈希桶数组的大小。
ASHIFT偏移量计算
源码解析
putval
/*
Implements Map.put and related methods
Params:
hash – hash for key
key – the key
value – the value to put
onlyIfAbsent – if true, don't change existing value
evict – if false, the table is in creation mode.
Returns:
previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//声明变量，使用局部变量代替全局变量 （一种编程习惯）
//tab-哈希桶 p-输入元素对应的哈希桶中的节点 n-哈希桶大小 i-输入元素对应的哈希桶索引
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果底层数组table没有初始化，则通过resize来初始化数组
if ((tab = table) == null || (n = tab.length) == 0)
//说明hashmap不是在new的时候初始化，而是在第一次putval的时候
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//未出现hash冲突
tab[i] = newNode(hash, key, value, null);
else {
//出现hash冲突
Node<K,V> e; K k;
//当前哈希桶中的节点与输入元素的hash值一致，则直接替换
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//当前哈希桶中的节点与输入元素的hash值一致，则遍历该位置上的红黑树节点，选择合适的位置插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//当前哈希桶中的节点与输入元素的hash值一致，则遍历该位置上的链表节点，选择合适的位置插入
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;
}
可以看出，resize是在putval之后，size增加和threshold作比较，再进行resize。
resize
final Node<K,V>[] resize() {
//使用局部变量持有table
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
//新容量
//新门限值
int newCap, newThr = 0;
if (oldCap > 0) {
//如果原容量已大于等于最大容量上线，则后续不再存在需要扩容的场景
//threshold赋值为Integer最大值，默认无需判断扩容
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 门限值*2
}
else if (oldThr > 0) // initial capacity was placed in threshold 使用门限值初始化容量
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
// 如果原门限值小于0，使用默认值初始化门限值和容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//第一次创建hashmap时在这初始化门限值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//新建底层数组对象
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新底层数组赋值给全局变量table
table = newTab;
if (oldTab != null) {
//原数组不为null，开始扩容迁移
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//链表只有一个元素，hash取模，直接下标赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是树结构，进行树结构扩容
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//链表数据迁移
//jdk1.8以前会发生死链问题
//jdk1.8以后用高低链解决
//低位链表
Node<K,V> loHead = null, loTail = null;
//高位链表
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扰动函数
static final int hash(Object key) {
int h;
//使用key对应的hashCode与其hashCode右移16位的结果进行异或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算最小2的整数次幂
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;
}
