【搞定Java集合框架】第5篇：HashMap JDK1.7 && JDK 1.8 【面试重点】

Love The Way You Lie 2022-03-26 05:10 57阅读 0赞

本文大部分内容来自于：[https://blog.csdn.net/a724888/article/details/80277176][https_blog.csdn.net_a724888_article_details_80277176]

## **本文目录：** ##

**1、HashMap【JDK1.7】**

1.1  定义

1.2  构造函数

1.3  数据结构

1.4  存储实现：put(key, value)

1.5  读取实现：get(key)

**2、HashMap【JDK1.8】**

2.1  HashMap 的成员属性源码分析

2.2  HashMap 构造器源码分析

2.3  HashMap 内部类——Node 源码分析

2.4  tableSizeFor 函数源码分析

2.5  HashMap 的 get 函数源码分析

2.6  HashMap 的 put 函数源码分析

2.7  HashMap 的 resize 函数源码分析  【重点中的重点】

**3、HashMap 面试“明星”问题汇总**

--------------------

# 1、HashMap【JDK1.7】 #

本部分内容转发自：[http://cmsblogs.com/?p=176][http_cmsblogs.com_p_176]

HashMap也是我们使用非常多的 Collection，它是基于哈希表的 Map 接口的实现，以 key-value 的形式存在。在HashMap中，key-value 总是会当做一个整体来处理，系统会根据 hash 算法来计算key-value的存储位置，我们总是可以通过key 快速地存、取value。下面就来分析 HashMap 的存取。

## 1.1  定义 ##

HashMap 实现了 Map 接口，继承 AbstractMap。其中 Map 接口定义了键映射到值的规则，而 AbstractMap 类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作，其实 AbstractMap 类已经实现了 Map。

public class HashMap<K,V> extends AbstractMap<K,V>
                              implements Map<K,V>, Cloneable, Serializable{
        
        // ...
    }

## 1.2  构造函数 ##

HashMap提供了三个构造函数：

> 1、HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
> 
> 2、HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
> 
> 3、HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。

在这里提到了两个参数：**初始容量、加载因子**。

这两个参数是影响 HashMap 性能的重要参数，其中：

**容量表示哈希表中桶的数量**，初始容量是创建哈希表时的容量。

**加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，加载因子越大表示散列表的装填程度越高，反之愈小。**

对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

## 1.3  数据结构 ##

我们知道在 Java 中最常用的两种结构是数组和链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap 也是如此。实际上**HashMap是一个“链表散列”**，如下是它数据结构：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

从上图我们可以看出 **HashMap 底层实现还是数组，只是数组的每一项都是一条链表**。其中参数 initialCapacity 就代表了该数组的长度。下面为 HashMap 构造函数的源码：

public HashMap(int initialCapacity, float loadFactor) {
    	// 初始容量不能<0
    	if (initialCapacity < 0)
    		throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    	// 初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
    	if (initialCapacity > MAXIMUM_CAPACITY)
    		initialCapacity = MAXIMUM_CAPACITY;
    	// 负载因子不能 < 0
    	if (loadFactor <= 0 || Float.isNaN(loadFactor))
    		throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    	// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
    	int capacity = 1;
    	while (capacity < initialCapacity)
    		capacity <<= 1;
    
    	this.loadFactor = loadFactor;
    	// 设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
    	threshold = (int) (capacity * loadFactor);
    	// 初始化table数组
    	table = new Entry[capacity];
    	init();
    }

从源码中可以看出，每次新建一个 HashMap 时，都会初始化一个 table 数组。table 数组的元素为 Entry 节点。

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

其中 Entry 为 HashMap 的内部类，它包含了键 key、值 value、下一个节点 next，以及 hash 值，这是非常重要的，正是由于 Entry 才构成了 table 数组的项为链表。

上面简单分析了 HashMap 的数据结构，下面将探讨 HashMap 是如何实现快速存取的。

## 1.4  存储实现：put(key, value) ##

先看源码：

public V put(K key, V value) {
    	// 当key为null，调用putForNullKey方法
    	// 保存null于table第一个位置中，这是HashMap允许为null的原因
    	if (key == null)
    		return putForNullKey(value);
    	// 计算key的hash值
    	int hash = hash(key.hashCode());                  ------(1)
    	// 计算key hash 值在 table 数组中的位置
    	int i = indexFor(hash, table.length);             ------(2)
    	// 从i出开始迭代 e,找到 key 保存的位置
    	for (Entry<K, V> e = table[i]; e != null; e = e.next) {
    		Object k;
    		// 判断该条链上是否有hash值相同的(key相同)
    		// 若存在相同，则直接覆盖value，返回旧value
    		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    			V oldValue = e.value;    // 旧值 = 新值
    			e.value = value;
    			e.recordAccess(this);
    			return oldValue;     // 返回旧值
    		}
    	}
    	// 修改次数增加1
    	modCount++;
    	// 将key、value添加至i位置处
    	addEntry(hash, key, value, i);
    	return null;
    }

通过源码我们可以清晰看到 HashMap 保存数据的过程为：

> 1、首先判断 key 是否为 null，若为 null，则直接调用 putForNullKey 方法；
> 
> 2、若不为空则先计算 key 的 hash 值；
> 
> 3、然后根据 hash 值搜索在 table 数组中的索引位置；
> 
> 4、如果 table 数组在该位置处有元素，则通过比较是否存在相同的 key，若存在则覆盖原来 key 的 value，否则将该元素保存在链头（最先保存的元素放在链尾）；
> 
> 5、若 table 在该处没有元素，则直接保存。

这个过程看似比较简单，其实深有内幕。有如下几点：

> 1、 先看迭代处。此处迭代原因就是为了防止存在相同的 key 值，若发现两个 hash 值（key）相同时，HashMap 的处理方式是用新 value 替换旧 value，这里并没有处理 key，这就解释了 HashMap 中没有两个相同的 key。
> 
> 2、 在看（1）、（2）处。这里是 HashMap 的精华所在。首先是hash方法，该方法为一个纯粹的数学计算，就是计算 h的 hash 值。

> 散列冲突指的是：不同的 key 经过hash 算法产生了相同的 hash 值。HashMap 解决散列冲突的方法是：拉链法，即在数组的每个下标处都拉出一个链表，用于存储 hash 值相同的 key。

*  **hash(int  h) 的源码： **

hashMap 中所采用的 hash 算法。

static int hash(int h) {
    	h ^= (h >>> 20) ^ (h >>> 12);
    	return h ^ (h >>> 7) ^ (h >>> 4);
    }

我们知道对于 HashMap 的 table 而言，数据分布需要均匀（最好每项都只有一个元素，这样就可以直接找到），不能太紧也不能太松，太紧会导致查询速度慢，太松则浪费空间。计算 hash 值后，怎么才能保证 table元 素分布均与呢？我们会想到取模，但是由于取模的消耗较大，HashMap 是这样处理的：调用 indexFor 方法。

static int indexFor(int h, int length) {
    	return h & (length-1);
    }

HashMap 的底层数组长度总是 2 的 n 次方。在构造函数中存在：capacity <<= 1; 这样做总是能够保证 HashMap 的底层数组长度为 2 的 n 次方。当 length 为 2 的 n 次方时，h & (length – 1) 就相当于对 length [取模][Link 1]，而且速度比直接取模快得多，这是 HashMap 在速度上的一个优化。至于**为什么是 2 的 n 次方【因为发生碰撞的概率最小】**下面解释。

我们回到 indexFor 方法，该方法仅有一条语句：h & (length – 1)，这句话除了上面的取模运算外还有一个非常重要的责任：均匀分布 table 数据和充分利用空间。

*  **这里举例解释下为什么 HashMap 的数组长度总是 2 的 n 次方？ **

这里我们假设 length 为 16(2 ^ n) 和 15，h 为 5、6、7。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

当 n = 15 时，6 和 7 的结果一样，这样表示他们在 table 存储的位置是相同的，也就是产生了碰撞，6、7 就会在一个位置形成链表，这样就会导致查询速度降低。诚然这里只分析三个数字不是很多，那么我们就看 0-15。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]

从上面的图表中我们看到总共发生了 8 次碰撞，同时发现浪费的空间非常大，有1、3、5、7、9、11、13、15 处没有记录，也就是没有存放数据。这是因为它们在与 14进行 & 运算时，得到的结果最后一位永远都是0，即0001、0011、0101、0111、1001、1011、1101、1111 位置处是不可能存储数据的。这样致使存储数据的空间减少，进一步增加碰撞几率，从而导致查询速度慢。

**而当 length = 16 时，length – 1 = 15 即 1111，那么进行低位 & 运算时，值总是与原来 hash 值相同，而进行高位运算时，其值等于其低位值。所以说当 length = 2 ^ n 时，不同的 hash 值发生碰撞的概率比较小，这样就会使得数据在 table 数组中分布较均匀，查询速度也较快。**

这里我们再来复习 put 的流程：当我们想往一个 HashMap 中添加一对 key-value 时，系统首先会计算 key 的 hash 值，然后根据 hash 值确认在 table 中存储的位置。若该位置没有元素，则直接插入。否则迭代该处元素链表并依次比较其 key 的 hash 值。如果两个 hash 值相等且 key 值相等(e.hash == hash && ((k = e.key) == key || key.equals(k)))，则用新的 Entry 的 value 覆盖原来节点的 value。如果两个 hash 值相等但 key 值不等 ，则将该节点插入该链表的链头。具体的实现过程见 addEntry 方法，如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
    	// 获取bucketIndex处的Entry
    	Entry<K, V> e = table[bucketIndex];
    	// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
    	table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
    	// 若HashMap中元素的个数超过极限了，则容量扩大两倍
    	if (size++ >= threshold)
    		resize(2 * table.length);
    }

这个方法中有两点需要注意：

*  **一是链的产生：**

这是一个非常优雅的设计。系统总是将新的 Entry 对象添加到 bucketIndex 处。如果 bucketIndex 处已经有了对象，那么新添加的 Entry 对象将指向原有的 Entry 对象，形成一条 Entry 链，但是若 bucketIndex 处没有 Entry 对象，也就是 e == null，那么新添加的 Entry 对象指向null，也就不会产生Entry链了。

*  **二、扩容问题：**

随着 HashMap 中元素的数量越来越多，发生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响 HashMap 的速度，为了保证 HashMap 的效率，系统必须要在某个临界点进行扩容处理。该临界点在当 HashMap 中元素的数量等于 table 数组长度\*加载因子。但是**扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新 table 数组中的位置并进行复制处理**。所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。

## 1.5  读取实现：get(key) ##

相对于 HashMap 的存而言，取就显得比较简单了。通过 key 的 hash 值找到在 table 数组中的索引处的 Entry，然后返回该 key 对应的 value 即可。

public V get(Object key) {
    	// 若 key 为null，调用getForNullKey方法返回相对应的value
    	if (key == null)
    		return getForNullKey();
    	// 根据该 key 的 hashCode 值计算它的 hash 码  
    	int hash = hash(key.hashCode());
    	// 取出 table 数组中指定索引处的值
    	for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
    		Object k;
    		// 若搜索的key与查找的key相同，则返回相对应的value
    		if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    			return e.value;
    	}
    	return null;
    }

在这里能够根据 key 快速的取到 value 除了和 HashMap 的数据结构密不可分外，还和 Entry 有莫大的关系，在前面就提到过，HashMap 在存储过程中并没有将 key，value 分开来存储，而是当做一个整体 key-value 来处理的，这个整体就是Entry 对象。同时 value 也只相当于 key 的附属而已。在存储的过程中，系统根据 key 的 hashcode 来决定 Entry 在 table 数组中的存储位置，在取的过程中同样根据 key 的 hashcode 取出相对应的 Entry 对象（value 就包含在里面）。

--------------------

# 2、HashMap【JDK1.8】 #

因为 HashMap 在面试中是重中之重，所以必须对其实现能够熟练的掌握。这里再从头分析下 HashMap 在 JDK1.8 中的实现。很多是和 JDK1.7 相同的，但是要注意其在 JDK1.8 中改进的地方。

该部分内容来源于以下两篇文章：

> [1、一篇文章彻底读懂HashMap之HashMap源码解析（上）][1_HashMap_HashMap]
> 
> [2、一篇文章彻底读懂HashMap之HashMap源码解析（下）][2_HashMap_HashMap]

## 2.1  HashMap 的成员属性源码分析 ##

public class HashMap<K,V> extends AbstractMap<K,V>
    			  implements Map<K,V>, Cloneable, Serializable {
    
    	private static final long serialVersionUID = 362498820763181265L;
    
    	// HashMap的初始容量为16，HashMap的容量指的是存储元素的数组大小，即桶的数量
    	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
    	// HashMap的最大的容量
    	static final int MAXIMUM_CAPACITY = 1 << 30; 
    
    	// 下面有详细解析
    	static final float DEFAULT_LOAD_FACTOR = 0.75f;
    	
    	// 当某一个桶中链表的长度>=8时，链表结构会转换成红黑树结构,
    	// 其实还要求桶的中元素数量>=64,后面会提到
    	static final int TREEIFY_THRESHOLD = 8;
    
    	// 当红黑树中的节点数量<=6时，红黑树结构会转变为链表结构
    	static final int UNTREEIFY_THRESHOLD = 6;
    
    	// 上面提到的：当Node数组容量>=64的前提下，如果某一个桶中链表长度>=8，
    	// 则会将链表结构转换成红黑树结构
    	static final int MIN_TREEIFY_CAPACITY = 64;
    }

*  **DEFAULT\_LOAD\_FACTOR**

DEFAULT\_LOAD\_FACTOR：HashMap 的负载因子，影响 HashMap 性能的参数之一，是时间和空间之间的权衡，后面会看到 HashMap 的元素存储在 Node 数组中，这个数组的大小这里称为“桶”的大小。另外还有一个参数 size 指的是我们往HashMap 中 put了多少个元素。当size > 桶的数量 \* DEFAULT\_LOAD\_FACTOR的时候，这时HashMap要进行扩容操作，也就是桶不能装满。DEFAULT\_LOAD\_FACTOR是衡量桶的利用率。

DEFAULT\_LOAD\_FACTOR较小时（桶的利用率较小），这时浪费的空间较多（因为只能存储桶的数量DEFAULT\_LOAD\_FACTOR个元素，超过了就要进行扩容），这种情况下往 HashMap 中 put 元素时发生冲突的概率也很小，所谓冲突指的是：多个元素被 put 到了同一个桶中。冲突小时（可以认为一个桶中只有一个元素）put、get 等 HashMap 的操作代价就很低，可以认为是O(1)。

DEFAULT\_LOAD\_FACTOR很大时，桶的利用率较大的时候(注意可以大于1，因为冲突的元素是使用链表或者红黑树连接起来的)，此时空间利用率较高，这也意味着一个桶中存储了很多元素，这时 HashMap 的 put、get 等操作代价就相对较大，因为每一个 put 或 get 操作都变成了对链表或者红黑树的操作，代价肯定大于O(1)，所以说 DEFAULT\_LOAD\_FACTOR 是空间和时间的一个平衡点。

> DEFAULT\_LOAD\_FACTOR较小时，需要的空间较大，但是 put 和 get 的代价较小;
> 
> DEFAULT\_LOAD\_FACTOR较大时，需要的空间较小，但是 put 和 get 的代价较大）。

扩容操作就是把桶的数量乘以2，即把 Node 数组的大小调整为扩容前的 2 倍，至于为什么是两倍，分析扩容函数时会讲解，这其实是一个 trick，细节后面会详细讲解。Node 数组中每一个桶中存储的是 Node 链表，当链表长度 >=8 的时候并且Node数组的大小 >=64，链表会变为红黑树结构（因为红黑树的增删改查复杂度是 O(logn)，链表是O(n)，红黑树结构比链表代价更小）。

下面再看看其他几个成员属性：

// 我们往map中put的(k,v)都被封装在Node中，所有的Node都存放在table数组中
    transient Node<K,V>[] table;
    
    // 用于返回keySet和values
    transient Set<Map.Entry<K,V>> entrySet;
    
    // 保存map当前有多少个元素
    transient int size;
    
    // failFast机制，在讲解ArrayList和LinkedList一文中已经讲过了
    transient int modCount;

*  **threshold 属性分析**

int threshold; // 下面有详细讲解
    
    // 负载因子，见上面对DEFAULT_LOAD_FACTOR参数的讲解，默认值是0.75
    final float loadFactor;

threshold 也是比较重要的一个属性：创建 HashMap 时，该变量的值是：初始容量（2 的整数次幂），之后 threshold的值是 HashMap 扩容的门限值，即当前 Nodetable 数组的长度 \* loadfactor。

举个例子而言，如果我们传给 HashMap 构造器的容量大小为 9，那么 threshold 初始值为16，在向 HashMap 中 put 第一个元素后，内部会创建长度为 16 的 Node 数组，并且 threshold 的值更新为 16 \* 0.75=12。具体而言，当我们一直往HashMap 中 put 元素的时候，如果put某个元素后，Node数组中元素个数为 13，此时会触发扩容（因为数组中元素个数> threshold了，即13 > threshold = 12），具体扩容操作之后会详细分析，简单理解就是，扩容操作将 Node 数组长度 \* 2；并且将原来的所有元素迁移到新的 Node 数组中。

## 2.2  HashMap 构造器源码分析 ##

// 构造器：指定map的大小，和loadfactor
    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);
    	   // 保存loadfactor
    	   this.loadFactor = loadFactor;
    
    	/* 注意，前面有讲tableSizeFor函数，该函数返回值：>= initialCapacity、
    	返回值是2的整数次幂，并且得是满足上面两个条件的所有数值中最小的那个数 */
    	this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 只指定HashMap容量的构造器，loadfactor使用的是默认的值:0.75
    public HashMap(int initialCapacity) {
    	this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    // 无参构造器，默认loadfactor：0.75,默认的容量是16
    public HashMap() {
    	this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    
    // 其他不常用的构造器就不分析了

从构造器中我们可以看到：**HashMap 是“懒加载”**，在构造器中值保留了相关保留的值，并没有初始化 table<Node> 数组，当我们向 map 中 put 第一个元素的时候，map 才会进行初始化！

## 2.3  HashMap 内部类——Node 源码分析 ##

// Node是HashMap的内部类
    static class Node<K,V> implements Map.Entry<K,V> {
    	final int hash; 
    	final K key;     // 保存map中的key
    	V value;         // 保存map中的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;
    	}
    }

HashMap 的内部类 Node：HashMap 的所有数据都保存在 Node 数组中。那么这个 Node 到底是个什么东西呢？

Node 的 hash 属性：保存 key 的 hashcode 的值：key的 hashcode ^ (key 的 hashcode >>> 16)。这样做主要是为了减少 hash 冲突。当我们往 map 中 put(k, v) 时，这个 k,v 键值对会被封装为 Node，那么这个 Node 放在 Node 数组的哪个位置呢：**index = hash & (n-1)**，n 为 Node 数组的长度。

那为什么这样计算 hash 可以减少冲突呢？

**如果直接使用 hashCode & (n - 1) 来计算 index，此时 hashCode 的高位随机特性完全没有用到，因为 n 相对于hashCode 的值很小，计算 index 的时候只能用到低 16 位。基于这一点，把 hashCode 高 16 位的值通过异或混合到hashCode 的低 16 位，由此来增强 hashCode 低 16 位的随机性。**

*  **HashMap 中的 hash 函数**

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

HashMap 允许 key 为null，null 的 hash 为 0（也意味着 HashMap 允许 key 为 null 的键值对）。**非 null 的 key 的 hash 高 16 位和低 16 位分别由由：key 的 hashCode 高 16 位和 hashCode 的高 16 位异或 hashCode 的低16位组成。主要是为了增强 hash 的随机性，减少 hash & (n - 1) 的随机性，即减小 hash 冲突，提高 HashMap 的性能**。所以作为HashMap 的 key 的 hashCode 函数的实现对 HashMap 的性能影响较大，极端情况下：所有 key 的 hashCode 都相同，这是HashMap 的性能很糟糕！

## 2.4  tableSizeFor 函数源码分析  ##

static final int tableSizeFor(int cap) {
    	// 举例而言：n的第三位是1(从高位开始数)， 
    	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;
    }

在 new HashMap 的时候，如果我们传入了大小参数，这是 HashMap 会对我们传入的 HashMap 容量进行传到tableSizeFor 函数处理。**这个函数主要功能是：返回一个数。这个数是大于等于 cap 并且是 2 的整数次幂的所有数中最小的那个，即返回一个最接近 cap(>= cap)，并且是 2 的整数次幂的数**。

具体逻辑如下：一个数是 2 的整数次幂，那么这个数减 1 的二进制就是一串掩码，即二进制从某位开始是一 串连续的1。所以只要对相应的掩码 +1 一定是 2 的整数次幂，这也是为什么 n = cap - 1 的原因。

举例而言，假设：n=00010000\_00000000\_00000000

n = 00010000_00000000_00000000    
    
    n |= n >>> 1; //执行完后
    // n = 00011000_00000000_00000000
    
    n |= n >>> 2; // 执行完后
    // n = 00011110_00000000_00000000
    
    n |= n >>> 4; // 执行完后
    // n = 00011111_11100000_00000000
    
    n |= n >>> 8; // 执行完后
    
    // n = 00011111_11111111_11100000
    
    n |= n >>> 16; // 执行完后
    // n = 00011111_11111111_11111111

返回 n + 1，(n + 1) >= cap、为2的整数次幂，并且是与 cap 差值最小的那个数。最后的 n+1 一定是 2 的整数次幂，并且一定是 >= cap。

整体的思路就是：如果 n 的二进制的第 k 为1，那么经过上面四个 ‘|’ 运算后 \[0 ,k\] 位都变成了1，即：一连串连续的二进制‘1’(掩码)，最后 n+1 一定是 2 的整数次幂（如果不溢出）。

## 2.5  HashMap 的 get 函数源码分析 ##

*  **get(Object  key)函数**

// 入口,返回对应的value
    public V get(Object key) {
    	Node<K,V> e;
    		
    	// hash函数上面分析过了
    	return (e = getNode(hash(key), key))== null ? null : e.value;
    }

**get 函数实质就是进行链表或者红黑树遍历搜索指定的 key 的节点的过程**。

另外需要注意到 HashMap 的 get 函数的返回值不能判断一个 key 是否包含在 map 中，get 返回 null 有可能是不包含该 key；也有可能该 key 对应的 value 为 null。因为 HashMap 中允许 key 为 null，也允许 value 为 null。

*  **getNode(int  hash, Object  key) 函数**

// 下面分析getNode函数
    final Node<K,V> getNode(int hash, Object key) {
    	Node<K,V>[] tab;
    	Node<K,V> first, e;
    	int n; K k;
    	if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1 ) & hash]) != null) {
    		if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
    			// 一次就匹配到了，直接返回，否则进行搜索
    			return first;
    		if ((e = first.next) != null) {
    			if (first instanceof TreeNode)
    				// 红黑树搜索/查找
    				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    			do {
    				// 链表搜索(查找)
    				if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    					return e;//找到了就返回
    			} while ((e = e.next) != null);
    		}
    	}
    	return null;  // 没找到，返回null
    }

注意 getNode 返回的类型是 Node：当返回值为 null 时表示 map 中没有对应的 key，注意区分 value 为 null；如果 key对应的 value 为 null 的话，体现在 getNode 的返回值 e.value 为 null，此时返回值也是 null，也就是 HashMap 的 get 函数不能判断 map 中是否有对应的key。get 返回值为 null 时，可能不包含该 key，也可能该 key 的 value 为 null。那么如何判断map 中是否包含某个 key 呢？见下面 contains 函数分析。getNode函数细节分析：

(n - 1) & hash：当前 key 可能在的桶索引，put 操作时也是将 Node 存放在 index = (n - 1) & hash 的位置。

getNode的主要逻辑：如果 table\[index\] 处节点的 key 就是要找的 key 则直接返回该节点； 否则：如果在 table\[index\] 位置进行搜索，搜索是否存在目标 key 的 Node：这里的搜索又分两种：链表搜索和红黑树搜索，具体红黑树的查找就不展开了，红黑树是一种弱平衡(相对于AVL)BST，红黑树查找、删除、插入等操作都能够保证在O(logn)时间复杂度内完成，红黑树原理不在本文范围内，但是大家要知道红黑树的各种操作是可以实现的，简单点可以把红黑树理解为BST，BST的查找、插入、删除等操作的实现在之前的文章中有[BST java实现][BST java]讲解，红黑树实际上就是一种平衡的BST。

*  **contains 函数源码分析**

public boolean containsKey(Object key) {
    	// 注意与get函数区分，我们往map中put的所有的<key,value>都被封装在Node中，
    	// 如果Node都不存在显然一定不包含对应的key
    	return getNode(hash(key), key) != null;
    }

## 2.6  HashMap 的 put 函数源码分析 ##

// put函数入口,两个参数：key和value
    public V put(K key, V value) {
    	// 下面分析这个函数，注意前3个参数，后面2个参数这里不太重要，因为所有的put操作后面的2个参数默认值都一样
    	return putVal(hash(key), key, value, false, true);
    }
    	
    // 下面是put函数的核心处理函数putVal
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    	Node<K,V>[] tab; 
    	Node<K,V> p; 
    	int n, i;
    	// 上面提到过HashMap是懒加载，所有put的时候要先检查table数组是否已经初始化了，
    	// 没有初始化得先初始化table数组，保证table数组一定初始化了
    	if ((tab = table) == null || (n = tab.length) == 0)
    		// 这个函数后面有resize函数分析
    		n = (tab = resize()).length;
    
    	/* 到这里表示table数组一定初始化了，与上面get函数相同，指定key的Node，
    	会存储在在table数组的i=(n-1)&hash下标位置，get的时候也是从table数组的该位置搜索 */
    	if ((p = tab[i = (n - 1) & hash])== null)
    		// 如果i位置还没有存储元素，则把当前的key，value封装为Node，存储在table[i]位置 
    		tab[i] = newNode(hash, key, value, null);
    	else {
    		 /* 如果table[i]位置已经有元素了，则接下来的流程是：
    			首先判断链表或者二叉树中是否已经存在key的键值对?
    			存在的话就更新它的value；不存在的话把当前的key，value插入到链表的末尾或者插入到红黑树中
    			如果链表或者红黑树中已经存在，Node.key等于key，则e指向该Node，
    			即e指向一个Node：该Node的key属性与put时传入的key参数相等的那个Node，后面会更新e.value
    		 */
    
    		Node<K,V> e; K k;
    		
    		/* 为什么get和put先判断p.hash==hash,下面的if条件中去掉hash的比较逻辑也是正确？
    		   因为hash的比较是两个整数的比较，比较的代价相对较小，
    		   key是泛型，对象的比较比整数比较代价大，所以先比较hash，hash相等再比较key
    		*/
    		if(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    		// e指向一个Node：该Node的key属性与put时传入的key参数相等的那个Node		  
    			e = p;
    		else if (p instanceof TreeNode)
    			// 红黑树的插入操作，如果已经存在该key的TreeNode，则返回该TreeNode，否则返回null
    			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    		else {
    			/* 如果table[i]处存放的是链表，接下来和TreeNode类似在遍历链表过程中先判断
    			   当前的key是否已经存在，如果存在则令e指向该Node；否则将该Node插入到链表末尾，
    			   插入后判断链表长度是否>=8，是的话要进行额外操作 */
    			// binCountt最后的值是链表的长度
    			for (int binCount = 0;;++binCount) {
    				if ((e = p.next) == null) {
    				/* 遍历到了链表最后一个元素,接下来执行链表的插入操作，先封装为Node,
    				再插入p指向的是链表最后一个节点，将待插入的Node置为p.next，就完成了单链表的插入 */
    					p.next = newNode(hash, key, value, null);
    					if (binCount >= TREEIFY_THRESHOLD - 1)
    					 
    					/* TREEIFY_THRESHOLD值是8,binCount>=7,然后又插入了一个新节点，链表长度>=8，
    					   这时要么进行扩容操作，要么把链表结构转为红黑树结构。我们接下会分析treeifyBin的源码实现 */
    					treeifyBin(tab, hash);
    					break;
    				 }
    
    				 /* 当p不是指向链表末尾的时候：先判断p.key是否等于key，等于的话表示当前key已经存在了，
    					令e指向p，停止遍历，最后会更新e的value;不等的话准备下次遍历，令p=p.next，即p=e。 */
    				if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    					break;
    				p = e;
    			}
    		}
    		
    		if (e != null) {
    			/*  表示当前的key在put之前已经存在了，并且上面的逻辑保证:
    				e已经指向了之前已经存在的Node，这时更新e.value就好。  */
    
    			// 更新oldvalue
    			V oldValue = e.value;
    
    			/* onlyIfAbsent默是false，evict为true。onlyIfAbsent为true表示：
    			 如果之前已经存在key这个键值对了，那么后面再put这个key时，忽略这个操作，不更新先前的value。
    			 这里了解就好 */
    			if (!onlyIfAbsent || oldValue == null)
    				// 更新e.value
    				e.value = value;
    
    			/* 这个函数的默认实现是“空”，即这个函数默认什么操作都不执行，那为什么要有它呢？
    			   这其实是个hook/钩子函数，主要要在LinkedHashMap（HashMap子类）中使用，
    			   LinkedHashMap重写了这个函数。以后会有讲解LinkedHashMap的文章。*/
    			afterNodeAccess(e);
    			// 返回旧的value
    			return oldValue;
    		}
    	}
    
    	// 如果是第一次插入key这个键，就会执行到这里
    	++modCount;    // failFast机制
    
    	/* size保存的是当前HashMap中保存了多少个键值对，HashMap的size方法就是直接返回size之前说过，
    	threshold保存的是当前table数组长度*loadfactor，如果table数组中存储的Node数量大于threshold，
    	这时候会进行扩容，即将table数组的容量翻倍。后面会详细讲解resize方法。*/
    	if (++size > threshold)
    		resize();
    			 
    	// 这也是一个hook函数，作用和afterNodeAccess一样
    	afterNodeInsertion(evict);
    	return null;
    }

*  **treeifyBin 源码解析**

// 将链表转换为红黑树结构，在链表的插入操作后调用
    final void treeifyBin(Node<K,V>[] tab, int hash) {
    	int n, index; 
    	Node<K,V> e;
    
    	/*  MIN_TREEIFY_CAPACITY值是64,也就是当链表长度>8的时候，有两种情况：
    	    如果table数组的长度<64,此时进行扩容操作;
    	    如果table数组的长度>64，此时进行链表转红黑树结构的操作.具体转细节在面试中几乎没有问的，
    	    这里不细讲了，大部同学认为链表长度>8一定会转换成红黑树，这是不对的！*/
    	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    		resize();   // 扩容
    	else if ((e = tab[index = (n - 1) & hash]) != null) {
    		TreeNode<K,V> hd = null, tl = null;
    		do {
    			TreeNode<K,V> p = replacementTreeNode(e, null);
    			if (tl == null)
    				hd = p;
    			else {
    				p.prev = tl;
    				tl.next = p;
    			}
    			tl = p;
    		} while ((e = e.next) != null);
    		if ((tab[index] = hd) != null)
    			hd.treeify(tab);
    	}
    }

## 2.7  HashMap 的 resize 函数源码分析  【重点中的重点】 ##

**面试谈到 HashMap 必考 resize 相关知识**，整体思路介绍：

有两种情况会调用当前函数：

> 1、之前说过 HashMap 是懒加载，**第一次调用 HashMap 的 put 方法的时候 table 还没初始化，这个时候会执行 resize，进行table 数组的初始化**，table 数组的初始容量保存在 threshold 中（如果从构造器中传入的一个初始容量的话），如果创建HashMap 的时候没有指定容量，那么 table 数组的初始容量是默认值：16。即，初始化 table 数组的时候会执行 resize 函数。
> 
> 2、**扩容的时候会执行 resize 函数**，当 size 的值 > threshold 的时候会触发扩容，即执行 resize 方法，这时 table 数组的大小会翻倍。

注意我们每次扩容之后容量都是翻倍（ \* 2），所以HashMap的容量一定是2的整数次幂，那么**HashMap的容量为什么一定得是 2 的整数次幂呢？【面试重点】**。

要知道原因，首先回顾我们 put key 的时候，每一个 key 会对应到一个桶里面，桶的索引是这样计算的： index = hash & (n-1)，index 的计算最为直观的想法是：hash % n，即通过取余的方式把当前的 key、value 键值对散列到各个桶中；那么这里为什么不用取余(%)的方式呢？

原因是：**CPU对位运算支持较好，即位运算速度很快**。另外，当 n 是 2 的整数次幂时：hash & (n - 1) 与 hash % (n - 1) 是等价的，但是两者效率来讲是不同的，位运算的效率远高于取余 % 运算。

基于上面的原因，HashMap中使用的是 hash & (n - 1)。这还带来了一个好处，就是将旧数组中的 Node 迁移到扩容后的新数组中的时候有一个很方便的特性：HashMap 使用 table 数组保存 Node 节点，所以 table 数组扩容的时候（数组扩容一定得是先重新开辟一个数组，然后把就数组中的元素重新散列（rehash）到新数组中去。

这里举一个例子来来说明这个特性：下面以 Hash 初始容量 n = 16，默认 loadfactor = 0.75 举例（其他 2 的整数次幂的容量也是类似的），默认容量：n = 16，二进制：10000；n - 1：15，n - 1 二进制：01111。某个时刻，map 中元素大于16 \* 0.75=12，即 size > 12。此时会发生扩容，即会新建了一个数组，容量为扩容前的两倍，newtab，len = 32。

接下来我们需要把 table 中的 Node 搬移 （rehash）到 newtab。从 table 的 i = 0 位置开始处理，假设我们当前要处理table 数组 i 索引位置的 node，那这个 node 应该放在 newtab 的那个位置呢？

下面的 hash 表示 node.key 对应的 hash 值，也就等于node.hash 属性值。另外为了简单，下面的 hash 只写出了8位（省略的高位的0），实际上 hash 是32位。node 在 newtab 中的索引：

index = hash % len 
          = hash & (len-1) 
          = hash & (32 - 1)
          = hash & 31 
          = hash & (0x0001_1111)；

再看 node 在 table 数组中的索引计算：

i = hash & (16 - 1) 
      = hash & 15
      = hash & (0x0000_1111)。

注意观察两者的异同：

i = hash & (0x0000_1111);
    
    index = hash & (0x0001_1111)

上面表达式有个特点：

index = hash & (0x0001_1111)
    
          = hash & (0x0000_1111) | hash & (0x0001_0000) 
    
          = hash & (0x0000_1111) | hash & n)
    
          = i + ( hash & n)

什么意思呢？

hash & n 要么等于 n 要么等于 0。也就是：index 要么等于 i，要么等于 i + n。

再具体一点：当 hash & n == 0的时候，index = i。当 hash & n == n的时候，index = i + n。

这有什么用呢？

当我们把 table\[i\] 位置的所有 Node 迁移到 newtab 中去的时候：这里面的 node 要么在 newtab 的i位置（不变），要么在 newtab 的 i + n 位置。也就是我们可以这样处理：把 table\[i\] 这个桶中的 node 拆分为两个链表 l1 和 l2：如果hash & n == 0，那么当前这个 node 被连接到 l1 链表；否则连接到 l2 链表。这样下来，当遍历完 table\[i\] 处的所有 node 的时候，我们得到两个链表 l1 和 l2，这时我们令 newtab\[i\] = l1，newtab\[i + n\] = l2，这就完成了 table\[i\] 位置所有 node 的迁移（rehash），这也是 HashMap 中容量一定的是2的整数次幂带来的方便之处。

下面的 resize 的逻辑就是上面讲的那样。将 table\[i\] 处的 Node 拆分为两个链表，这两个链表再放到 newtab\[i\] 和newtab\[i + n\] 位置。

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;
    		}
    		// 正常扩容：newCap = oldCap << 1
    		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
    			// 容量翻倍，扩容后的threshold自然也是*2
    			newThr = oldThr << 1; 
    	}
    	else if (oldThr > 0) 
    	   newCap = oldThr;
    	else {
    	   // table数组初始化的时候会进入到这里
    	   // 默认容量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;    // 更新threshold
    	@SuppressWarnings({"rawtypes", "unchecked"})
    	// 扩容后的新数组
    	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    	table = newTab;        // 执行容量翻倍的新数组
    	if (oldTab != null) {
    		// 之后完成oldTab中Node迁移到table中去
    		for (int j = 0; j < oldCap; ++j) {
    			Node<K,V> e;
    			if ((e = oldTab[j]) != null) {
    				oldTab[j] = null;
    				if (e.next == null)
    				// j这个桶位置只有一个元素，直接rehash到table数组
    					newTab[e.hash & (newCap - 1)] = e;
    				else if (e instanceof TreeNode)
    					// 如果是红黑树：也是将红黑树拆分为两个链表，这里主要看链表的拆分，两者逻辑一样
    					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    				else { 
    					// 链表的拆分第一个链表l1
    					Node<K,V> loHead = null, loTail = null;
    
    					// 第二个链表l2
    					Node<K,V> hiHead = null, hiTail = null;
    					Node<K,V> next;
    					do {
    						next = e.next;
    						if ((e.hash & oldCap)== 0) {
    							// rehash到table[j]位置将当前node连接到l1上  
    							if (loTail == null)
    								loHead = e;
    							else
    								loTail.next = e;
    							loTail = e;
    						}
    						else {
    							// 将当前node连接到l2上
    							if (hiTail == null)
    								hiHead = e;
    							else
    								hiTail.next = e;
    							hiTail = e;
    						}
    					} while ((e = next) != null);
    
    					if (loTail != null) {
    						// l1放到table[j]位置
    						loTail.next = null;
    						newTab[j] = loHead;
    					}
    					if (hiTail != null) {
    						// l1放到table[j+oldCap]位置
    						hiTail.next = null;
    						newTab[j + oldCap] = hiHead;
    					}
    				}
    			}
    		}
    	}
    	return newTab;
    }

--------------------

# 3、HashMap 面试“明星”问题汇总 #

**你知道 HashMap 吗，请你讲讲 HashMap？**

**这个问题不单单考察你对 HashMap 的掌握程度，也考察你的表达、组织问题的能力。个人认为应该从以下几个角度入手（所有常见 HashMap 的考点问题总结）：**

> 1、size 必须是 2 的整数次方原因；
> 
> 2、get 和 put 方法流程；
> 
> 3、resize 方法；
> 
> 4、影响 HashMap 的性能因素（key 的 hashCode 函数实现、loadFactor、初始容量）；
> 
> 5、HashMap key 的 hash 值计算方法以及原因（见上面 hash 函数的分析）；
> 
> 6、HashMap 内部存储结构：Node 数组 + 链表或红黑树；
> 
> 7、table\[i\] 位置的链表什么时候会转变成红黑树（上面源码中有讲）；
> 
> 8、HashMap 主要成员属性：threshold、loadFactor、HashMap 的懒加载；
> 
> 9、HashMap 的 get 方法能否判断某个元素是否在 map 中；【不能：null】
> 
> 10、HashMap 线程安全吗，哪些环节最有可能出问题，为什么？
> 
> 11、HashMap 的 value 允许为 null，但是 HashTable 和 ConcurrentHashMap 的 value 都不允许为 null，试分析原因？
> 
> 12、HashMap 中的 hook 函数（在后面讲解 LinkedHashMap 时会讲到，这也是面试时拓展的一个点）

上面问题的答案都可以在上面的源码分析中找到，下面在给三点补充：

**1、HashMap 的初始容量是怎样影响 HashMap 的性能的？**

假如你预先知道最多往 HashMap 中存储 64 个元素，那么你在创建 HashMap 的时候：如果选用无参构造器：默认容量16，在存储 16\*loadFactor 个元素之后就要进行扩容（数组扩容涉及到连续空间的分配，Node 节点的 rehash，代价很高，所以要尽量避免扩容操作）。如果给构造器传入的参数是 64，这时 HashMap 中在存储 64 \* loadFactor 个元素之后就要进行扩容；但是如果你给构造器传的参数为：(int)(64/0.75) + 1，此时就可以保证 HashMap 不用进行扩容，避免了扩容时的代价。

**2、HashMap 线程安全吗，哪些环节最有可能出问题，为什么？**

我们都知道 **HashMap 线程不安全**，那么哪些环节最优可能出问题呢，及其原因：没有参照，这个问题有点不好直接回答，但是我们可以找参照啊。

参照：ConcurrentHashMap，因为大家都知道 HashMap 不是线程安全的，ConcurrentHashMap是线程安全的。对照ConcurrentHashMap，看看 ConcurrentHashMap 在 HashMap 的基础之上增加了哪些安全措施，这个问题就迎刃而解了。后面会有分析 ConcurrentHashMap 的文章。

这里先简要回答这个问题：**HashMap 的 put 操作是不安全的，因为没有使用任何锁。HashMap 在多线程下最大的安全隐患发生在扩容的时候**。想想一个场合：HashMap 使用默认容量 16，这时 100 个线程同时往 HashMap 中 put 元素，会发生什么？**扩容混乱**，因为扩容也没有任何锁来保证并发安全。另外，后面的博文会讲到 ConcurrentHashMap 的并发扩容操作是 ConcurrentHashMap 的一个核心方法。

**3、HashMap 的 value 允许为 null，但是 HashTable 和 ConcurrentHashMap 的 value 都不允许为 null，试分析原因？**

首先要明确 ConcurrentHashMap 和 Hashtable 从技术从技术层面讲是可以允许 value 为 null 。但是它们实际上是不允许的，这肯定是为了解决一些问题，为了说明这个问题，我们看下面这个例子（这里以 ConcurrentHashMap 为例，HashTable 也是类似）。

HashMap 由于允 value 为 null，get 方法返回 null 时有可能是 map 中没有对应的 key；也有可能是该 key 对应的 value 为 null。所以 get 不能判断 map 中是否包含某个 key，只能使用 contains 判断是否包含某个 key。

看下面的代码段，要求完成这个一个功能：**如果 map 中包含了某个 key ，则返回对应的 value，否则抛出异常**：

if (map.containsKey(k)) {
       return map.get(k);
    } else {
       throw new KeyNotPresentException();
    }

1、如果上面的 map 为HashMap，那么没什么问题，因为 HashMap 本来就是线程不安全的，如果有并发问题应该用ConcurrentHashMap，所以在单线程下面可以返回正确的结果。

2、如果上面的 map 为ConcurrentHashMap，此时存在并发问题：在 map.containsKey(k) 和 map.get 之间有可能其他线程把这个 key 删除了，这时候 map.get 就会返回 null，而 ConcurrentHashMap 中不允许 value 为 null，也就是这时候返回了 null，一个根本不允许出现的值？

**但是因为 ConcurrentHashMap 不允许 value 为 null，所以可以通过 map.get(key) 是否为 null 来判断该 map 中是否包含该 key，这时就没有上面的并发问题了。**

[https_blog.csdn.net_a724888_article_details_80277176]: https://blog.csdn.net/a724888/article/details/80277176
[http_cmsblogs.com_p_176]: http://cmsblogs.com/?p=176
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220326/8f109dc48bd64684bbe77ecf7f5322bd.png
[Link 1]: http://www.cnblogs.com/jasonkoo/articles/2213763.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220326/f4359b7545c54ea2a2c3b13a694676f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20220326/9eb51f8debca4e89aa442ed0b863ba4e.png
[1_HashMap_HashMap]: https://mp.weixin.qq.com/s/MVOqN8mbUtaU0ClUmS4qKw
[2_HashMap_HashMap]: https://mp.weixin.qq.com/s/I6KFAO1n9IQznieUZL95YA
[BST java]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247483930&idx=1&sn=2be1e39990a698a24f54c380a000a193&chksm=eb5121eedc26a8f8ec3f0af997e23fccbd76184cce6cd24a455f5beb7a2f3bc03a1d4cb20751&scene=21#wechat_redirect