一、基本原理
HashMap 的内部可以看做数组+链表的复合结构。数组被分为一个个的桶(bucket)。哈希值决定了键值对在数组中的寻址。具有相同哈希值的键值对会组成链表。需要注意的是当链表长度超过阈值(默认是8)的时候可能会触发树化（触发树化还需要看桶的长度是否已经达到预期值，否则只会触发扩容），链表会变成树形结构。
把握HashMap的原理需要关注4个方法：hash、put、get、resize。
hash方法。 将 key 的 hashCode 值的高位数据移位到低位进行异或运算。这么做的原因是有些 key 的 hashCode 值的差异集中在高位，而哈希寻址是忽略容量以上高位的，这种做法可以有效避免哈希冲突。
put 方法。 put 方法主要有以下几个步骤：
- 通过 hash 方法获取 hash 值，根据 hash 值寻址。
- 如果未发生碰撞，直接放到桶中。
- 如果发生碰撞，则以链表形式放在桶后。
- 当链表长度大于阈值后会将会考虑改为红黑树，如果桶数组长度小于常量MIN_TREEIFY_CAPACITY时，不会变为红黑树，而是调用resize()方法进行扩容。MIN_TREEIFY_CAPACITY的默认值是64。
- 如果集合中元素的个数达到阈值（默认是数组的长度*loadFactor），会调用 resize 方法扩展容量。
get方法。 get 方法主要有以下几个步骤：
通过 hash 方法获取 hash 值，根据 hash 值寻址。
如果与寻址到桶的 key 相等，直接返回对应的 value。
如果发生冲突，分两种情况。如果是树，则调用 getTreeNode 获取 value；如果是链表则通过循环遍历查找对应的 value。
resize 方法。 resize 做了两件事：
将原数组扩展为原来的 2 倍。
重新计算 index 索引值，将原节点重新放到新的数组中。这一步可以将原先冲突的节点分散到新的桶中。
二、进阶
2.1Hashmap的初始化优化：
由于HashMap 的 put方法存在扩容的情况，在我们初始化HaspMap时，如果已经知道需要放到HashMap中元素个数时，就有必要在初始化时指定数组大小。
分析：
2.1.1 HashMap put()
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)
//数组为空，调用resize()对数组进行初始化。
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;
}
}
//如果添加的元素的key本来就已经在Hashmap 里面的，会直接返回原来的值，不会进行扩容判断
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//这里进行了扩容判断，所以threshold 是用来扩容判断的，size 就是集合中元素的个数，只有在添加了新元素的情况下才会进行扩容判断。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2.1.2 HashMap resize()
final Node<K,V>[] resize() {
//对oldTab 赋值，这里的table 就是 HashMap 内的桶数组。
Node<K,V>[] oldTab = table;
//获取桶数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取原来用于扩容判断的阈值
int oldThr = threshold;
int newCap, newThr = 0;
//如果桶数组的长度大于0，则表明之前已经初始化
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//将原数组和扩容判断的阈值扩展为原来的 2 倍。
newThr = oldThr << 1; // double threshold
}
/**
* 桶数组的长度小于0，oldThr 这里已经代表threshold (用于扩容判断的阈值)，
* threshold默认值为0，但是这里threshold 大于0，这表明hashmap
* 未添加过元素，但是在实例化hashmap 时已经传入了数组的大小范围数值。
* 这种情况下，threshold 代表的就是初始化数组大小的范围。
*/
else if (oldThr > 0) // initial capacity was placed in threshold
//这里赋予了数组大小的范围。
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/**
* 这里代表haspmap 的桶数组为空，阈值也为0，
* 走hashmap 默认初始化的数组大小的值 和 阈值 ，16 和 16*0.75 = 12；
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR *
DEFAULT_INITIAL_CAPACITY);
}
//对扩容的值进行初始化，loadFactor
if (newThr == 0) {
/*从这里和 下面的threshold = newThr 赋值 可以知道
threshold = 数组大小*loadFactor，结合之前的put方法就表明
当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容。
*/
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//这里给threshold 赋最新的值
threshold = newThr;
//这里进行了数组的实例化
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
/* 篇幅过长，省略掉，这里进行的是重新计算 index 索引值，
将原节点重新放到新的数组中。这一步可以将原先冲突的节点分散到新的桶中。*/
}
return newTab;
}
2.1.3 HashMap 构造函数
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
//默认装载因子数值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
/**
* tableSizeFor的功能（不考虑大于最大容量的情况）是返回
* 大于或等于输入参数且最近的2的整数次幂的数，意思是假如你
* 传入的数组大小是10，但是hashmap会强制给你设置成16
*/
this.threshold = tableSizeFor(initialCapacity);
}
2.1.4 tableSizeFor()
分析参考 https://www.cnblogs.com/loading4/p/6239441.html
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;
}
详解如下：
先来分析有关n位操作部分：先来假设n的二进制为01xxx...xxx。接着
对n右移1位：001xx...xxx，再位或：011xx...xxx
对n右移2为：00011...xxx，再位或：01111...xxx
此时前面已经有四个1了，再右移4位且位或可得8个1
同理，有8个1，右移8位肯定会让后八位也为1。
综上可得，该算法让最高位的1后面的位全变为1。
最后再让结果n+1，即得到了2的整数次幂的值了。
现在回来看看第一条语句：
int n = cap - 1;
让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。
总结：
结合上面HashMap的方法的分析，我们知道了当hashmap中的元素个数超过数组大小 * loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16 * 0.75=12的时候，就把数组的大小扩展为2 * 16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有16个元素new HashMap(15), 但是理论上来讲new HashMap(16)是最合适的，不过上面已经分析过，即使是15，hashmap也自动会将其设置为16。 但是new HashMap(16)还不是更合适的，因为0.75*16< 15, 也就是说为了让0.75 * 数组长度> 15, 我们必须这样new HashMap(32)才最合适，避免了resize的问题。
2.2 HashMap和红黑树
从JDK1.8开始，在HashMap里面定义了一个常量TREEIFY_THRESHOLD，默认为8。当链表中的节点数量大于TREEIFY_THRESHOLD时，链表将会考虑改为红黑树，代码是在上面putVal()方法的这一部分：
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;
}
其中的treeifyBin()方法就是链表转红黑树的方法，这个方法的代码是这样的：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
可以看到，如果table长度小于常量MIN_TREEIFY_CAPACITY时，不会变为红黑树，而是调用resize()方法进行扩容。MIN_TREEIFY_CAPACITY的默认值是64。显然HashMap认为，虽然链表长度超过了8，但是table长度太短，只需要扩容然后重新散列一下就可以。
2.3 HashMap扩容机制
resize()方法如下,截取关键部分分析，关于桶是树节点情况下的扩容较为复杂就不多讲了，有兴趣的自行了解。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //注释1
newThr = oldThr << 1; // double threshold
}
........
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //注释2
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //注释3
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //注释10
else { // preserve order
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) { //注释4
if (loTail == null) //注释5
loHead = e;
else
loTail.next = e; //注释6
loTail = e; //注释7
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { /注释8
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
代码解析：
1，在resize()方法中，定义了oldCap参数，记录了原table的长度，定义了newCap参数，记录新table长度，newCap是oldCap长度的2倍（注释1），同时扩展点也乘2。
2，注释2是循环原table，把原table中的每个链表中的每个元素放入新table。
3，注释3，e.next==null，指的是链表中只有一个元素，所以直接把e放入新table，其中的e.hash & (newCap - 1)就是计算e在新table中的位置。
4，注释// preserve order，这个注释是源码自带的，这里定义了4个变量：loHead，loTail，hiHead，hiTail，看起来可能有点眼晕，其实这里体现了JDK1.8对于计算节点在table中下标的新思路：
正常情况下，计算节点在table中的下标的方法是：hash&(oldTable.length-1)，扩容之后，table长度翻倍，计算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我们有了这样的结论：这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度。这种情况下我们就可以把链表内的节点分成两种，"新下标等于旧下标" 或者 "新下标等于旧下标加上旧数组的长度",把这两种节点重新组成不同的新链表，再把表头赋值给对应的桶就好了。
举个例子，假设table原长度是16，扩容后长度32，那么一个hash值在扩容前后的table下标是这么计算的：
image.png
hash值的每个二进制位用abcde来表示，那么，hash和新旧table按位与的结果，最后4位显然是相同的，唯一可能出现的区别就在第5位，也就是hash值的b所在的那一位，如果b所在的那一位是0，那么新table按位与的结果和旧table的结果就相同，反之如果b所在的那一位是1，则新table按位与的结果就比旧table的结果多了10000（二进制），而这个二进制10000就是旧table的长度16。
换言之，hash值的新散列下标是不是需要加上旧table长度，只需要看看hash值第5位是不是1就行了，位运算的方法就是hash值和10000（也就是旧table长度）来按位与，其结果只可能是10000或者00000。
所以，注释4处的e.hash & oldCap，就是用于计算位置b到底是0还是1用的，只要其结果是0，则新散列下标就等于原散列下标，否则新散列坐标要在原散列坐标的基础上加上原table长度。
理解了上面的原理，这里的代码就好理解了，代码中定义的四个变量：
loHead，下标不变情况下的链表头
loTail，下标不变情况下的链表尾
hiHead，下标改变情况下的链表头
hiTail，下标改变情况下的链表尾
而注释4处的(e.hash & oldCap) == 0，就是代表散列下标不变的情况，这种情况下代码只使用了loHead和loTail两个参数，由他们组成了一个链表，否则将使用hiHead和hiTail参数。
注释5 到 注释 7 就是链表的尾插法，这里就不再多讲了。
代码到注释8这里就好理解了，
只要loTail不是null，说明链表中的元素在新table中的下标没变，所以新table的对应下标中放的是loHead，另外把loTail的next设为null
反之，hiTail不是null，说明链表中的元素在新table中的下标，应该是原下标加原table长度，新table对应下标处放的是hiHead，另外把hiTail的next设为null。
再讲一下注释10部分的桶节点是树节点情况下的扩容，有了上面的基础，这里不会讲太详细。
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//第一部分
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
//记录元素的个数
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
//记录元素的个数
++hc;
}
}
//第二部分
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map); //注释1
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified) //注释2
loHead.treeify(tab); //注释3
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead; //注释4
if (loHead != null) //注释5
hiHead.treeify(tab);
}
}
}
根据上面的代码，第一部分和第二部分的code 就是 把 整棵树的节点分成两种，
"新下标等于旧下标" 或者 "新下标等于旧下标加上旧数组的长度" ，可以看出是以双向链表的方式存储的，并且保存了这两种节点的元素个数。
第二部分之后的代码
先看注释1 ，这里先对新下标等于旧下标链表的元素个数进行了判断，如果小于UNTREEIFY_THRESHOLD （默认值是6），则做了去树化的动作。
注释3，则是做了树化的动作。
注释2的判断条件是为什么了，假设hiHead ==null ，就意味着上面节点的分类只有一种，就是 "新下标等于旧下标"，那这种情况下就不用再进行树化了，因为原来就是树了。
注释4就是把链表头先放到桶内，再去判断是否树化。
注释5就是注释2一样的解析了。
网友评论