一.什么是hash表
不同数据结构的操作性能：
1.数组
下标查找：O(1)
值查找:遍历O(n),二分查找O(logn),插入删除平均O(n)
2.线性链表
查找、更新:O(n)
新增、删除:O(1)
3.二叉树
平均O(logn)
4.哈希表
哈希表中进行添加，删除，查找等操作,不考虑hash冲突O(1);
二.HashMap的基本结构
在 Java 的 HashMap 中， 采用了第一种 Separate chaining 方法(大多数翻译为拉链法)+链表和红黑树来解决冲突。
哈希冲突
当我们通过Hash函数得出的实际存储地址相同怎么办？
在 HashMap 中， 哈希碰撞之后会通过 Node 类内部的成员变量 Node<K,V> next; 来形成一个链表(节点小于8)或红黑树（节点大于8， 在小于6时会从新转换为链表）， 从而达到解决冲突的目的。
static final int UNTREEIFY_THRESHOLD = 6;
什么是Hash？
最简单形式的 hash，是一种在对任何变量/对象的属性应用任何公式/算法后， 为其分配唯一代码的方法。
哈希函数每次在相同或相等的对象上应用哈希函数时, 应每次返回相同的哈希码。换句话说, 两个相等的对象必须一致地生成相同的哈希码。
Java 中所有的对象都有 Hash 方法。
Java中的所有对象都继承 Object 类中定义的 hashCode() 函数的默认实现。 此函数通常通过将对象的内部地址转换为整数来生成哈希码，从而为所有不同的对象生成不同的哈希码。
3.HashMap的代码实现：
HashMap的Node结构:
Node是HashMap用来存储键值对的数据结构，其基本结构如下：
static class Node<K,V> implements Map.Entry<K,V> {
// key的hash值
final int hash;
// key值
final K key;
// value值
V value;
// 链表下一个节点
Node<K,V> next;
HashMap如何存储包含键值对的Node?
键值对在 HashMap 中是以 Node 内部类的数组存放的，如下所示：
transient Node<K,V>[] table;
通过计算出来的Hash码，转换成该数组的下标，在该下标的位置存储对应的Node.
该数组对应的长度始终是2的次幂，如下函数:
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
其原理是将传入参数 (cap) 的低二进制全部变为1，最后加1即可获得对应的大于 cap 的 2 的次幂作为数组长度。
为什么要使用2的次幂作为数组的容量呢？
在此有涉及到 HashMap 的 hash 函数及数组下标的计算， 键(key)所计算出来的哈希码有可能是大于数组的容量的，那怎么办？ 可以通过简单的求余运算来获得，但此方法效率太低。HashMap中通过以下的方法保证 hash 的值计算后都小于数组的容量。
(n - 1) & hash
这也正好解释了为什么需要2的次幂作为数组的容量。由于n是2的次幂，因此，n-1类似于一个低位掩码。通过与操作，高位的hash值全部归零，保证低位才有效 从而保证获得的值都小于n。
以默认的初始值16为例。
01010011 00100101 01010100 00100101
& 00000000 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000000 00000101 //高位全部归零，只保留末四位
// 保证了计算出的值小于数组的长度 n
但是，使用了该功能之后，由于只取了低位，因此 hash 碰撞会也会相应的变得很严重。这时候就需要使用「扰动函数」。（原来扰动函数是hash()方法...）
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
该函数通过将哈希码的高16位的右移后与原哈希码进行异或而得到，以上面的例子为例。
此方法保证了高16位不变， 低16位根据异或后的结果改变。计算后的数组下标将会从原先的5变为0。
使用了 「扰动函数」 之后， hash 碰撞的概率将会下降。 有人专门做过类似的测试， 虽然使用该 「扰动函数」 并没有获得最大概率的避免 hash 碰撞，但考虑其计算性能和碰撞的概率， JDK 中使用了该方法，且只hash一次。
HashMap如何进行初始化？
以下是初始化的代码：
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;
this.threshold = tableSizeFor(initialCapacity);
}
参数：initialCapacity(初始化容量)、loadFactor(负载因子)
通过该函数进行了容量和负载因子的初始化，如果是调用的其他的构造函数， 则相应的负载因子和容量会使用默认值（默认负载因子=0.75， 默认容量=16）。在此时， 还没有进行存储容器 table 的初始化， 该初始化要延迟到第一次使用时进行。
HashMap如何进行扩容？
transient Node<K,V>[] table;
所谓扩容，就是在table数组的容量达到阀值的时候，需要进行扩容.
int threshold;
扩容发生的条件？
初始化的话只要数值为空或者数组长度为 0 就会进行。 而扩容是在元素的数量大于阈值（threshold）时就会触发。
threshold = loadFactor * capacity
比如 HashMap 中默认的 loadFactor=0.75, capacity=16, 则。
threshold = loadFactor * capacity = 0.75 * 16 = 12
那么在元素数量大于 12 时， 就会进行扩容。 扩容后的 capacity 和 threshold 也会随之而改变。
负载因子:影响扩容触发的阀值，值较小的时候，哈希碰撞就很少，存取性能比较高，但是会占用较多内存。值较大时，哈希碰撞很多，性能比较低，需要较少内存。不建议修改。
扩容的过程：
JDK1.7
void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //！！将数据转移到新的Entry数组里
table = newTable; //HashMap的table属性引用新的Entry数组
threshold = (int)(newCapacity * loadFactor);//修改阈值
}
使用一个容量更大的数组来代替已有的容量小的数组；transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里；
transfer()函数的代码
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
注释标记[1]处，将newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话)；
indexFor()是计算每个元素在数组中的位置，源码：
static int indexFor(int h, int length) {
return h & (length-1); //位AND计算
}
这样，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上；
例如，旧数组容量为16，对象A的hash值是4，对象B的hash值是20,对象C的hash值是36；
通过indexFor()计算后，A、B、C对应的数组索引位置分别为4,4,4; 说明这3个对象在数组的同一位置上，形成了Entry链；
旧数组扩容后容量为16*2，重新计算对象所在的位置索引，A、B、C对应的数组索引位置分别为4,20,4; B对象已经被放到别处了；
JDK1.8
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)
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
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 { // 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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
//step1:
hiHead = e;
else
//step2:
hiTail.next = e;
//step3:
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;
}
大概步骤为：
1.将容量修改为扩容后的容量
2.将阀值赋值为扩容后的阀值
3.创建新的Node数组，将老数组的引用更新为新数组
4.将老数组中的Node节点重新hash到新的数组中。（注意对于只有单个节点、链表、红黑树的情况处理不同）
这里解释一下对于链表的情况：
前面说过了数组的容量为 2 的整次幂， 同时， 数组的下标通过下面的代码进行计算。
index = (table.length - 1) & hash
该方法除了可以很快的计算出数组的索引之外， 在扩容之后， 进行重 hash 时也会很巧妙的就可以算出新的 hash 值。 由于数组扩容之后， 容量是现在的 2 倍， 扩容之后 n-1 的有效位会比原来多一位， 而多的这一位与原容量二进制在同一个位置。 示例。
if ((e.hash & oldCap) == 0)
该语句用语判断是否需要进行移动，从而提高效率。
==* 如何通过保证head 和 tail 来保证链表的顺序和之前一样，（避免产生循环引用？）==
else {
if (hiTail == null)
//step1:
hiHead = e;
else
//step2:
hiTail.next = e;
//step3:
hiTail = e;
}
这里以高位举例解析其中部分代码，这里不区分不移动的节点：
上图说明头节点确认后是不再变的，只在尾节点后追加。
注意：
虽然 HashMap 设计的非常优秀， 但是应该尽可能少的避免 resize(), 该过程会很耗费时间。
同时， 由于 hashmap 不能自动的缩小容量 因此，如果你的 hashmap 容量很大，但执行了很多 remove操作时，容量并不会减少。如果你觉得需要减少容量，请重新创建一个 hashmap。
HashMap的get()过程
HashMap的put()过程
参考：
https://my.oschina.net/placeholder/blog/180069
https://mp.weixin.qq.com/s/GfB6yerj3fVm_WqSbVCRqA
