今天来讲一个老生常谈，都被讲烂的一个问题，网上随便一搜hashmap，各式各样的文章，今天从源码入手带你一行一行地重新了解hashmap。但是重点是放在了本身的原理，至于多线程问题，jdk1.7，1.8的区别，会重新出一篇文章来讨论。
本文讲解前默认各位小伙伴是已经会hashmap的用法的了，怎么样都有过new HashMap<>() 的经验，着重讲的是原理。
工作原理
结构组成
image-20210423133546475
put
- 首先是或者对插入对象的key的hash值进行扰动得到「新的hash值」，简单来讲是为了更好的散列
- 根据hash值找到需要插入值的下标，然后对链表进行相应的操作，在末尾插入，hash冲突，转化成红黑树
- 如果有需要，则进行扩容
get
获取值的时候就比较简单了，直接根据key的hash找到桶的下标，再遍历链表找到值就好了。
「注意：key对象本身有个hash值，但是put和get的时候是经过了hash算法进行了扰动生成了新的hash值，但是对象本身的hash值不变。」
成员变量
肯定是挑重点的说先，其它的有了基础后可以自行去源码中查找学习，这样更有成就感。
内部类-Node
通过一开始也知道，HashMap 是由「数组加链表」组成的，其实本质就是多个下面Node<K,V>组成的数组 。
node-hashmap
其实好像也没啥好讲的，知道有这么一个类，类里面有那些成员变量就好了。
成员变量
fields-hashmap
可能有小伙伴会发现了，怎么没有capcity 容量这个成员变量呀。需要注意的是jdk1.8之后，「桶数组的初始化不是在构造函数内完成的，而是在第一次put的时候完成的」，所以不设capcity这个变量完全没问题。
构造函数
构造函数大体来说有两种，一种是给成员变量赋值，一种是复制一个新的map
construct-hashmap
上面有两个函数tableSizeFor() 和putMapEntries() 有兴趣的小伙伴可以去看下源码，实现比较简单，这里就不再赘述。
Put
hash()
让我们来看下put的源码
代码语言：javascript复制public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
首先运行的是一个hash() 的函数
static final int hash(Object key) {//hash算法
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先int h = key.hashCode() h是一个4字节32位的数，接着是异或上h >>> 16 最后得到了新的hash值。
h是个32位的数，那么它右移16位后，高位（前16位）为0，而x ^ 0 = x。所以整个上面一句话的作用就是「保留高位，低位和高位异或」，这样子能达到的目标就是扰乱了低位，且低位具有高位的一部分属性。
接下来的重点就到了putVal() ，需要分为第一次put和其它put来讲。
第一次put
第一次put时候的putVal()
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;
//.....
}
当第一次put的时候，table肯定是为空的，也就是if ((tab = table) == null || (n = tab.length) == 0) 判断返回为true，走到resize() 流程。
来看看第一次put的时候resize是怎么运作的
init-hashmap
通过源码可以看到真正的table数组是在「第一次put中」的putVal() 中的resize() 时才「初始化。」
正常put
看源码，首先会有一个根据hash计算该key应该放在哪个桶下面，「n是桶数组的长度，永远是2的幂。」 反映在二进制就是只有某一位是1，其它全是0。这样的情况下，n - 1就是尾部全是1，其它全是0。（n - 1） & hash就是保留hash值中数组长度低位的数，高位的数置0。
假设n = 16，那么n - 1 = 15 = 00001111，这样与上hash相当于只保留了hash的后4位。
normalPut-hashmap
扩容
可以发现上述源码中在最后还有一个resize() ，可见resize() 除了初始化的时候有用，更多时候是用在扩容这方面。
上面源码注释中也有写到是当k-v个数 > 扩容阈值 = table数组容量 * 负载因子（默认是0.75）的时候开始扩容，table数组变成原来的2倍，旧k-v重新散列在新数组中。
resize-hashmap
我把后面的拆开来说，因为其一是因为其巧妙，其二是因为太长了看着疲惫
停一下
可以提前说下，jdk的思想是「把链表拆分成两部分」进行散列。想拆成2部分必须用hash经过某种运算得到两种结果，计算机里面自然就想到了0，1。一个数和另一个数得到0和1，所以可以想到&运算，且其中一个数只有1位是1，其它都是0。
所以算法就是hash（注意，是扰动前的hash）& newCap 这样得到的结果就只有0和1了。
rehash-hashmap
Get
相比之前的插入和扩容函数，get() 相对来说就简单了
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
可以看到最终到了getNode() 函数
get-hashmap
