就像从 HellWord 开始一样，这一次我们从 Map m = new HashMap() 开始
HashMap的存储过程
基于Map m = new HashMap()，我们看一个测试例子
Map<String, String> map = new HashMap<>();
map.put("1", "有村架纯");
map.put("2", "新垣结衣");
map.put("3", "石原里美");
map.put("4", "斋藤飞鸟");
System.out.println(map);
控制台输出：
{1=有村架纯, 2=新垣结衣, 3=石原里美, 4=斋藤飞鸟}
进入put源码，看一下它是怎么进行的：
//put源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
真正执行存入键值对的方法
transient Node<K,V>[] table;
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;
//计算出这个节点位置下标，也就是在位桶数组中的位置
//进行一个取模运算：算法规则是： （数组的长度-1）& hash
if ((p = tab[i = (n - 1) & hash]) == null) //<--------这个单独讲讲它的来由
//如果这个位置上没有节点，那么我们创建一个节点放在这个位置上
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果这个key的hash值和原本在这个节点上的hash值相通 key值也相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //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);
//骚操作来了，如果这条链上的节点大于等于这个TREEIFY_THRESHOLD - 1，也就是7个
//转换成红黑树的结构
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; //那就没有再遍历的意思了
//e指向p
p = e;
}
}
//找到了相等的key，只覆盖掉它的值
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() 方法，那么我们先必须了解这个方法的作用是什么。扩容之后，有一个极具消耗性能的过程，那就是：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是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 ( //这个意思就是，新数组容量扩大为原来的一倍，相当于乘以2
(newCap = oldCap << 1) < MAXIMUM_CAPACITY
&&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
//创建hash表
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历旧的hash表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e; //临时节点
//如果旧的数组上当前位置上存在节点，那么将这个节点hash进新数组
if ((e = oldTab[j]) != null) {
//设置旧节点为null，释放引用，便于GC回收
oldTab[j] = null;
//如果当前节点的下个节点为空，也就是说没有造成hash冲突
//则直接重新计算改节点 再对应新hash桶中的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //树节点类型，红黑树结构，单独解析
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 到了里，也就是说存在冲突
/*
这里是需要注意的地方，这个东西如果没懂，那下面的东西自然就看不懂了
这里的操作是，重新hash旧数组的链表上的节点，如果
hash值是不相同的，那么将它拆出来放到新的位置上去
如果相等，那么保留在原来位置上。也就是说，java8版本的rehash
并不是简单的将链表直接复制过去
*/
Node<K,V> loHead = null, loTail = null; //低位首尾节点
Node<K,V> hiHead = null, hiTail = null; //高位首尾节点
Node<K,V> next; //指向的 下一个节点
do {
next = e.next;
//判断当前节点的hash值与旧数组的容量进行与运算，
//如果为0，则节点元素的新下标位置也就不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e; //将当前节点设置为头节点
else
loTail.next = e; //追加到尾节点的后面
loTail = e;
}
//为1。则节点元素的新下标位置为 原来下标 + oldCapacity
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;
}
HashMap的扩容过程
虽然前面源码里讲了，但是这里还是做一个文字叙述，毕竟源码读起来很费劲。
- put操作
- 首先根据键值对的key，调用它本身的hashcode方法，获得hashcode码
- 获取到hashcode之后，按照 index = (table.lenth - 1) & hashcode; 获取在位桶数组中的索引index，这个方法叫相除取余法 或者 取模？
- 判断当前位置上是否有节点，如果有，调用equals比较这个节点的key值（或者是Entry链上的节点），如果相等，hash值也相等，覆盖掉value值。
- 如果不等，并且没达到散列表的阈值 THRESHOLD = 0.75 * capacity，1.7版本的Hashmap是采用前插法，也就是旧数组上的节点被推入链表，新节点代替原节点位置，1.8采用的是后插法，直接插在链表末尾。
- 如果达到阈值，采取扩容操作。首先创建新的数组，这个数组的容量是原来的俩倍，然后将旧数组中的节点重新hash进新数组，这就是rehash。原数组中的每个元素节点都会在新数组中的新位置，如果rehash还是发生的冲突，依然采取前插或者后插进形成链表。值得一提的是，在1.8版本的rehash过程，如果链表上的节点值大于8，实际是>= 7个，当前链表上的元素节点小于64个，那么，单链表将转换成红黑树的结构
总结一下HashMap的1.7于1.8的扩容差别，感受一下1.8的骚操作：
1.7：扩容之后节点采取 index = （table.capacity & hashcode）运算新位桶数组的位置。
1.8：index = 节点.hash值 & 旧数组的capacity，拿个栗子：table.size = 4，由于有个约定，数组的大小为原来的俩倍，实际上在二进制上，就是向左移动了一位，如0100 到 1000，那么，我们只要将它于hash值低位进行与操作，最后就只有0和1，规定来了，0放在原地，索引不变，1放在它处，索引改变。
差别
HashMap为什么要改头插到尾插呢？
在1.7版本的HashMap采用的是头插法，1.8改成了尾插法，这是为什么呢？
我们来看看hashmap本来的存储结构
头插法
在使用头插法的处理方式下，处于A位置的节点往往都是最新插入的节点，原本在该位置的节点会被推入B位置，在这条Entry链下，每一个Entry对象都包含 hash值、key、value、指向下一个Entry的指针，由此形成了ABCD这样一条链。我们重新温习一下resize 的处理过程：
1、创建数组，大小为原来的2倍；
2、将位桶数组上的Entry根据：hash值 = （table.length - 1）& hashcode 公式重新hash进新的数组。
这时候就有一个问题，原本是ABCD这样的形式，使用头插法的方式扩容之后，它先拿A节点，再拿B节点，接着拿C节点，最后拿D节点，计算hash值后，进入新数组的顺序就可能变成了这样DCBA，整个链表会反转过来。
那反转之后会造成什么问题呢？点击这里开始烧脑，后插法则完美的避开了这个问题，但是在多线程场景下，HashMap毕竟不是安全的，请使用性能更好安全性更佳的 CurrendHashMap。
