一.什么是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 方法(大多数翻译为拉链法)+链表和红黑树来解决冲突。

image.png

哈希冲突

当我们通过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位的右移后与原哈希码进行异或而得到，以上面的例子为例。

image.png

此方法保证了高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)

该语句用语判断是否需要进行移动，从而提高效率。

image.png

==* 如何通过保证head 和 tail 来保证链表的顺序和之前一样，（避免产生循环引用？）==

else {
                                if (hiTail == null)
                                    //step1:
                                    hiHead = e;
                                else
                                    //step2:
                                    hiTail.next = e;
                                //step3:    
                                hiTail = e;
                            }

这里以高位举例解析其中部分代码，这里不区分不移动的节点：

image.png

上图说明头节点确认后是不再变的，只在尾节点后追加。

注意：
虽然 HashMap 设计的非常优秀， 但是应该尽可能少的避免 resize(), 该过程会很耗费时间。

同时， 由于 hashmap 不能自动的缩小容量 因此，如果你的 hashmap 容量很大，但执行了很多 remove操作时，容量并不会减少。如果你觉得需要减少容量，请重新创建一个 hashmap。

HashMap的get()过程

image.png

HashMap的put()过程

image.png

参考：
https://my.oschina.net/placeholder/blog/180069
https://mp.weixin.qq.com/s/GfB6yerj3fVm_WqSbVCRqA