从零学习HashMap

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

1.1、什么是哈希表？

先复习一下数据结构

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

哈希表：（数组 + 链表）相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

1.2、哈希表如何工作？

它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。白话一点的说就是通过把Key通过一个固定的算法函数（hash函数）转换成一个整型数字，然后就对该数字对数组的长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

当使用hash表查询时，就是使用hash函数将key转换成对应的数组下标，并定位到该下标的数组空间里获取value，这样就充分利用到数组的定位性能进行数据定位。

• key：我们输入待查找的值
• value：我们想要获取的内容
• hash值：key通过hash函数算出的值（对数组长度取模，便可得到数组下标）
• hash函数（散列函数）：存在一种函数F，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个遍历比较。这样就预先知道key在的位置，直接找到数据，提升效率。 即
• 地址index=F(key) hash函数就是根据key计算出该存储地址的位置，hash表就是基于hash函数建立的一种查找表。

1.3、什么是哈希冲突？

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。通过构造性能良好的hash函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是hash表的另一个关键问题。 创建和查找hash表都会遇到冲突，两种情况下解决冲突的方法应该一致。

哈希冲突的解决方案：

开放定址法: 这种方法也称再散列法，基本思想是：当关键字key的hash地址p=F(key)出现冲突时，以p为基础，产生另一个hash地址p1，如果p1仍然冲突，再以p为基础，再产生另一个hash地址p2，。。。知道找出一个不冲突的hash地址pi，然后将元素存入其中。

线性探测法

链地址法（拉链法，位桶法）:将产生冲突的关键字的数据存储在冲突hash地址的一个线性链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。

2、HashMap的实现原理是什么？1.7和1.8有哪些区别？

JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，那么他们为什么要这样做呢？因为JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。

扩容后数据存储位置的计算方式也不一样：1. 在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1）。而在JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。

JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率）

为什么当桶中键值对数量大于8才转换成红黑树，数量小于6才转换成链表？

因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。还有选择6和8，中间有个差值7可以有效防止链表和树频繁转换。

2.1、什么是头插法？

在头结点（为了操作方便，在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以存储数据标题、表长等信息，也可以不存储任何信息，其指针域存储第一个结点的首地址）H之后插入数据，其特点是读入的数据顺序与线性表的逻辑顺序正好相反

2.2、什么是尾插法？

将每次插入的新结点放在链表的尾部，尾插法就是要使后面插入的结点在前一个插入结点和NULL值之间。

2.3、1.8之后为什么改为尾插法？

主要是为了安全,防止多线程下形成环化 因为resize的赋值方式，也就是使用了单链表的头插入方式（1.8之前），同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

就可能出现下面的情况，大家发现问题没有？

B的下一个指针指向了A

一旦几个线程都调整完成，就可能出现环形链表

如果这个时候去取值，就出现了无限循环的状态..

使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了

2.3.1、hashmap的扩容原理

什么时候进行扩容？也就是resize

有几个因素：

• Capacity：HashMap当前长度。
• DEFAULT_LOAD_FACTOR：负载因子，默认值0.75f。

• DEFAULT_INITIAL_CAPACITY

  

• • 为啥用位运算？不直接写16？

    位移运算符 效率高

• • 为啥选择16呢？

    如果两个元素不相同,但是hash函数的值相同,这两个元素就是一个碰撞

    因为把任意长度的字符串变成固定长度的字符串,所以存在一个hash对应多个字符串的情况,所以碰撞必然存在

    为了减少hash值的碰撞,需要实现一个尽量均匀分布的hash函数,在HashMap中通过利用key的hashcode值,来进行位运算 公式:index = e.hash & (newCap - 1)

    举个例子: 1.计算"book"的hashcode 十进制 : 3029737 二进制 : 101110001110101110 1001

    2.HashMap长度是默认的16，length - 1的结果 十进制 : 15 二进制 : 1111

    3.把以上两个结果做与运算 101110001110101110 1001 & 1111 = 1001 1001的十进制 : 9,所以 index=9

    hash算法最终得到的index结果,取决于hashcode值的最后几位

    为了推断HashMap的默认长度为什么是16 现在,我们假设HashMap的长度是10,重复刚才的运算步骤: hashcode : 101110001110101110 1001 length - 1 : 1001 index : 1001

    再换一个hashcode 101110001110101110 1111 试试: hashcode : 101110001110101110 1111 length - 1 : 1001 index : 1001

    从结果可以看出,虽然hashcode变化了,但是运算的结果都是1001,也就是说,当HashMap长度为10的时候,有些index结果的出现几率 会更大而有些index结果永远不会出现(比如0111),这样就不符合hash均匀分布的原则.

    在使用是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。可以降低hash碰撞的几率。

言归正传，到底什么时候进行扩容呢，假定默认长度就是16，负载因子0.75f, 16 * 0.75 = 12 , 那么在put第13个的时候就会进行resize。

2.3.2、hashmap扩容分为两步

• 扩容：创建一个新的Entry空数组，长度是原数组的2倍。

• ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

• • 为什么要重新Hash呢，不直接复制过去？

    因为长度扩大以后，Hash的规则也随之改变。

    Hash的公式---> index = HashCode（Key） & （Length - 1）

2.3.3、拓展：重写equals方法的时候需要重写hashCode方法？

因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址。

== 比较的是两个对象的地址
复制代码

在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

在结合HashMap说一下，HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”张三“和”李四“的index可能是一样的，在一个链表上的。我们去get的时候，他就是根据key去hash然后计算出index，找到了index，那我怎么找到具体的”张三“和”李四“呢？就是用到了equals方法！虽然它们的hashCode一样，但是他们并不相等。

3、JDK1.8中HashMap性能优化之红黑树

3.1、什么是红黑树？

红黑树也叫自平衡二叉查找树或者平衡二叉B树。二叉树不用多说，二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

时间复杂度为O(log n)

高度h <= log2(n+1)

3.1.1、红黑树的主要特性:

• 每个节点要么是黑色，要么是红色。（节点非黑即红）
• 根节点是黑色。
• 每个叶子节点（NIL）是黑色。
• 如果一个节点是红色的，则它的子节点必须是黑色的。（也就是说父子节点不能同时为红色）
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。（这一点是平衡的关键）
• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

HashMap中的代码

TreeNode继承自LinkedHashMap中的内部类——LinkedHashMap.Entry，而这个内部类又继承自Node，所以算是Node的子类。parent用来指向它的父节点，left指向左孩子，right指向右孩子，prev则指向前一个节点（原链表中的前一个节点），注意，这些字段跟Entry，Node中的字段一样，是使用默认访问权限的，所以子类可以直接使用父类的属性。

3.1.2、红黑树的左旋和右旋:

将节点以某个节点为中心向左或者向右进行旋转操作以保持二叉树的平衡

左旋：

我们要对节点A执行左旋的操作，那我们就需要执行接下来的几个操作：

①将A的右子树设置为D；

②如果D不为空，则将D的父节点设置为A；

③将C的父节点设置为A的父节点；

④如果A的父节点为空，则将C设置为root节点，如果A为父节点的左子树，则将C设置为A父节点的左子树，如果A为父节点的右子树，则将C设置为A父节点的右子树；

⑤将C的左子树设置为A；

⑥将A的父节点设置为C。

执行完成后的树形结构如下图：

动图展示：

右旋：

①将A的左子树设置为E；

②如果E不为空，则将E的父节点设置为A；

③将B的父节点设置为A的父节点，如果A的父节点为空，则将B设置为root节点，如果A为父节点的左子树，则将B设置为A父节点的左子树，如果A为父节点的右子树，则将B设置为A父节点的右子树；

④将B的右子树设置为A；

⑤将A的父节点设置为B。

执行完成后的树形结构如下图：

动图展示：

4、源码分析

4.1、插入（put）

插入的时候做了哪些动作？

找了一个牛X的流程图

① 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

② 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③ 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④ 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤ 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥ 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

源码：

HashMap<Object, Object> hashMap = new HashMap<>();
hashMap.put("a",1); 

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;
        // 步骤①：tab为空则创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 步骤②：计算index，并对null做处理（n 为数组长度）
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K, V> e;
            K k;
            // 步骤③：节点key存在，直接覆盖value
            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);
                        //链表长度大于8转换为红黑树进行处理
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;

                    }
                    // key已经存在直接覆盖value
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k)))) break;
                    p = e;

                }

            }

            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;

    }
复制代码

index计算方式：

index = hashCode(key) & (当前table长度length - 1)
复制代码

扩容：

final Node<K,V>[] resize() {
    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) {
            // 阀值设为int最大值
            threshold = Integer.MAX_VALUE;
            // 返回老的数组，不再扩充
            return oldTab;
        }// 如果老的容量*2 小于最大容量并且老的容量大于等于默认容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新的阀值也再老的阀值基础上*2
            newThr = oldThr << 1; // double threshold
    }// 如果老的阀值大于0
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 新容量等于老阀值
        newCap = oldThr;
    else {  // 如果容量是0，阀值也是0，认为这是一个新的数组，使用默认的容量16和默认的阀值12           
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的阀值是0，重新计算阀值
    if (newThr == 0) {
        // 使用新的容量 * 负载因子（0.75）
        float ft = (float)newCap * loadFactor;
        // 如果新的容量小于最大容量 且 阀值小于最大 则新阀值等于刚刚计算的阀值，否则新阀值为 int 最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    } 
    // 将新阀值赋值给当前对象的阀值。
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        // 创建一个Node 数组，容量是新数组的容量（新容量要么是老的容量，要么是老容量*2，要么是16）
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 将新数组赋值给当前对象的数组属性
    table = newTab;
    // 如果老的数组不是null
    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)
                    // 调用红黑树 的split 方法，传入当前对象，新数组，当前下标，老数组的容量，目的是将树的数据重新散列到数组中
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 如果既不是树，next 节点也不为空，则是链表，注意，这里将优化链表重新散列（java 8 的改进）
                  // Java8 之前，这里曾是并发操作会出现环状链表的情况，但是Java8 优化了算法。此bug不再出现，但并发时仍然不建议HashMap
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 这里的判断需要引出一些东西：oldCap 假如是16，那么二进制为 10000，扩容变成 100000，也就是32.
                        // 当旧的hash值 与运算 10000，结果是0的话，那么hash值的右起第五位肯定也是0，那么该于元素的下标位置也就不变。
                        if ((e.hash & oldCap) == 0) {
                            // 第一次进来时给链头赋值
                            if (loTail == null)
                                loHead = e;
                            else
                                // 给链尾赋值
                                loTail.next = e;
                            // 重置该变量
                            loTail = e;
                        }
                        // 如果不是0，那么就是1，也就是说，如果原始容量是16，那么该元素新的下标就是：原下标 + 16（10000b）
                        else {
                            // 同上
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 理想情况下，可将原有的链表拆成2组，提高查询性能。
                    if (loTail != null) {
                        // 销毁实例，等待GC回收
                        loTail.next = null;
                        // 置入bucket中
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}


复制代码

4.2、查询(get)

HashMap 的查找操作比较简单，

• 先定位键值对所在的哈希桶数组的位置

• table[index]的首个元素是否和key一样(hash、equals都相等)，如果相同则返回该value

• 如果不相同判断首个元素的类型，然后再对链表或红黑树进行查找。

源码：

HashMap<Object, Object> hashMap = new HashMap<>();
hashMap.put("a",1);
hashMap.get("a");


public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 定位键值对所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //2.哈希桶的首个元素是否和key一样(hash、equals都相等)，如果相同则返回该value
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 3. 如果 first 是 TreeNode 类型，则调用黑红树查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
            // 4. 对链表进行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
复制代码

有时间后续在更详细的分析源码部分。