Java 集合框架_HashMap JDK1.8新算法

在讲解HashMap之前，我们先说一说HashMap中一些比较重要的算法，这个是我们理解HashMap源码的关键。

一. 哈希化

1.1 用位运算实现哈希化

我们知道HashMap是基于哈希表实现的，而且是链地址法实现的哈希表(即数组加链表的形式)。

哈希表的关键是哈希化，就是将很大的哈希值转化成变成一定区间范围内的值，在上一章中我们采用了取余%操作来实现哈希化的。但是我们知道取余%是非常耗费性能的，尽量不要使用这种方式，那怎么实现高效率的哈希化呢？

我们知道两个数最快的运算方式是位运算，那么怎么样使用位运算将较大的哈希值hashCode变成一定区间范围内的值呢？

那就使用&运算。我们知道如果有一个数它的高位都是0.低位都是1，即0b000011111...这种形式。它与任何一个数进行&运算，得到的结果值都不可能大于这个数。例如0b111 & 0b1010111010010 = 0b010。因为&运算只有两位都是1才是1，否则就是0.

那怎么得到0b000011111...这种形式的数?

有一个非常简单的方法，如果一个数是2的幂数，即0b0001000...这种形式，例如 2、4、8、16、32等等。这个数减一得到的数就是0b000011111...这种形式。例如8-1 =7(0b111)。

这个就解释了为什么HashMap数组的长度必须是2的幂数，因为这样就可以使用&运算的方式实现哈希化。即 (table.length - 1) & hashCode。

这个也是一个公式，即 任何一个数x % 2^n都可以转成 数x & (2^n - 1)。也就是说数x对2^n进行取余，本质上是返回数x 低n位二进制数。这个很重要，对我们理解resize()方法由很大帮助，具体请看后面对resize()方法的详解。

1.2 哈希值高位失效问题

但是这里还是有个问题，那就是哈希值hashCode高位失效。

因为&运算导致哈希值hashCode的高位不管是0或者1，与0相与结果都是0，会导致很多不同的哈希值hashCode只要低位是相等的，那么哈希化(即相与操作)得到的值是一样的。
它们会存到同一个链表中，导致哈希表中有的数组存放的链表很长，有的却是为空，很影响哈希表的效率。

怎么处理hashCode高位失效问题呢？就要用到HashMap中一个静态方法int hash(Object key)。

   static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

看到这种表达式，一定很懵逼，一步一步分析它的作用。

先看一下它是怎么处理的,h表示key值的哈希值。h >>> 16表示右移16位，我们知道一个int整形有32位，右移16位表示丢弃高16位的数据，因为都变成高16位都变成0了，然后再和原来的h值进行异或^。

要知道一个事实就是异或^0，每一位保持不变。0b101 ^ 0b000 = 0b101。h ^ (h >>> 16)得到的结果我们知道高16位是不变的，低16位才可能发生改变，而且它的改变是与高16位数有关的，这样就将高16位的数据也利用起来，减缓了高位失效。

三. 数组长度

根据上一节我们知道，HashMap中数组的长度必须是2的幂数。

  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;
    }

我们知道当哈希表元素的个数超出哈希表阈值(即数组长度*负载因子),就要进行数组扩容，而根据上一节我们知道，HashMap中数组的长度必须是2的幂数。
所以这个方法就是返回一个与cap最近的2的幂数。

怎样返回一个与cap最近的2的幂数呢？有一个简单地方法。
int n = 1; while (n < cap) n <<= 1;
这个实现方式很容易理解，因为n开始值是1，而n <<= 1得到的值一定也是2的幂数,然后利用循环，找出比cap大(包括等于)的数。
这种方式简单易懂,以前HashMap就是用这种方式计算的，但是可能觉得两个数判断大小很耗时间或者循环比较耗时间，所以使用了上面这种全新的算法(我只想说mmp)

上面这种算法理解起来就比较麻烦了。

1. 首先我们确定一个事实，一个不是0正整数，它可以表示0b0001XXX这种形式，我们就用0b1000做示范。
2. 第一步 n |= n >>> 1 即 0b1000 | 0b0100 = 0b1100
3. 第二步 n |= n >>> 2 即 0b1100 | 0b0011 = 0b1111
4. 第三步 n |= n >>> 4 即 0b1111 | 0b0000 = 0b1111

不知道大家看出来什么规律了么？

• 第一步将n右移一位，再与n相或，它的作用就是将n从0b0001XXX变成0b00011XX形式。
• 再看第二步，n右移两位，那么就是将n从0b00011XX变成0b0001111形式。
• 第三步时，发现值没有变化，那是因为我们已经将n完成转换成0b0001111...形式。
• 因为int是32位的，所以需要n |= n >>> 16才能确保覆盖整个整数范围,最后我们再使用n = n+1,将n从0b0001XXX变成0b0010000形式(也就是2的幂数)

还有个疑惑，这里为什么要n = cap - 1，因为按照我们的逻辑，直接使用cap也可以啊。

这就考虑的一个边界问题了，如果cap就是2的幂数，比如是8(即0b1000)，按照算法我们将它变成0b1111形式，最后再加1，就变成了16(即0b10000),那么就就对了，因为与8最近2的幂数应该就是8，与9最近2的幂数才是16。所以这里先cap - 1将8变成7(0b111)，最后结果还是8。

最后n >= MAXIMUM_CAPACITY判断条件，是因为HashMap 数组最大长度是1 << 30，所以要判断最大值。

四. 数组扩容

数组扩容对于基于数组实现的集合都是很重要的方法，比如ArrayList和HashMap。而HashMap的数组扩容就更加麻烦，它涉及到再哈希的问题。

因为扩容后的数组长度与原来数组长度是不一样的，那么哈希化之后得到的下标值也有可能是不一样的。

4.1 再哈希问题新算法

HashMap的数组扩容是通过resize()方法实现的，这个方法最重要的就是将老数组中全部键值对存放到新数组中。也就是再哈希问题

一种简单的方法，就是先遍历老数组，获取对应链表，再遍历链表，得到每个键值对，然后对键值对的key进行新数组的哈希化，得到一个下标值，然后进行处理。看一看以前版本jdk是怎么处理这个问题的。

    // jdk老版本进行重新哈希化的算法
    // 将HashMap中的全部元素都添加到newTable中
    void transfer(Entry[] newTable) {
        // HashMap老的哈希表
        Entry[] src = table;
        // 新的哈希表长度
        int newCapacity = newTable.length;
        // 遍历老的哈希表
        for (int j = 0; j < src.length; j++) {
            // 得到j下标处的链表
            Entry<K, V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K, V> next = e.next;
                    // 得到新的哈希化的下标值
                    int i = indexFor(e.hash, newCapacity);
                    // 将元素e插入到链表的表头
                    e.next = newTable[i];
                    newTable[i] = e;
                    // 将next赋值给e，遍历老的链表
                    e = next;
                } while (e != null);
            }
        }
    }

老版本代码逻辑比较简单：

1. 遍历老的哈希表，得到链表头元素e，以及下一个元素next，并求出新的哈希化下标值i。
2. 将e插入新的哈希表i下标位置链表的表头。通过公式e.next = newTable[i]，newTable[i] = e来实现
3. 将next赋值给e，循环遍历老的链表
   这种实现方式简单明了，容易让人理解。但是有个问题，就是得到的新链表和老链表是反向的，因为我们遍历老链表是从头到尾的，但是插入新链表却是从头插入。

jdk1.8对再哈希问题提供了全新的算法。我们知道HashMap集合数组长度必须是2的幂数(2^n)， 而且每次扩容老数组的一倍，即2^(n+1)。

1. 集合中数组数量是2的幂数2^n即0b00010000..这种形式，进行哈希化，就是用一个数x & (2^n - 1) 返回的就是数x低位的二进制数(即低n位的二进制数)

例如 长度是4(2^2) 0b00100，那么3(2^2 - 1) 0b00011。
数x分别是3 0b00011 7 0b00111 15 0b01111，它们 & 3 得到都是3，也就是它们在低位(低2位)的表现形式。

2. HashMap集合进行数组扩容时，得到新数组长度就是2^(n+1)，对新数组进行哈希化，就变成了 数x & (2^ (n + 1) - 1), 返回的是数x低n+1位的二进制数。

这个时候我们发现与扩容前相比，哈希化的下标值低n位是不变的，有可能改变的是就是第n+1位(从低往高数)。

• 如果第n+1位是0，那么新的哈希化的得到的下标值和原来的是一样的。
• 如果第n+1位是1，那么新得到的下标值与原来相比，要加上 2^n (即原数组长度)。

例如 长度就从4(2^2) 变成了8(2^3) 0b01000, 那么7(2^3 - 1) 0b00111。
数x分别是3 0b00011 7 0b00111 15 0b01111，它们 & 7 得到的分别是 3，7， 7，也就是它们在低位(低3位)的表现形式。

注意 第n+1位对应的数是2^n, 比如说第3(2+1)位对应的数是4(2^2)，即0b100.

因此我们发现对新数组进行哈希化，有了更好的方式，不需要使用数x & (2^(n+1) - 1)得到新的下标值。变成判断数x的第n+1位(从低往高数)是0还是1。

判断数x的第n+1位是0还是1，也有个很简单的方式。就是用数x & 2^n ,因为2^n 只有第n+1位是1，其他位置都是0。那么它与任何数相&只有两个结果，0表示数x第n+1是0，1表示数x第n+1位是1.而2^n就是老数组的长度。

4.2 再哈希新算法代码实现

先遍历老数组，用j表示数组下标，获取下标j对应位置的链表e，如果链表e不为null，那么下标j就是链表e中键值对对应的哈希值。
根据链表中元素的数量分为两种情况：

1. 链表元素数量为1

if (e.next == null)  newTab[e.hash & (newCap - 1)] = e;

当e.next为null，那么链表只有一个元素。发现这里使用了e.hash & (newCap - 1)计算新的下标值，然后直接将e赋值到这个位置。这时我们就有两个疑惑了。

• 为什么没有用新的方式计算下标值呢？这里其实是可以用新的计算方式的,例如：

int newIndex = (e.hash & oldCap) == 0 ? j : j + oldCap;
newTab[newIndex] = e;

这个得到的newIndex值与e.hash & (newCap - 1)得到的值是一样的，而且计算起来更加麻烦，这里就不用这种方式。

• 为什么直接将e赋值给newTab数组，难道不怕newTab数组该位置已经有了元素，而导致被覆盖情况么?

既然源码这么写的，那么就不可能出现覆盖情况，这时为什么呢?
我们说过新数组和老数组哈希化得到的值只有一个位会可能不一样，也就是说新数组哈希化得到的下标值，要么与老数组哈希化得到的值一样，要么是老数组哈希化得到的值加上老数组的长度。
也就是说老数组链表中的元素会被分配到这个两个位置的链表中，而当前位置链表长度为1，它只能分配到一个位置，不会发生覆盖情况。

2. 链表元素数量不为1

      else {
                        // loHead表示放入当前j位置链表的链表头，loTail表示链表尾，
                        // 因为Node是单向链表，所以要用链表尾变量，将键值对插入到链表尾
                        Node<K,V> loHead = null, loTail = null;
                        // loHead表示放入当前j+oldCap位置链表的链表头，loTail表示链表尾，
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // (e.hash & oldCap) == 0 表示对n+1位是0，那么它在新数组中的哈希化后的值和原来的一样
                            // 将元素放入loHead链表中
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                            // 用while循环遍历这个链表
                        } while ((e = next) != null);
                        // 将链表放到新数组对应位置。
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }

那么这个链表就可能分为两个链表，放到本下标j位置，以及j+ oldCap下标位置。
所以我们要创建两个变量loHead和hiHead表示这两个链表，但是如果我们要保持链表的顺序不变，就还要创建两个变量loTail和hiTail表示链表尾，这样遍历链表的时候，就可以向新链表 链表尾插入元素，保证新链表的顺序和老链表一样。
具体步骤：

1. 通过while循环遍历链表。
2. 然后用(e.hash & oldCap) == 0 判断式，决定链表中的元素插入到那个链表中。
3. 将两个链表放入新数组对应位置。

4.3 resize()方法详解

     final Node<K,V>[] resize() {
        // 使用oldTab表示原来的数组
        Node<K,V>[] oldTab = table;
        // oldCap表示老数组的长度， oldThr表示老的阈值
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        // newCap表示新数组的长度， newThr表示新的阈值
        int newCap, newThr = 0;
        // oldCap > 0表示table数组已经创建了
        if (oldCap > 0) {
            // 老数组长度已经最大容量了，那么就不能进行数组扩容，直接返回老数组
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 对老数组长度进行2倍扩容。
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0)
            // table数组还没有创建，threshold代表的是数组的长度，所以赋值给新数组的长度
            newCap = oldThr;
        else {
            // table数组还没有创建，且threshold为0，只有一种情况，那就是使用默认无参构造函数创建的Map集合
            // 所以使用默认的初始数组长度DEFAULT_INITIAL_CAPACITY(16)
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 这时可以直接计算出它的阈值， 即默认数组长度 16 * 默认负载因子 0.75f
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            // 因为新的数组长度newCap可能很大，所以要考虑超过最大容量上限问题，
            // 如果出现那样的情况，那么新的阈值就是int型最大值Integer.MAX_VALUE
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 将新阈值赋值给threshold
        threshold = newThr;
        // 根据新的数组长度创建新的数组newTab，并将它赋值给table
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 如果老数组不为空，那么就要将老数组中键值对元素迁移到新数组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 {
                        // loHead表示放入当前j位置链表的链表头，loTail表示链表尾，
                        // 因为Node是单向链表，所以要用链表尾变量，将键值对插入到链表尾
                        Node<K,V> loHead = null, loTail = null;
                        // loHead表示放入当前j+oldCap位置链表的链表头，loTail表示链表尾，
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // (e.hash & oldCap) == 0 表示对n+1位是0，那么它在新数组中的哈希化后的值和原来的一样
                            // 将元素放入loHead链表中
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                            // 用while循环遍历这个链表
                        } 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;
    }

这个方法返回扩容之后的新数组，主要可能进行那个步骤，创建符合长度的新数组，确定新的阈值threshold，将老数组中元素移到新数组中。
这个还分为三种情况：

1. 老数组存在，一般是将老数组进行两倍扩容，但是如果老数组长度已经是最大容量MAXIMUM_CAPACITY，不能再扩容了，那么就直接返回老数组。
2. 老数组不存在，那么阈值threshold就是新数组的长度，还有一种特殊情况，就是threshold也是0。那么它是HashMap空参构造函数创建的，特殊处理。
3. 将老数组元素移动到新数组，这个在再哈希过程详细说了。

未完待续