一文搞懂 HashMap 常见面试题

待我称王封你为后i 2023-10-01 12:24 3阅读 0赞

#### 文章目录 ####

*   *  1. Hash
     *  2. Hash Table
     *  3. Hash Code
     *  4. Hash 函数
     *   *  4.1 hash(key)
     *  5. HashMap 的 put() 方法
     *   *  5.1 tableSizeFor
         *  5.2 Hash 冲突
         *   *  5.2.1 开放寻址
             *  5.2.2 链路地址
         *  5.3 put 流程图
     *  6. HashMap 的 resize() 扩容机制
     *   *  6.1 什么是无效扩容
         *  6.2 加载因子为什么是 0.75
     *  7. HashMap 链表会形成死循环？
     *  8. 什么时候用到红黑树
     *  9. HashMap 链表大于 8 一定会转为红黑树吗
     *  10. HashMap 相关面试题

### 1. Hash ###

Hash，一般翻译做散列，或音译为哈希，是把任意长度的[输入][Link 1]（又叫做预映射pre-image）通过散列算法变换成固定长度的[输出][Link 2]，该输出就是散列值。这种转换是一种[压缩映射][Link 3]，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的[消息摘要][Link 4]的函数。[–百度百科][Link 5]

实际上我们可以把它理解为一个算法，即 Hash 算法，最简单的算法就是加减乘除，而 Hash 算法就是相对比较复杂的一个运算，它的输入可以是字符串，可以是数据，可以是任何文件，经过哈希运算后，变成一个固定长度的输出，该输出就是哈希值。但是哈希算法有一个很大的特点，就是你不能从结果推算出输入。如下：

![image-20211231163103280][]

常见的基于 Hash 算法的加密算法，如 MD5，SHA 等等。

### 2. Hash Table ###

Hash Table，哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即 key，即可查找到其对应的值。

如 Java 中的 HashMap 就是基于哈希表的。

### 3. Hash Code ###

hashcode就是通过hash函数得来的，通俗的说，就是通过某一种算法得到的，hashcode 就是在 hash 表中有对应的位置。

每个对象都有 hashcode，对象的 hashcode 怎么得来的呢？

在 `Object`类中，存在以下一个方法：

public native int hashCode();

可以看到，它的返回值为 int 类型，那么它是如何计算的呢？我们知道`Object`是所有类的超类，那么必然JDK中一些类会对其进行实现，如 `String` 类，其实现如下：

// jdk8
    public int hashCode() {
        
        int h = hash;
        if (h == 0 && value.length > 0) {
        
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
        
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

### 4. Hash 函数 ###

实际上，我们了解 Hash 可以从 HashMap 入手，在 JDK1.7 之前，HashMap 是基于数组加链表的方式，如下：

![image-20220104173345810][]

对应在源码中通过 Entry 来存储数据，在 jdk7 叫 Entry，jdk8 中叫Node。

**jdk1.7**

static class Entry<K,V> implements Map.Entry<K,V> {
        
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
        
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        //...
    }

**jdk1.8**

static class Node<K,V> implements Map.Entry<K,V> {
        
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
        
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        //...
    }

#### 4.1 hash(key) ####

既然涉及到 Hash，必然就涉及到 Hash 值的计算，Hash 值的计算在put，get等方法中都有涉及，在 JDK1.7 和 1.8 稍有不同，如下：

**jdk1.7**

final int hash(Object k) {
        
        int h = 0;
        if (useAltHashing) {
        
            if (k instanceof String) {
        
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
        h ^= k.hashCode();
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

**jdk1.8**

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

可以看到都是通过位运算来计算 Hash 值，关于位运算可以看这篇文章（[Java中的位运算][Java]）。

### 5. HashMap 的 put() 方法 ###

当我们`new HashMap()`在未指定大小的时候，其默认为 16，如下：

/**
     * The default initial capacity - MUST be a power of two.
     *
     * 默认数组的初始容量，且必须为2的次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    // 存放所有Node节点的数组
    transient Node<K,V>[] table;

**那么为什么说 table 数组的长度必须是 2 的次幂呢？**

`put()`方法源码如下：

public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }

可以看到在存入数据时会先计算 key 的 hash 值，即`hash(key)`：

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

然后通过`(n-1) & hash` 的取值来判断将该数据放入 table 的哪个**下标**，如下：

![image-20220104145843344][]

注：n 为 table 数组的长度。

其中 `&` 为二进制中的`位与`运算，两个位都为 1 时，结果才为 1 `(1&1=1，0&0=0，1&0=0)`，如下：

4 & 6 = 4

首先把两个十进制的数转换成二进制

4  0 1 0 0
    6  0 1 1 0
    ----------
    4  0 1 0 0

因为HashMap 的 table 数组的长度是 2 的次幂 ，那么对于这个数再减去 1（即 n-1），转换成二进制的话，就肯定是最高位为 0，其他位全是1 的数。为什么？

因为一个数（大于0）为 2 的次幂，那么根据奇偶判断这个数必定为偶数，那么减 1 之后就为奇数，那么一个数转为二进制数的末位就为 1。

以 HashMap 默认初始数组长度 16 为例，`16-1`的二进制为`1111`，然后随意指定几个 hash 值与其计算，并与其进行位与运算：

十进制
    hash1	1 0 1 1 0 1 1 1
    15      0 0 0 0 1 1 1 1
    -----------------------
    7       0 0 0 0 0 1 1 1
    
    hash2	1 0 1 1 0 1 0 1
    15      0 0 0 0 1 1 1 1
    -----------------------
    5       0 0 0 0 0 1 0 1
    
    hash3	1 0 1 1 0 1 0 0
    15      0 0 0 0 1 1 1 1
    -----------------------
    4       0 0 0 0 0 1 0 0

若不为 2 次幂，假如为 15，则减 1 后 14 的二进制为 `1110`，再次进行运算：

十进制
    hash1	1 0 1 1 0 1 1 1
    14      0 0 0 0 1 1 1 0
    -----------------------
    6       0 0 0 0 0 1 1 0
    
    hash2	1 0 1 1 0 1 0 1
    14      0 0 0 0 1 1 1 0
    -----------------------
    4       0 0 0 0 0 1 0 0
    
    hash3	1 0 1 1 0 1 0 0
    14      0 0 0 0 1 1 1 0
    -----------------------
    4       0 0 0 0 0 1 0 0

很明显，在不为 2 次幂的时候，最后两个通过位运算，求出的值都为 4，也就是说数据都分布在 table 数组下标为 4 的节点上（数据桶），带来的问题就是由于出现 Hash 碰撞导致 HashMap 上的数组元素分布不均匀，而数组上的某些位置，永远也用不到，进而影响其性能。

此时，就有人说了，我不是可以指定 HashMap 的大小吗？我就不给他 2 次幂的数，会怎样呢？比如`new HashMap(7)`。假设你传一个 7 进去，实际上最终 HashMap 的大小是 8，其具体的实现其构造器的 `tableSizeFor()`。

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

#### 5.1 tableSizeFor ####

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

**其中还是通过位运算去解析的，即如果你传一个 7 进去，实际上最终 HashMap 的大小是 8，传一个 10，那么 HashMap 的大小是 16，传 20，HashMap 的大小是 32。**

对于`(n-1) & hash`，还存在另外一种说法，**(n - 1) & hash等于 hash % n**，举个例子：

当 n = 16 时，二进制形式为 00010000，（n-1）的二进制形式为 00001111 ，假设 hash = 33，其二进制形式为 00100001，则：

0 0 0 0 1 1 1 1
    0 0 1 0 0 0 0 1
    ---------------
    0 0 0 0 0 0 0 1

其结果为 1，即`(16-1) & 33 = 1`，而 `33 % 16 = 1`，两者相等，但前提是**当 n 为 2 的任意次幂时，（n-1）& hash 等价于 hash % n**。从而也保证了当添加一个数时的下标 index 在数组范围内。

**put 方法详细说明**

//jdk1.8
    //put方法，会先调用一个hash()方法，得到当前key的一个hash值，
    //用于确定当前key应该存放在数组的哪个下标位置
    //这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲
    public V put(K key, V value) {
        
    	return putVal(hash(key), key, value, false, true);
    }
    
    //把hash值和当前的key，value传入进来
    //这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
    //evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一个空实现，因此不用关注这个参数
    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是否为空，如果空的话，会先调用resize扩容
    	if ((tab = table) == null || (n = tab.length) == 0)
    		n = (tab = resize()).length;
    	//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，
    	//若没有，则把key、value包装成Node节点，直接添加到此位置。
    	// i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲
    	if ((p = tab[i = (n - 1) & hash]) == null)
    		tab[i] = newNode(hash, key, value, null);
    	else {
         
    		//如果当前位置已经有元素了，分为三种情况。
    		Node<K,V> e; K k;
    		//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
    		//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
    		if (p.hash == hash &&
    			((k = p.key) == key || (key != null && key.equals(k))))
    			e = p;
    		//2.如果当前是红黑树结构，则把它加入到红黑树 
    		else if (p instanceof TreeNode)
    			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    		else {
        
    		//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
    			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的话，直接退出循环，跳转到①处
    				if (e.hash == hash &&
    					((k = e.key) == key || (key != null && key.equals(k))))
    					break;
    				p = e;
    			}
    		}
    		//①
    		//说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值
    		if (e != null) {
         // existing mapping for key
    			V oldValue = e.value;
    			//用新值替换旧值，并返回旧值。
    			if (!onlyIfAbsent || oldValue == null)
    				e.value = value;
    			//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，
    			//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能
    			// Callbacks to allow LinkedHashMap post-actions
    			//void afterNodeAccess(Node<K,V> p) { }
    			afterNodeAccess(e);
    			return oldValue;
    		}
    	}
    	//fail-fast机制
    	++modCount;
    	//如果当前数组中的元素个数超过阈值，则扩容
    	if (++size > threshold)
    		resize();
    	//同样的空实现
    	afterNodeInsertion(evict);
    	return null;
    }

#### 5.2 Hash 冲突 ####

上面讲到了通过 hash 位运算有效的解决了数据分布不均匀的情况，但是在高并发或者大数据场景中，如果使用 HashMap，那么由于数组是有长度限制的，所以当 `put` 元素时，通过`hash(key)`计算 hash 值来确定元素存放的下标可能会出现相同的值，也就是所谓的 Hash 碰撞（Hash 碰撞）。

举个简单的例子：

11,52,62,63,4,5;

对上面的进行取余计算：

11 % 10 = 1
    52 % 10 = 2
    62 % 10 = 2   --->此时就称之为Hash冲突

其实这是一个无法避免的问题，比如 MD5 这些加密的 Hash 算法等等在某些情况下都会出现冲突，我们几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，所以针对散列冲突问题，我们需要通过其他途径来解决。

##### 5.2.1 开放寻址 #####

开放寻址法的核心思想是，如果出现了哈希冲突，我们就重新探测一个空闲位置，将其插入。

当我们往哈希表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

看看别人的解释：

简单地讲，也就是说，一间厕所，来了一个顾客就蹲其对应的位置，如果又来一个顾客，把厕所单间门拉开，一看里面有位童鞋正在用劲，那么怎么办？很自然的，拉另一个单间的门，看看有人不，有的话就继续找坑。当然了，一般来说，这个顾客不会按顺序一个一个地拉厕所门，而是会去拉他认为有可能没有被占用的单间的门，这可以通过闻味道，听声音来辨别，这就是寻址查找算法。如果找遍了所有厕所单间，看尽了所有人的光屁股，还是找不到坑，那么这座厕所就该扩容了。当然了，厕所扩容不会就只单单增加一个坑位，而是综合考虑成本和保证不让太多顾客拉到裤子里，会多增加几个坑位，比如增加现有坑位的 0.72 倍。为什么是 0.72 呢，这是所长多年经营所得到的经验值，为了让自己的经验发扬光大，需要出去演讲，又不能太俗，总不能说“厕所坑位因子”吧，那就把把 0.72 叫做“装填因子”或者“扩容因子”吧。

##### 5.2.2 链路地址 #####

链表法其实就是使用链表，链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。

也就是为什么 HashMap 中需要链表，也就是上面的 Node 节点，每一个节点都会保存自身的 hash、key、value、以及下个节点，如下：

如当出现哈希冲突定位到同一个 index 下，则通过链表的方式往后追加，如下：

![image-20220104202142219][]

#### 5.3 put 流程图 ####

![image-20220105115942079][]

### 6. HashMap 的 resize() 扩容机制 ###

前面讲过，HashMap 的默认数组容量大小为 16，也就是说它是有限的，那么随着数据的增加，达到一定量之后就会自动扩容，即`resize()`。

那么触发`resize()`的具体条件是什么呢？主要包括两个方面：

1.  **capacity**：HashMap 当前长度，默认为 16。
2.  **load factor**：加载因子，默认值 0.75f。

其中负载因子的大小决定着哈希表的扩容和哈希冲突，一旦达到阈值就会扩容，阈值在HashMap中定义如下：

/**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

那么什么时候扩容呢？就是`capacity*load factor`，即`16*0.75=12`，也就是说数组最多只能放 12 个元素，一旦超过 12 个，哈希表就需要扩容。

而在扩容的过程中包含了 2 步：

1.  **扩容**，创建一个新的 Entry 空数组，长度是原数组的 2 倍（2次幂），即 16 扩容后为 32；
2.  **Rehash**，遍历原 Node 数组，从新计算索引的值并添加到新数组。

那么为什么需要**Rehash**呢？

前面说道 hash 值是通过 `(n-1)&hash`来计算的，其中 n 为数组的长度，数组长度发生变化，如果不重新计算，很可能后续添加元素的时候会生冲突。

#### 6.1 什么是无效扩容 ####

在扩容的过程中 jdk7 和 jdk8 是不同的，即**jdk7 先扩容再put 而jdk8 先put再扩容**，为什么？

jdk7 put 主要源码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
        
        if ((size >= threshold) && (null != table[bucketIndex])) {
        
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

可以看到是先判断`size >= threshold`并且当前数组索引的桶不为空就扩容，也就是说如果当存在重复的 key 时候直接替换即可，而不需要扩容，而`jdk7`却是直接扩容，也就是所谓的**无效扩容**。

而 jdk8 中则不然，它是先 put 元素然后在进行判断，如下：

if (++size > threshold)
        resize();

#### 6.2 加载因子为什么是 0.75 ####

此时，产生了另外一种想法，扩容需要遍历原数组并需要重新计算 Hash，对于容量来说，可能不好控制，那如果把**加载因子**调大是不是就可以减少扩容次数呢？

**1、加载因子是1.0**

比如设置为 1，那么就是等元素到 16 之后才扩容。

![image-20220105195041298][]

一开始数据保存在数组中，当发生 Hash 碰撞后，就在这个数据节点上，生出一个链表，当链表长度达到一定长度的时候，就会把链表转化为红黑树。

**当加载因子是1.0的时候，也就意味着，只有当数组的8个值（这个图表示了8个）全部填充了才会发生扩容。这就带来了很大的问题，因为 Hash 冲突时避免不了的。当负载因子是 1.0 的时候，意味着会出现大量的Hash的冲突，底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。**

**2、加载因子是0.5**

加载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，**Hash冲突也会减少**，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是触发扩容，会浪费一定的内存空间，这时空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。

总结起来就是：

1.  加载因子调高了，意味着 Hash 碰撞概率增加，查找速度变慢；
2.  加载因子调低了，Hash 碰撞概率降低，查找速度变高，但空间利用率降低。

而为什么是 0.75？在源码中也有体现，如下：

![image-20220105202014726][]

其大致意思就是说负载因子是 0.75 的时候，权衡之后空间利用率相对较高，并且降低了Hash碰撞的概率。

### 7. HashMap 链表会形成死循环？ ###

这个问题实际上是针对 jdk7 的，因为 jdk7 的链表是头插法，在并发情况下可能会造成死循环，而 jdk8 采用的是尾插法，不会产生死循环。

那么什么是头插法和尾插法呢？可以看看下面这张图：

![image-20220106152324204][]

在 jdk7的 put 方法中，主要流程如下：

put()  --> addEntry()  --> resize() -->  transfer()

主要问题就出现在`transfer()`，也就是扩容过程中出现了问题，该方法的作用是**将原来的所有数据全部重新插入（rehash）到新的数组中**，如下：

void transfer(Entry[] newTable, boolean rehash) {
        
        // 获取新table的长度
        int newCapacity = newTable.length;
        // 遍历老table中的元素
        for (Entry<K,V> e : table) {
        
            // 遍历每一个链表的元素
            while(null != e) {
        
                // 获取当前元素的 next
                Entry<K,V> next = e.next; 
                // 判断是否需要重新hash
                if (rehash) {
        
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 获取元素对应的新table位置
                int i = indexFor(e.hash, newCapacity);
                // 进行转移，头插法
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

实际上，非并发情况下是不会出现死循环的，这里演示在并发的情况下。

假设 HashMap 初始容量为 4，则 `4*0.75=3`，若在之前已经插入了 3 个元素 A，B，C（为了方便直接用以表示节点的key-value），并且它们都 hash 到一个位置上，则形成如下的链表结构：

![image-20220107161745890][]

此时插入第 4 个元素时，HashMap 需要扩容（为原来的 2 倍），若此时有**两个线程同时**插入，则两个线程都会建立新的数组，如下：

![image-20220107163640649][]

当线程 1 执行到`transfer()`中的`Entry<K,V> next = e.next` ，且 CPU 时间片刚好到了，那么此时对于线程 1 来说：

e = A;
    e.next = B;

然后线程 2 开始正常执行，在 rehash 之后，A、B、C 又在同一位置，则按照头插法的方式循环完成之后的结构如下所示：

![image-20220107175932194][]

在执行完上面的步骤之后，此时线程 2 的 CPU 时间片到了，又轮到线程 1，对于线程 1 来说`e = A;`  
`e.next = B`，那么此时的引用关系因为：

![image-20220107180130441][]

而我们知道在 JVM 中我们的对象都存在于堆中，因为对于线程 1 来说，`e = A;e.next = B`即`A.next =B`，而对于线程 2 来说则是`B.next=A`，所以此时 2 个数组对于 A、B、C 的引用关系如下：

![image-20220108131439917][]

可以看到 A，B之间相互引用，若此时存在另外的线程来调用 `get()` 方法，如下：

final Entry<K,V> getEntry(Object key) {
        
        //如果hashmap的大小为0返回null    
        if (size == 0) {
        
            return null;
        }
        // 判断key如果为null则返回0,否则将key进行hash    
        int hash = (key == null) ? 0 : hash(key);
        //indexFor方法通过hash值和table的长度获取对应的下标    
        // 遍历该下标下的(如果有)链表    
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        
            Object k;
            //判断当前entry的key的hash如果和和参入的key相同返回当前entry节点        
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) 
                return e;
        }
        return null;
    }

可以看到在 for 循环查找元素时，只要 `e.next != null`，则会一直循环查找，所以在并发的情况，发生扩容时，可能会产生循环链表，在执行 get 的时候，会触发死循环。

那么问题来了，既然有死循环产生的可能为**什么还要使用头插法**呢？

这可能得问实现者了，有种说法，我觉得挺有道理：**缓存的时间局部性原**则，最近访问过的数据下次大概率会再次访问，把刚访问过的元素放在链表最前面可以直接被查询到，减少查找次数。

这实际上并不能算是一个问题，因为 HashMap 本就不是线程安全的，所以你如果用它来处理并发，本就是不符合逻辑的，所以在并发情况下可以使用线程安全的如 ConcurrentHashMap。

### 8. 什么时候用到红黑树 ###

红黑树是一棵二叉查找树，其具备以下性质：

1.  节点是红色或黑色（非黑即红）
2.  根节点是黑色
3.  所有的null节点称为叶子节点，且都是黑色
4.  所有红色节点的子节点都是黑色（即没有连续的红色节点）
5.  任意一个节点到其叶子节点的所有路劲都包含相同数目的黑色节点

![image-20220108133603691][]

如果想了解更多关于红黑树的可以参看我的这篇文章：[图解红黑树][Link 6]

而在 HashMap 中运用红黑树的主要目的是为了查询效率，我们知道，在 jdk7 是通过链表来解决了 Hash 冲突，但是如果某一条链表上存在很多数据，当我们需要查找的时候，则需要一直遍历，知道找到对应的值，时间复杂度为O(n)。而 jdk8 就引入了红黑树，红黑树是一棵二叉查找树，其查询是插入时间复杂度为 O(logn)，效率高于链表。

那么就有人说了，既然有红黑树，为什么还需要链表？

因为红黑树的查询很快，但是增加删除操作却比较复杂，需要进行相应的**左旋、右旋**操作，相比链表是比较耗时的，所以在 jdk8 中也不是一上来就使用红黑树，遵循以下规则：

1.  数组容量大小大于 64 且链表大小大于 8，链表转为红黑树；
2.  当红黑树的大小小于 6，红黑树退化为链表。

### 9. HashMap 链表大于 8 一定会转为红黑树吗 ###

不是的，数组容量大小大于 64 **且**链表大小大于 8，链表才会转为红黑树。

如果说仅仅是链表长度大于 8，而数组容量小于 64，此时还是会扩容但不会转为红黑树。

因为此时数组容量较小，应该尽量避开使用红黑树，因为红黑树需要进行**左旋，右旋，变色**操作来保持平衡，所以当数组长度小于 64，使用数组加链表比使用红黑树查询速度要更快、效率要更高。

注：对于红黑树的大小小于 6，红黑树退化为链表，实际上只有 resize 的时候才会进行转换，同样也不是到 8 的时候就变成红黑树。

**为什么是链表长度大于 8 的时候转为红黑树？能不能是其他数值？**

通常情况下，**链表长度很难达到 8**，在源码中有这样一段注释：

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution 
    with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although 
    with a large variance because of resizing granularity. Ignoring variance, the expected 
    occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). 
    The first values are:
          0:    0.60653066
          1:    0.30326533
          2:    0.07581633
          3:    0.01263606
          4:    0.00157952
          5:    0.00015795
          6:    0.00001316
          7:    0.00000094
          8:    0.00000006
          more: less than 1 in ten million

在理想情况且在随机哈希码下，哈希表中节点的频率遵循[泊松分布][Link 7]，而根据统计，忽略方差，列表长度为 K 的期望出现的次数是以上的结果，可以看到其实在为 8 的时候概率就已经很小了，可以看到**当长度为 8 的时候，概率仅为 0.00000006**。这是一个小于千万分之一的概率，一般来说我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换，因此再往后调整并没有很大意义。

如果真的碰撞发生了8次，那么这个时候说明由于元素本身和 hash 函数的原因，此时的链表性能已经已经很差了，操作的 hash 碰撞的可能性非常大了，后序可能还会继续发生 hash 碰撞，因此特殊情况下链表长度为 8，哈希表容量又很大，造成链表性能很差的时候，只能采用红黑树提高性能，这是一种应对策略。

**为什么链表的长度为 8 是变成红黑树？为什么红黑树大小为 6 时又变成链表？**

首先我们先了解一下什么是平均查询长度，ASL(Average Search Length)。

另外，从结果上来看[平均查找长度去掉系数之后就是时间复杂度][Link 8]。

链表属于顺序查找，红黑树可以看作二叉树，属于二分查找。

对于顺序查找来说，假设存在 n 个数，每个数字查找概率相等，那么有：

(1+2+3+4+...+n)/n = (n+1)/2

对于二分查找来说，其平均查询长度为：log2n。

这里就不推导了，感兴趣的看看这篇文章（https://www.jianshu.com/p/6d7b9c7fef3a）

因此，当链表长度为 **6** 时：

*  链表查询的平均长度为：**(n+1)/2 = (6+1)/2 = 3.5**
 *  红黑树查询的平均长度为：**log2n = log26 = 2.6**

因此，当链表长度为 **7** 时：

*  链表查询的平均长度为：**(n+1)/2 = (7+1)/2 = 4**
 *  红黑树查询的平均长度为：**log2n = log27 = 2.8**

当链表长度为 **8** 时：

*  链表查询的平均长度为：**(n+1)/2 = (8+1)/2 = 4.5**
 *  红黑树查询的平均长度为：**log2n = log28 = 3**

为什么链表的长度为 8 是变成红黑树？

我们对比一下，长度为 8 时红黑树的查询长度要低，而本来出现长度为 8 的概率就很低，若这么小的概率都出现了，那说明很有必要进行树化。那么为什么不选择 6 呢？虽然 6 的速度也很快，但是概率比 8 的概率高，因此树化的可能性就越大，**转化和生成树本身就耗费时间**。

为什么红黑树大小为 6 时又变成链表？

主要是因为，如果也将该阈值设置于 8，那么当 hash 碰撞在 8 时，会反生链表和红黑树的不停相互转换，白白浪费资源。中间有个差值 7 可以防止链表和树之间的频繁转换，假设一下：

如果设计成链表个数超过 8 则链表转换成树结构，链表个数小于 8 则树结构转换成链表，如果 HashMap 不停的插入，删除元素，链表个数在 8 左右徘徊，就会频繁的发生红黑树转链表，链表转红黑树，效率会很低下。

如果设计成链表个数超过 7 则链表转换成树结构，跳出技术角度来说，千万分之一的概率都能碰到，说明是真的牛逼，那假设红黑树大小为 7 时变成链表，那万一又达到 8 了呢？（因为前面 8 这么低的概率还达到了 8），所以此时又要变成红黑树，还是会频繁的发生红黑树转链表，链表转红黑树，同样效率低下。

所以干脆中间给一个过渡值 7，差值 7 可以防止链表和树之间的频繁转换。

### 10. HashMap 相关面试题 ###

**1、HashMap 的数据结构？**

1.7：数组+链表

1.8：数组+链表+红黑树

**2、HashMap 的工作原理？**

HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry<K,V>接口）实现，HashMap 通过 put & get 方法存储和获取。

存储对象时，将 K/V 键值传给 put() 方法：

1.  调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；
2.  调整数组大小（当容器中的元素个数大于 capacity \* loadfactor 时，容器会进行扩容resize 为 2n）；
    
     *  如果 K 的 hash 值在 HashMap 中不存在，则执行插入，若存在，则发生碰撞；
     *  如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 true，则更新键值对；
     *  如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 false，则插入链表的尾部（尾插法）或者红黑树中（树的添加方式）。

获取对象时，将 K 传给 get() 方法：

1.  调用 hash(K) 方法（计算 K 的 hash 值）从而获取该键值所在链表的数组下标；
2.  顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。

hashCode 是定位的，存储位置；equals是定性的，比较两者是否相等。

**3、当两个对象的 hashCode 相同会发生什么？**

因为 hashCode 相同，不一定就是相等的（equals方法比较），所以两个对象所在数组的下标相同，"碰撞"就此发生。又因为 HashMap 使用链表存储对象，这个 Node 会存储到链表中。

**4、你知道 hash 的实现吗？为什么要这样实现？**

JDK 1.8 中，是通过 hashCode() 的高 16 位异或低 16 位实现的：`(h = k.hashCode()) ^ (h >>> 16)`，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。

**5、为什么要用异或运算符？**  
保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。

**6、HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？**

①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；

②、loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；

③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）

④、如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。

**7、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？**

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

[Link 1]: https://baike.baidu.com/item/%E8%BE%93%E5%85%A5/5481954
[Link 2]: https://baike.baidu.com/item/%E8%BE%93%E5%87%BA/11056752
[Link 3]: https://baike.baidu.com/item/%E5%8E%8B%E7%BC%A9%E6%98%A0%E5%B0%84/5114126
[Link 4]: https://baike.baidu.com/item/%E6%B6%88%E6%81%AF%E6%91%98%E8%A6%81/4547744
[Link 5]: https://baike.baidu.com/item/Hash/390310?fr=aladdin
[image-20211231163103280]: https://img-blog.csdnimg.cn/img_convert/3ef9e8830b8631b5a82acaab1eb4ccde.png
[image-20220104173345810]: https://img-blog.csdnimg.cn/img_convert/8b30f62daf9fd2cf813462ce819aaf7c.png
[Java]: https://blog.csdn.net/weixin_43477531/article/details/107032305
[image-20220104145843344]: https://img-blog.csdnimg.cn/img_convert/635fe1dae623dcb184c14ff3a88ab04f.png
[image-20220104202142219]: https://img-blog.csdnimg.cn/img_convert/e2ceccc3d89f2f1770ecf2dda0278a06.png
[image-20220105115942079]: https://img-blog.csdnimg.cn/img_convert/3ff5a426e42abb3c372d31c97ab2b42d.png
[image-20220105195041298]: https://img-blog.csdnimg.cn/img_convert/208074a762aed7fd81381c6f61d2dece.png
[image-20220105202014726]: https://img-blog.csdnimg.cn/img_convert/11d99ae09ca6ab5c81c579f015b08d9a.png
[image-20220106152324204]: https://img-blog.csdnimg.cn/img_convert/fb909695d0aa4937f5c053e9795766fc.png
[image-20220107161745890]: https://img-blog.csdnimg.cn/img_convert/a0b5b239ff17856cecc1f4a9405da65c.png
[image-20220107163640649]: https://img-blog.csdnimg.cn/img_convert/1f07e8887036191f383e10e58f3007bf.png
[image-20220107175932194]: https://img-blog.csdnimg.cn/img_convert/88afd9826dd646ae0c2d73a280b6a872.png
[image-20220107180130441]: https://img-blog.csdnimg.cn/img_convert/1264f294ae7692568ad4ed4e18b02755.png
[image-20220108131439917]: https://img-blog.csdnimg.cn/img_convert/8914621b49cbd9dd06c1e727473ba6cb.png
[image-20220108133603691]: https://img-blog.csdnimg.cn/img_convert/e0ada7a952e67e036eec21326886c601.png
[Link 6]: https://javatv.blog.csdn.net/article/details/119120401
[Link 7]: https://baike.baidu.com/item/%E6%B3%8A%E6%9D%BE%E5%88%86%E5%B8%83/1442110
[Link 8]: https://www.zhihu.com/question/21680896/answer/466229561