(大厂进阶)全网HashMap最全面试题(附答案)-IT乾坤技术博客

文章首发于我的个人博客，到个人博客体验更佳阅读哦

> <a href='https://www.itqiankun.com/article/hashmap-basic-question' target ='_blank'>https://www.itqiankun.com/article/hashmap-basic-question</a>

[TOC]

## hashmap基础

### hashmap的node

hashmap类有一个非常重要的属性Node<K,V>  是hashmap的一个内部类，实现Entry接口，本质上是一个映射

可以看到，Node类的基本属性有：

> hash：key的哈希值

> key：节点的key，类型和定义HashMap时的key相同

> value：节点的value，类型和定义HashMap时的value相同

> next：该节点的下一节点

值得注意的是其中的next属性，记录的是下一个节点本身，也是一个Node节点，这个Node节点也有next属性，记录了下一个节点，于是，只要不断的调用Node.next.next.next……，就可以得到：

Node-->下个Node-->下下个Node……-->null

这样的一个链表结构，而对于一个HashMap来说，只要明确记录每个链表的第一个节点，就能顺序遍历链表上的所有节点。

### hashmap的容量

HashMap的容量，默认是16

```java 
        /**
         * The default initial capacity - MUST be a power of two.
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
```

HashMap的加载因子，默认是0.75

### hashmap的负载因子

HashMap的加载因子，默认是0.75

```java 
        /**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
```

当HashMap中元素数超过容量加载因子时，HashMap会进行扩容。

> 所以要注意，如果要往HashMap中放1000个元素，又不想让HashMap不停的扩容，最好一开始就把容量设为2048，设为1024不行，因为元素添加到七百多的时候还是会扩容。

### hashmap的hash()算法

#### HashMap里面的hash()返回值

问题：HashMap里面的hash()返回值为什么不是`key.hashCode()`的返回值，而是`key.hashCode() ^ (key.hashCode() >>> 16)`的返回值呢？

- 源码：

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

这样做的目的是为了减少hash的冲突概率。

> hashmap再put()的时候，hash冲突是不可避免的，所以如何尽量避免hash冲突，或者在hash冲突时如何高效定位到数据的真实存储位置就是HashMap中最核心的部分。

`key.hashCode() ^ (key.hashCode() >>> 16)`的逻辑就是先获得key的hashCode的值 h，然后 h 和 h右移16位 做异或运算。`实质上就是把一个数的低16位与他的高16位做异或运算`

如果不这样的话，那么就只有hash()返回值的末x位参与到运算，这样就会造成hash冲突的概率高一些。如果先把key的hashCode()返回值的`高16位`和`低16位`进行异或运算，这样高16位也参与到hash()的运算逻辑了，这样就能减少冲突。

- 实例讲解

比如有两个key的hashCode()方法返回值分别如下

```
key1.hashCode():
1111 1111 1111 1111 0101 0101 0111 0101
key2.hashCode():
1111 1111 1110 1111 0101 0101 0111 0101
```

**如果没有`^ (h >>> 16)`，那么`15 & hash`就分别是**

key1在底层的数组索引值是：5
```java
1111 1111 1111 1111 0101 0101 0111 0101
0000 0000 0000 0000 0000 0000 0000 1111
```

key2在底层的数组索引值是：5
```java
1111 1111 1110 1111 0101 0101 0111 0101
0000 0000 0000 0000 0000 0000 0000 1111
```
这是因为key1.hashCode()和key2.hashCode()的低16位完全相同，然后`15 & hash`的时候，15的二进制`0000 0000 0000 0000 0000 0000 0000 1111`的高位几乎都是0，这就造成`15 & hash`的时候，只有`hash`的低16位起了作用，而key1.hashCode()和key2.hashCode()的低16位完全相同，所以底层索引值也就相同了，这样很容易造成hash冲突。

**但是如果有`^ (h >>> 16)`**

就比如key.hashCode的值，也就是`h变量`如下所示：
```
1111 1111 1110 1111 0101 0101 0111 0101
```
然后呢，`h ^ (h >>> 16)`就是：

```
1111 1111 1110 1111 0101 0101 0111 0101
^
0000 0000 0000 0000 1111 1111 1110 1111

```

计算结果是：这里可以看出来，最终的结果值的低16位是`hash`的高16位和低16位^运算的结果。这样做的好处就是`finalHash`的低16位具有了`hash`的低16位和高16位的都有的特征，这样就减少了hash冲突的概率

```
1111 1111 1110 1111 1010 1010 1001 1010
```

## hashmap的数组+链表/树问题

### hashmap为什么引入链表

hashmap的底层是数组，当map进行put()操作时候，会进行hash计算，判定这个对象属于数组的那个位置。当多个对象的值再同一个数组位置上面的时候，就会有hash冲突。这个时候就引入了链表

### 为什么jdk1.8会引入红黑树呢

当链表长度大于8时，遍历查找效率较慢，故引入红黑树

### hashmap为什么一开始不就使用红黑树？

这是因为红黑树相对于链表维护成本大，红黑树在插入新数据之后，可能会通过左旋、右旋、变色来保持平衡，造成维护成本过高，故链路较短时，不适合用红黑树。

### HashMap的底层数组取值的时候，为什么不用`取模`，而是&

tab[i = (n - 1) & hash]

这是因为在计算机运算的时候，使用&比`取模`的性能更快。

### 数组的长度为什么是2的次幂

总共有三个好处：

> - 为了减少hash冲突，就是为了让数据均匀分布。此时我们一般使用公式(hashCode%size），这样可以达到最大的平均分配。而(n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n
> -  &运算速度快，比%取模运算块，根据计算，Java的%、/操作比&慢10倍左右
> - 能保证 索引值 肯定在 capacity 中，不会超出数组长度

具体的想要了解看下面的知识点

hashMap的底层数据结构是数组+链表的结构，所以hashMap每次保存的数据都是分散保存在数组的各个index位置，而为了存取效率达到最高，要求hashMap每次保存的时候尽量平均分散到数组的各个位置，这样可以避免每次存取都要遍历链表造成额外的时间成本开销。

所以就通过hashMap对数组长度取余运算（hashCode%size），这样可以达到最大的平均分配；但是hashMap的作者想到了如果通过位运算来计算取余的话效率会比10进制的取余运算来的快，因为我们知道计算机的底层运算都是转化位二进制运算的；

所以为了位运算的取余效果能到10进制的效果，作者推算出了如果容量为2的N次方的话，那么hash&(length-1) == hash%length;length转为二进制位一个1+N个0，length-1转为二进制位一个0+N个1；则任意的hash值和length-1做位运算，结构都是后面N个位的的二进制，因为length-1的二进制前面都是0，位运算后都是0，相当于舍弃了高位，保留了后面的N位，后面的N位刚好在0-length之间，也就是等于hash%length取余；具体推算过程：

> 假设hash值为20，hashMap的容量为length=16

> 十进制取余算法：20%16 = 4；所以任何的hash值得取余都在0-15之间，达到了最有可能得平均分配；

> 二进制算法：20转为二进制位10100，length-1=15 = 01111；所以二进制算法为10100 & 01111 = 0100 = 4，高位和length-1的0相与后全部舍弃，直接保留了hash值最后N位，而最后N位刚好就是十进制的取余运算的结果；任何hash值都是这样；

> 再比如随便的二进制的hash值位101010101010111，假设容量length依旧位2的4（N=4）次方16，所以length-1的hash值还是0111，101010101010111和0111相与后结果为0111，十进制为7，相当于高位全部被舍弃，实际上就是保留了hash值的低N位；读者可以将101010101010111转为10进制在对16取余，验证余数是否为7；就是验证公式：hash&(length-1) == hash%length；

> 假如不是按2的幂次方，随便假设为length = 15，hash= 17，则10进制取余运算为2，二进制位运算为10001&01110 =0，不会等于10进制的的运算结果；而实际上length-1 = 14 = 01110和任何的hash相与，最后的一位的0都会被舍弃，所以任何的hash值和01110相与的结果都不会出现1101（13），1001（9）等数据，所以相当于table的数组中index =13或者9的位置永远不会保存到数据，造成空间浪费；所以就不能用位运算计算key对应的value的值，就要用10进制计算，速度就比不上二进制算法；

所以总结出：如果既要达到最可能的平均分配hashMap的value的在table的各个index，又要用二进制计算实现存取效率，就要要求hashMap的容量必须为2的幂次方；

> 所以如果不考虑性能问题，我们可以不设置数组的长度是2次幂倍数，此时也没有必要使用`h & (length-1)`，而是换成`h % length`。

### 如果指定数组的长度不为 2次幂，就破坏了数组的长度是2次幂的这个规则吗？

不会的，HashMap 的tableSizeFor方法做了处理，能保证n永远都是2次幂。

```java
/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    //cap-1后，n的二进制最右一位肯定和cap的最右一位不同，即一个为0，一个为1，例如cap=17（00010001），n=cap-1=16（00010000）
    int n = cap - 1;
    //n = (00010000 | 00001000) = 00011000
    n |= n >>> 1;
    //n = (00011000 | 00000110) = 00011110
    n |= n >>> 2;
    //n = (00011110 | 00000001) = 00011111
    n |= n >>> 4;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 8;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 16;
    //n = 00011111 = 31
    //n = 31 + 1 = 32, 即最终的cap = 32 = 2 的 (n=5)次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
```

## hashmap里面的源码

### HashMap的put()

- 1.8的put()方法

> 1. 如果key对应的索引位置是null，那么直接插入
> 2. 数组里面key对应的索引值位置的值不为null，判断这个老值的key是否和新put的key是否相同，如果相同，就把老的值返回，并且记录这个位置
> 3. 数组里面key对应的索引值位置的值不为null，判断这个索引位置的值是不是树结构，如果是树结构，调用树结构putTreeVal方法添加数据
> 4. 数组里面key对应的索引值位置的值不为null，然后这个索引位置的值就是一个链表结构，然后遍历所有的链表(`当遍历的长度大于8的时候，就会转成树结构`)，如果链表结构里面有key值和新key值相同，就把老的值给返回，并且记录这个位置，如果遍历到尾部还不相同，那么就使用`尾插入`把数据给添加进去。
> 5. 对2步骤和4步骤记录的位置进行处理，一是把标记的位置的老值给返回，二是把新插入的值放到标记的位置上面。

底层源码：

```java
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果table为空，或者还没有元素时，则扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果首结点值为空，则创建一个新的首结点。
    // 注意：(n - 1) & hash才是真正的hash值，也就是存储在table位置的index。在1.6中是封装成indexFor函数。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {    // 到这儿了，就说明碰撞了，那么就要开始处理碰撞。
            Node<K,V> e; K k;
            // 如果在首结点与我们待插入的元素有相同的hash和key值，则先记录。
            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;
                        }
                        // 如果找到与我们待插入的元素具有相同的hash和key值的结点，则停止遍历。此时e已经记录了该结点
                        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;
                // onlyIfAbsent表示如果当前位置已存在一个值，是否替换，false是替换，true是不替换
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);  // 这个是空函数，可以由用户根据需要覆盖
                return oldValue;
            }
        }
    ++modCount;
    // 当结点数+1大于threshold时，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // 这个是空函数，可以由用户根据需要覆盖
    return null;
}
```

HashMap在put()的时候，如果put一个已经存在的key，那么会把老的key对应的value值返回

```java
public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(1,5);
        Integer put = map.put(1, 8);
        System.out.println(put);
    }
````
结果如下：
```java
5
```

### HashMap的get()

- 1.8的get()方法

> 1. 首先获取当前key对应的数组索引位置，然后判断该位置的首节点是否是自己想要的值`根据key和key.hashCode()来判断`
> 2. 首节点如果不是的话，判断节点是否是树节点，如果是的话，通过调用`getTreeNode()`来实现`get()`方法，如果不是树节点，那么就是链表，然后死循环遍历链表，查询是否有自己想要的值
> 3. 如果上面的步骤都没有查询到数据，直接返回null.

底层源码：

```java

public V get(Object key) {
        //定义一个Node对象来接收
        Node<K,V> e;
        //调用getNode()方法，返回值赋值给e，如果取得的值为null，就返回null，否则就返回Node对象e的value值
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

//取hash值方法，HashMap的put方法的也是调用了这个方法，get方法也调用这个方法，保证存取时key值对应的hash值是一致的，这样才能正确对应 
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
     
final Node<K,V> getNode(int hash, Object key) {
        //定义几个变量 
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //首先是判断数组table不能为空且长度要大于0，同时把数组长度tab.length赋值给n
        if ((tab = table) != null && (n = tab.length) > 0 &&
             //其次是通过[(n - 1) & hash]获取key对应的索引，同时数组中的这个索引要有值，然后赋值给first变量
            (first = tab[(n - 1) & hash]) != null) {
            //这个first其实就是链表头的节点了，接下来判断first的hash值是否等于传进来key的hash值
            if (first.hash == hash && 
                //再判断first的key值赋值给k变量，然后判断其是否等于key值，或者判断key不为null时，key和k变量的equals比较结果是否相等
                ((k = first.key) == key || (key != null && key.equals(k))))
                //如果满足上述条件的话，说明要找的就是first节点，直接返回
                return first;
            //走到这步，就说明要找的节点不是首节点，那就用first.next找它的后继节点 ，并赋值给e变量，在这个变量不为空时   
            if ((e = first.next) != null) {
                //如果首节点是树类型的，那么直接调用getTreeNode()方法去树里找
                if (first instanceof TreeNode)
                     //这里就不跟进去了，获取树中对应key的节点后直接返回
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //走到这步说明结构还是链表    
                do {
                    //这一步其实就是在链表中遍历节点，找到和传进来key相符合的节点，然后返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                  //获取e节点的后继节点，然后赋值给e，不为空则进入循环体  
                } while ((e = e.next) != null);
            }
        }
        //以上条件都不满足，说明没有该key对应的数据节点，返回null
        return null;
    }

```

### HashMap的扩容原理

#### 1.7的扩容原理

**什么时候扩容和扩容多少**

1.7的扩容从put()方法作为入口讲解：

`put(K, V)`操作

```java 
    public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);//计算键的hash值
            int i = indexFor(hash, table.length);//通过hash值对应到桶位置
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
      
        //顺序遍历桶外挂的单链表
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      
        //注意这里的键的比较方式== 或者 equals()
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);//遍历单链表完毕，没有找到与键相对的Entry，需要新建一个Entry换句话说就是桶i是一个空桶；
            return null;
        }
```

既然找到一个空桶，那么新建的`Entry`必然会是这个桶外挂单链表的第一个结点。通过`addEntry`，找到了扩容的时机。

```java 
    
        /**
         * Adds a new entry with the specified key, value and hash code to
         * the specified bucket.  It is the responsibility of this
         * method to resize the table if appropriate.
         *
         * Subclass overrides this to alter the behavior of put method.
         */
        void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
      
              // 当size大于等于某一个阈值thresholdde时候且该桶并不是一个空桶；
                resize(2 * table.length);//将容量扩容为原来的2倍
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);//扩容后的，该hash值对应的新的桶位置
            }
    
            createEntry(hash, key, value, bucketIndex);//在指定的桶位置上，创建一个新的Entry
        }
    
        /**
         * Like addEntry except that this version is used when creating entries
         * as part of Map construction or "pseudo-construction" (cloning,
         * deserialization).  This version needn't worry about resizing the table.
         *
         * Subclass overrides this to alter the behavior of HashMap(Map),
         * clone, and readObject.
         */
        void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<>(hash, key, value, e);//链表的头插法插入新建的Entry
            size++;//更新size
        }
    
```

上面有几个重要成员变量：

*  size
 *  threshold

```java 
       /**
         * The number of key-value mappings contained in this map.
         */    
       transient int size;
    
        /**
         * The next size value at which to resize (capacity * load factor).
         * @serial
         */
        int threshold;
    
        /**
         * The load factor for the hash table.
         *
         * @serial
         */
        final float loadFactor;
```

由注释可以知道：

*  size记录的是map中包含的Entry的数量
 *  而threshold记录的是需要resize的阈值 且 `threshold = loadFactor * capacity`
 *  capacity 其实就是桶的长度

```java 
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    ```

因此现在总结出扩容的时机：

**当`map`中包含的`Entry`的数量大于等于`threshold = loadFactor * capacity`的时候，且新建的`Entry`刚好落在一个非空的桶上，此刻触发扩容机制，将其容量扩大为`2倍`。**

> 这个这样说明比较好理解：因为size 已经大于等于阈值了，说明Entry数量较多，哈希冲突严重，那么若该Entry对应的桶不是一个空桶，这个Entry的加入必然会把原来的链表拉得更长，因此需要扩容；若对应的桶是一个空桶，那么此时没有必要扩容。

当`size`大于等于`threshold`的时候，并不一定会触发扩容机制，但是会很可能就触发扩容机制，只要有一个新建的`Entry`出现哈希冲突，则立刻`resize`。

直到这里我们回答了什么时候扩容和扩容多少的问题，那么下面回答如何扩容的问题。

**HashMap的扩容过程**

上面有一个很重要的方法，包含了几乎属于的扩容过程，这就是`resize()`

```java 
    /**
         * Rehashes the contents of this map into a new array with a
         * larger capacity.  This method is called automatically when the
         * number of keys in this map reaches its threshold.
         *
         * If current capacity is MAXIMUM_CAPACITY, this method does not
         * resize the map, but sets threshold to Integer.MAX_VALUE.
         * This has the effect of preventing future calls.
         *
         * @param newCapacity the new capacity, MUST be a power of two;
         *        must be greater than current capacity unless current
         *        capacity is MAXIMUM_CAPACITY (in which case value
         *        is irrelevant).
         */
        void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
      
        //最大容量为 1 << 30
                threshold = Integer.MAX_VALUE;
                return;
            }
    
            Entry[] newTable = new Entry[newCapacity];//新建一个新表
            boolean oldAltHashing = useAltHashing;
            useAltHashing |= sun.misc.VM.isBooted() &&
                    (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
            boolean rehash = oldAltHashing ^ useAltHashing;//是否再hash
            transfer(newTable, rehash);//完成旧表到新表的转移
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }
    
        /**
         * Transfers all entries from current table to newTable.
         */
        void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
      
        //遍历同桶数组中的每一个桶
                while(null != e) {
      
        //顺序遍历某个桶的外挂链表
                    Entry<K,V> next = e.next;//引用next
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);//找到新表的桶位置;原桶数组中的某个桶上的同一链表中的Entry此刻可能被分散到不同的桶中去了，有效的缓解了哈希冲突。
                    e.next = newTable[i];//头插法插入新表中
                    newTable[i] = e;
                    e = next;
                }
            }
        }
```

对于`resize`的过程，相对来讲是比较简单清晰易于理解的。**旧桶数组中的某个桶的外挂单链表是通过头插法插入新桶数组中的，并且原链表中的Entry结点并不一定仍然在新桶数组的同一链表**。

这里很容易就想到多线程情况下，这个`transfer`方法在多线程环境下会乱套。事实上也是这样的，由于**缺乏同步机制**，当多个线程同时`resize`的时候，某个线程`t`所持有的引用`next`（参考上面代码`next`指向原桶数组中某个桶外挂单链表的下一个需要转移的`Entry`），可能已经被转移到了新桶数组中，那么最后该线程`t`实际上在对新的桶数组进行`transfer`操作。

如果有更多的线程出现这种情况，那很可能出现大量线程都在对**新桶数组**进行`transfer`，这样极易造成死循环，数据丢失等等，因此`HashMap`不是线程安全的，所以考虑在多线程环境下使用并发工具包下的`ConcurrentHashMap`。

#### 1.8的扩容原理

JDK1.8对resize()方法进行很大的调整，JDK1.8的resize()方法如下：

```java 
        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)                      //注释1
                    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) {                                 //注释2
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        if (e.next == null)                                        //注释3
                            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) {                      //注释4
                                    if (loTail == null)                            //注释5
                                        loHead = e;
                                    else
                                        loTail.next = e;                           //注释6
                                    loTail = e;                                    //注释7
                                }
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            if (loTail != null) {                                  /注释8
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }
```

代码解析：

1，在resize()方法中，定义了oldCap参数，记录了原table的长度，定义了newCap参数，记录新table长度，newCap是oldCap长度的2倍（注释1），同时扩展点也乘2。

2，注释2是循环原table，把原table中的每个链表中的每个元素放入新table。

3，注释3，e.next==null，指的是链表中只有一个元素，所以直接把e放入新table，其中的e.hash & (newCap - 1)就是计算e在新table中的位置，和JDK1.7中的indexFor()方法是一回事。

4，注释// preserve order，这个注释是源码自带的，这里定义了4个变量：loHead，loTail，hiHead，hiTail，看起来可能有点眼晕，其实这里体现了JDK1.8对于计算节点在table中下标的新思路：

> 正常情况下，计算节点在table中的下标的方法是：hash&(oldTable.length-1)，扩容之后，table长度翻倍，计算table下标的方法是hash & (newTable.length-1)，也就是hash & (oldTable.length*2-1)，于是我们有了这样的结论：**这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度**。

举个例子，假设table原长度是16，扩容后长度32，那么一个hash值在扩容前后的table下标是这么计算的：

hash值的每个二进制位用abcdef来表示，那么，hash和新旧table按位与的结果，最后4位显然是相同的，唯一可能出现的区别就在第5位，也就是hash值的b所在的那一位，如果b所在的那一位是0，那么新table按位与的结果和旧table的结果就相同，反之如果b所在的那一位是1，则新table按位与的结果就比旧table的结果多了10000（二进制），而这个二进制10000就是旧table的长度16。

换言之，hash值的新散列下标是不是需要加上旧table长度，<span style='color: red'>只需要看看hash值第5位是不是1就行了，位运算的方法就是hash值和10000（也就是旧table长度）来按位与</span>，其结果只可能是10000或者00000。

所以，注释4处的`e.hash & oldCap`，就是用于计算位置b到底是0还是1用的，只要其结果是0，则新散列下标就等于原散列下标，否则新散列坐标要在原散列坐标的基础上加上原table长度。

理解了上面的原理，这里的代码就好理解了，代码中定义的四个变量：

> loHead，下标不变情况下的链表头
>
> loTail，下标不变情况下的链表尾
>
> hiHead，下标改变情况下的链表头
>
> hiTail，下标改变情况下的链表尾

而注释4处的`(e.hash & oldCap) == 0`，就是代表散列下标不变的情况，这种情况下代码只使用了loHead和loTail两个参数，由他们组成了一个链表，否则将使用hiHead和hiTail参数。

其实e.hash & oldCap等于0和不等于0后的逻辑完全相同，只是用的变量不一样。

以等于0的情况为例，处理一个3-->5-->7的链表，过程如下：

> 首先处理节点3，e==3，e.next==5
>
> 注释5，一开始loTail是null，所以把3赋值给loHead。
>
> 注释7，把3赋值给loTail。
>
> 然后处理节点5，e==5，e.next==7
>
> 注释6，loTail有值，把e赋值给loTail.next，也就是3.next==5。
>
> 注释7，把5赋值给loTail。

现在新链表是3-->5，然后处理节点7，处理完之后，链表的顺序是3-->5-->7，loHead是3，loTail是7。可以看到，链表中节点顺序和原链表相同，不再是JDK1.7的倒序了。

代码到注释8这里就好理解了，

只要loTail不是null，说明链表中的元素在新table中的下标没变，所以新table的对应下标中放的是loHead，另外把loTail的next设为null

反之，hiTail不是null，说明链表中的元素在新table中的下标，应该是原下标加原table长度，新table对应下标处放的是hiHead，另外把hiTail的next设为null。

[itqiankun.com.68449037962256056401.png 1]: https://itqiankun.oss-cn-beijing.aliyuncs.com/new_picture/myblog/2021/07/05/itqiankun.com.68449037962256056401.png
[itqiankun.com.68449037962256056402.png]: https://itqiankun.oss-cn-beijing.aliyuncs.com/new_picture/myblog/2021/07/05/itqiankun.com.68449037962256056402.png
[itqiankun.com.68449037962256056403.png]: https://itqiankun.oss-cn-beijing.aliyuncs.com/new_picture/myblog/2021/07/05/itqiankun.com.68449037962256056403.png
[itqiankun.com.68449037962256056404.png]: https://itqiankun.oss-cn-beijing.aliyuncs.com/new_picture/myblog/2021/07/05/itqiankun.com.68449037962256056404.png
[itqiankun.com.68449037962256056405.png]: https://itqiankun.oss-cn-beijing.aliyuncs.com/new_picture/myblog/2021/07/05/itqiankun.com.68449037962256056405.png
[itqiankun.com.68449037962256056406.png]: https://itqiankun.oss-cn-beijing.aliyuncs.com/new_picture/myblog/2021/07/05/itqiankun.com.68449037962256056406.png

(大厂进阶)全网HashMap最全面试题(附答案)

全部教程