Java基础知识：HashMap（一）

HashMap

1 HashMap集合简介

• HashMap 基于哈希表的 Map 接口进行实现，是以 key-value 的存储形式进行存放键值对。HashMap 的实现是不同步的，这意味着它不是线程安全的。他的 key、value 都可以为 null。此外，HashMap 中的映射不是有序的。
• JDK 1.8 之前 HashMap 由 数组+链表 组成，数组是 HashMap 的主体，链表则是主要为了解决 哈希冲突（两个对象调用的 hashCode 方法计算的哈希值一致导致计算的数组索引值相同） 而存在的（“拉链法”解决冲突）。
• JDK 1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，“默认为8”）并且当前数组的长度大于 64 时，此时此缩影位置上的所有数据改为使用红黑树存储。

补充

将链表转换成红黑树前会进行一次判断，即使阈值大于 8，但是数组长度小于 64，此时并不会将链表变为红黑树。而是选择进行数组扩容。

为什么这么做

这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下编委红黑树结构，反而会降低效率。因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于 64 时，搜索时间相对要快。 所以综上所述，为了提高性能和减少搜索时间，底层在阈值大于 8 且数组长度大于 64 时，链表才转换为红黑树。具体参考 treeifyBin 方法。 当然虽然增加了红黑树作为底层数据结构，结构变复杂了，但是阈值大于 8 且数组长度大于 64 时，链表转换为红黑树时，效率也变得更高效了。

红黑树

特点

1. HashMap 存储读取是无序的；
2. 键和值都可以是 null，但是键位置只能是一个 null；
3. 键位置是唯一的，底层的数据结构控制键；
4. JDK1.8 以前数据结构是：链表+数组；
5. JDK1.8 以后数据结构式：链表+数组+红黑树；
6. 阈值（边界值）大于 8 并且数组长度大于 64，才将链表转为红黑树，为了提高效率。

2 HashMap底层数据结构

2.1 数据结构概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在的一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行速度和更快的存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构：就是存储数据的一种方式。

2.2 底层数据结构与存储过程

1. HashMap<String,Integer> map = new HashMap<>();
   • 当创建 HashMap集 合对象的时候，在JDK8以前，构造方法创建一个长度为 16 的 Entry[] table 用来存储键值对数据的。
   • 在JDK8以后，不是在HashMap的构造方法底层创建数组了，是在第一次调用put方法时创建的数组，Node[] table 用来存储键值对数据的。
2. 假设项哈希表中存储 小明-5 ，根据 key 调用 String 类中重写之后的 hashCode() 方法计算出值，然后结合 数组长度 并采用 特定算法（例如：对长度取余）计算出向 Node 数组中存储数据的空间的索引值。
   • 如果计算出的索引空间没有数据，则直接将该键值对存储到数组中；
   • 例如：（对照图）计算出的索引是 3，则 “小明-5” 就被放入第 3 个位置；
3. 向哈希表中存储数据 王阿姨-23 ，假设该键值对结合数组长度计算出的索引值也是 6 ，且此时数组空间不为 null，那么底层会比较 王阿姨 和 老王 的 hash 值是否一致。
   • 如果不一致：则在此空间上划出一个节点来存储键值对 王阿姨-23 （见图）；
   • 这种方式就称为：拉链法；
4. 向哈希表中存储数据 小明-18 ，那么其计算出的 索引值 值肯定是 3，且计算出的 hash 值相等，则此时发生 哈希冲突（哈希碰撞） 。此时会调用 小明-5 的 equals 方法对 小明-18 进行比较内容是否相等。
   • 若相等：将之后添加的数据的 value 覆盖之前的 value；
   • 若不相等：那么继续向下和其他数据的 key 进行比较，若都不相等，则再划出一个节点进行存储数据，若相等则继续按照覆盖的方法执行覆盖（见图）；
5. 如果节点长度（链表长度）大于阈值 8 并且数组长度大于 64 则将链表改为红黑树进行存储。

存储示意图

2.2 存储过程面试题

面试题 1 ：哈希表底层采用何种计算方式计算hash值？还有那些算法可以计算出hash值？ 解答： 1. HashMap 底层采用 key 的重写 hashCode() 方法结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引。 2. 还可以采用：平方取中值法、取余法、伪随机数。 3. 10%8=2，11%8=3，其他计算方式效率较低，而位运算效率要高。

面试题 2 ：当两个对象的 hashCode 相等时会发生什么？ 解答： 会发生哈希碰撞，若 key 值内容相同则替换旧的 value ，不然连接到链表的后面，直至链表长度超过阈值 8 且数组长度超过 64 时再采用红黑树存储。

面试题 3 ：何时会发生哈希碰撞，什么是哈希碰撞，如何解决哈希碰撞？ 解答： 只要两个元素的 key 经过计算后得到的 hash 值相同就会发生碰撞。JSDK8 以前采用链表来解决哈希碰撞。JSDK8 以后采用链表+红黑树来解决哈希碰撞。

面试题 4 ：如果两个键的 hashCode 相同，如何存储键值对？ 解答： hashCode 相同，通过 equals 比较内容是否相同并递归地进行如下的比较操作。 相同：将新的 value 覆盖旧的 value。 不相同：将新的键值对添加到哈希表中。

2.3 扩容与小结

1. 在不断的添加数据的过程中，会涉及到扩容问题。当超出临界值（且要存放的位置）时，进行扩容操作。
   • 默认的扩容方式：扩容为原来容量的 2 倍，并将原有的数据复制过来。
   • 在 Java 中数组的长度时固定的，所以需要构造新的数组对象来存储原来的数据。
2. 综上所述，当位于一个链表中的元素较多时（即：hash 值相等但是内容不相等的元素较多时）通过 key 值依次查找的效率较低。而 JDK1.8 中，哈希表存储采用 数组+链表+红黑树 实现，当链表长度（阈值）超过 8 且数组长度超过 64 时，转为红黑树存储法，大大减少了查找时间。

2.4 为什么使用红黑树

问题描述：针对传统 hashMap 的缺点，JDK1.8 为什么引入红黑树？这样结构不是更麻烦吗？为何阈值大于 8 就要换成红黑树？

• JDK1.8 以前的方法，即使哈希函数取值再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存档到同一个桶中时，这个桶下就有一条长链表，这时候 HashMap 就相当于一个单链表，加入单链表有 n 个元素，遍历的时间复杂度就是 O(n) 失去了其优势。
• 针对这种情况，JDK1.8 中引入了红黑树（红黑树的查找时间复杂度为：O(logn)）来优化这个问题，当链表长度很小的时候，即使遍历，速度也很快。一旦链表长度不断被增加，其查询速度对性能一定会有影响，所以采用红黑树算法。
• 阈值为什么取 8 ，见后面源码解析。

说明：

1. size 表示 HashMap 中 k-v的实时数量 ，注意这个不等于数组长度。
2. threshold（临界值）= capacity（容量）* loadFactor（加载因子）。
3. 临界值是当前已占用数组长度的最大值。size 超过这个临界值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的两倍。

3 HashMap继承关系

HashMap继承关系如下：

继承关系

• Cloneable 空接口，表示可以克隆。创建并返回 HashMap 对象的一个副本。
• Serializable 序列化接口。属于标记性接口。HashMap 对象可以背序列化也可以被反序列化。
• AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作。

补充问题： 通过上述继承关系我们发现一个问题。HashMap 已经继承了 AbstractMap 而 AbstractMap 类实现了 Map 接口，那 HashMap 为什么还要再继续实现 Map 接口呢？同样在 ArrayList 中与在 LinkedList 中都是这样的结构的设计思路是什么？ 解答： 据 java 集合框架创始人 Josh Bloch 描述，这样写是一个失误。在 java 集合框架中，类似这样的写法很多，最开始写 java 集合框架的时候，他认为这样写在某些地方可能是有价值的，直到他意识到错了。很显然，JDK 的维护者，后来不认为这个小小的失误值得去修改，所以就这样保留下来了。

4 HashMap集合类成员

4.1 成员变量

4.1.1 序列化版本号

private static final long serialVersionUID = 362498820763181265L;

4.1.2 集合的初始化容量（必须是2的n次幂）

//默认的厨师容量是16 -- 1 << 4 相当于 1*2^4 -- 1*16
static final int DEFAULE_INITAL_CAPACITY = 1 << 4;

问题： 为什么必须是 2 的 n 次幂？如果输入值是 10 会怎么样？ 解答： HashMap 构造方法还可以指定集合的初始化容量大小：

HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子（0.75）的空 HashMap。

综上所述，我们已经知道，当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，要尽量减少 哈希碰撞，就是要尽量吧数据分配均匀，每个链表长度大致相同。这个实现，就是“把数据存到哪个链表中”的算法。

为什么必须是 2 的 n 次幂 该算法的实际就是取模，hash%length ，计算机中直接取余的笑料并不如位运算。所以源码中作乐优化，使用了 hash%(length-1) ，而实际上 hash%length 的前提条件就是 length 必须是 2 的 n 次幂。

为什么能均匀分布减少哈希碰撞 2 的 n 次幂实际就是 1 后面 n 个 0 ，2 的 n 次方 - 1 实际就是 n 个 1。

举例说明： 按位与运算：相同的二进制数位上，都是 1 的时候，结果为 1，否则为 0。

"如果是 2 的 n 次幂"
例如长度为 8 的时候, 3&(8-1)=3 2%(8-1)=2 , 不同位置上不碰撞。
例如长度 length 为 8 的时候, 8 是 2 的 3 次幂，二进制是：00001000
00001000 → 8
-      1
--------
00000111 → 7

如下所示：

hash & (length - 1)
3 & (8 - 1) = 3
  00000011 → 3 hash
& 00000111 → 7 length-1
----------------------
  00000011 → 3 数组下标

hash & (length - 1)
2 & (8 - 1) = 2
  00000010 → 2 hash
  00000111 → 7 length-1
----------------------
  00000010 → 2 数组下标

说明：上述计算结果是不同位置上的，不发生碰撞。

"如果不是 2 的 n 次幂"
例如长度为 9 的时候, 3&(9-1)=0 2&(9-1)=0 , 都在 0 位置上发生了哈希碰撞。
例如长度 length 为 9 的时候, 9 不是 2 的 n 次幂, 二进制是：00001001
00001001 → 9
-      1
--------
00001000 → 8

如下所示：

hash & (length - 1)
3 & (9 - 1) = 0
  00000011 → 3 hash
& 00001000 → 8 length-1
----------------------
  00000000 → 0 数组下标

hash & (length - 1)
2 & (9 - 1) = 2
  00000010 → 2 hash
& 00001000 → 8 length-1
----------------------
  00000000 → 0 数组下标

说明：上述计算结果都在 0 位置上，发生了哈希碰撞。

注意：当然，如果不考虑效率，直接取余即可（就不需要要求长度必须是 2 的 n 次方了）

4.1.3 小结

1. 由上面可以看出，当我们根据 key 的 hash 确定其在数组的位置时，如果 n 为 2 的幂次方，可能数组数组的一些位置永远不会插入数据，浪费数组的空间，增大 哈希冲突。
2. 另一方面，一般我们可能会通过 % 取余来确定位置，这样也可以，只不过会降低性能。而且，当 n 为 2 的幂次方时满足：hash%(length-1) == hash%length
3. 因此，HashMap 容量为 2 的幂次方的原因，就是为了数据的均匀分布，减少 哈希冲突。
4. 如果创建 HashMap 对象时，输入的数组长度不是 2 的幂次方，HashMap 会通过不断的位运算和或运算得到距离其最近的 2 的幂次方的数。 具体代码如下：

//创建HashMap集合对象，指定数组长度为10
HashMap map = new HashMap(10);
public HashMap(int initalCapacity) {
	this(initalCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initalCapacity, float loadFactor) {
	//initalCapacity = 10
	if(initalCapacity < 0)
		throw new IllegalArgumentException("Illegal inital capacity: " + initalCapacity);
	if(initalCapacity > MAXIMUN_CAPACITY)
		initalCapacity = MAXIMUN_CAPACITY;
	if(loadFactor <= 0 || FLoat.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

	this.loadFactor = loadFactor;
	this.threshold = tableSizeFor(initalCapacity);
	//initalCapacity = 10
}
static final int tableSizeFor(int cap) {
	//int cap = 10
	int n = cap - 1;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return (n < 0) ? 1 : (n >= MAXIMUN_CAPACITY) ? MAXIMUN_CAPACITY : n + 1;
}

代码解析：

由此可以看出，当在实例化 HashMap 实例时，如果给定来 initalCapacity（假设是10）由于 HashMap 的 capacity 必须都是 2 的幂指数 ，因此这个方法用于找到大于等于 initalCapacity 的最小 2 指数（如果已经是，则直接返回）。

算法分析：

1. 对 cap 减 1 的操作：为了防止 cap 已经是 2 的幂次方。如果 cap 已经是 2 的幂次方，有没有执行 - 1 的操作，则执行完后面的无符号右移草组织好，返回的 capacity 将是这个 cap 的 2 倍。
2. 如果 n 这时为 0（经过 cap - 1 后），则经过后面几次无符号右移操作后依然是 0，最后返回的 capacity 是 1（只讨论 n 不等于 0 的情况）。
3. |（按位或运算）的运算规则是：相同的二进制位数上，都是 0 的时候，结果为 0，否则为 1。

第一次右移：

int n = cap - 1; // cap = 10 n = 9
n |= n >>> 1;
  00000000 00000000 00000000 00001001 → 9 n
| 00000000 00000000 00000000 00000100 → 4 n>>>1
-------------------------------------
  00000000 00000000 00000000 00001101 → 13 |=

由于 n 不等于 0，则 n 的二进制表示中总会有一个 bit 为 1，这是考虑最高位的 1。通过无符号右移 1 位，则将最高位的 1 右移了 1 位，再做或操作，使得 n 的二进制表示中与最高位的 1 紧邻的右边一位也为 1 。

第二次右移：

n |= n >>> 2;
  00000000 00000000 00000000 00001101 → 13 n
| 00000000 00000000 00000000 00000011 → 3 n>>>2
-------------------------------------
  00000000 00000000 00000000 00001111 → 15 |=

注意，这个 n 已经经过了 n |= n >>> 1; 的操作。

第三次右移：

n |= n >>> 4;
  00000000 00000000 00000000 00001111 → 15 n
| 00000000 00000000 00000000 00000000 → 0 n>>>4
-------------------------------------
  00000000 00000000 00000000 00001111 → 15 |=

以此类推。 注意，容量最大也就是 32 bit的正数，因此最后 n |= n >>> 16; 最多也就 32 个 1 （已经是负数。在执行 tableSizeFor 之前，对 initalCapacity 作了判断，如果大于 MAXIMUN_CAPACITY (2 ^ 30) 会执行位运算，所以这里面的位运算操作之后，最大为 30 个 1，不会大于等于 MAXIMUN_CAPACITY。30个 1，加 1 之后得到 2 ^ 30）

经过所有按位或运算之后将值赋给 threshold 。

4.2 红黑树转换

问题：为什么 Map 桶中节点个数超过 8 才转为红黑树结构？

8 这个阈值定义在 HashMap 中，针对这个成员变量，在源码的注释中只说明了 8 是 bin（bucket::桶）从链表转为树的阈值，但没有说明为什么是 8。 在 HashMap 对象中的说明为：

因为树节点的大小约为普通节点的 2 倍，所以我们只在箱子包含足够的节点时才使用树节点（参考 TREEIFY_THRESHOLD）。当它们变得太小（由于删除或调整大小）时，就会被转换会普通的桶。在使用分布良好的用户 hashcode 时，很少使用树箱。理想情况下，在随机哈希码下，箱子中节点的频率服从泊松分布。 (http://en.wikipedia.org/wiki/Poisson_distribution) 默认阈值为 0.75，平均参数约为 0.5，尽管由于调整粒度的差异很大，忽略方差，列表大小 k 的预期出现次数为 (exp(-0.5) * pow(0.5,k) / factorial(k))

4.2.1 链表节点泊松分布：

TreeNodes 占用空间是普通 Nodes 的两倍，所以只有当 bin 包含足够多的节点时才会转换成 TreeNodes，而“是否足够多”就是有 TREEIFY_THRESHOLD 的值决定的。当 bin 中节点数变少时，又会转成普通的 bin。并且查看源码可以发现，链表长度达到 8 就转成红黑树，长度降为 6 就传承普通 bin。

这样就解释了为什么不是一开始就将其转换为 TreeNodes，而是需要一定节点数才能转换为 TreeNodes，说白就是权衡了空间与时间。

当 hashCode 离散性很好的时候，树型 bin 用到的概率非常小，因为数据均匀分布在每个 bin 中，几乎不会有 bin 中链表的长度能够达到阈值。但是在随机 hashCode 下，离散性会变差，然而 JDK 又不能阻止用户实现这种不好的 hash 算法，因此就可能导致不均匀的数据分布。

不过理想情况下随机 hashCode 算法下所有 bin 中节点的分布频率会遵循泊松分布，我们可以看到，一个 bin 中链表长度达到 8 个元素的概率仅为 0.00000006，几乎是不可能事件，所以，之所以选择 8 ，不是随便决定的，而是根据概率统计决定的。

4.2.2 小结

4.2.2.1 泊松分布

Poisson分布（泊松分布），是一种统计与概率学里常见的离散[概率分布]。 泊松分布的概率函数为：

P(X=k)=λkk!e−λ,k=0,1,...P(X=k)=\frac{\lambda^k}{k!}e^{-\lambda},k=0,1,... P(X=k)=k!λk​e−λ,k=0,1,...

泊松分布的参数 λ\lambdaλ 是单位时间（或单位面积）内随机事件的平均发生次数。泊松分布适合描述单位时间内随机事件的发生次数。

4.2.2.2 参考解释

红黑树的平均查找长度是 log(n)log(n)log(n) ，如果长度为 8 ，平均查找长度为 log(8)=3log(8)=3log(8)=3 ，链表的平均查找长度为 n2\frac{n}{2}2n​ ，当长度为 8 时，平均查找长度为 82=4\frac{8}{2}=428​=4 ，这才有转换成树的必要，链表长度如果是小于等于 6，62=3\frac{6}{2}=326​=3 ，而 log(6)=2.6log(6)=2.6log(6)=2.6 ，虽然速度也很快，但是转化为树结构和生成树的时间并不会很短。

4.3 红黑树转回链表

//当桶(bucket bin)上的节点数小于这个值时树转为链表
static final int UNTREEIFY_THRESHOLD = 6;

当 Map 里面的数量超过这个值时，表中的桶才能树形化，否则桶内元素太多时会发生扩容，而不是树形化。为了避免扩容操作、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD(8)

//桶中结构转化为红黑树对应的数组长度的最小值
static final int MIN_FREEIFY_CAPACITY = 64;

4.4 table 用来初始化（重点）

重难点，必须是 2 的 n 次幂

//存储元素的数组
transient Node<K,V>[] table;

table 在JDK1.8 中我们了解到 HashMap 是由数组+链表+红黑树组成的结构，其中 table 就是 HashMap 中的数组，jdk8 之前数组类型是 Entry<K,V> 类型。从 JDK1.8 之后是 Node<K,V> 类型。只是换了个名字，但都实现了同样的接口：Map.Entry<K,V> 。负责存储键值对数据。

4.5 存放缓存

//存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;

4.6 存放元素个数（重点）

//存放元素个数，注意这个不等于数组的长度
transient int size;

size 为 HashMap 中 key-value 的实时数量，不是数组 table 的长度。

4.7 记录HashMap修改次数

//每次扩容和更改map机构的计数器
transient int modCount;

4.8 调整下一次容量大小

//临界值 当实际大小（容量 * 负载因子）超过临界值时，会进行扩容
int threshold;

4.9 哈希表的加载因子（重点）

//加载因子
final float loadFactor;

说明：

1. loadFactor 加载因子，是用来衡量 HashMap 满载的程度，表示 HashMap 的疏密程度，影响 hash 操作到同一个数组位置的概率， 计算 HashMap 的实时加载因子的方法为：size/capacity ，而不是占用桶的数量去除以 capacity 。capacity 是桶的数量，也就是 table 的长度 length 。
2. loadFactor 太大导致查找元素效率低下，大小导致数组的利用率偏低，存放的数据会很分散。loadFactor 的默认值为 0.75 是官方给出的一个比较好的临界值。
3. 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容。而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容次数，可以通过创建 HashMap 集合对象时指定初始容量来避免。
4. 同时在 HashMap 的构造器中可以定制 loadFactor。

//构造方法：
HashMap(int initalCapacity, float loadFactor)
//构造一个带制定初始容量和加载因子的空 HashMap

4.9.1 为什么加载因子设置为 0.75 初始化临界值是12

loadFactor 越趋近于 1 ，那么数组中存放的数据（entry）也就越多、越密集，也就是会让链表的长度增加。反之成立。

如果希望链表尽可能少一些。要提前扩容，有的数组空间有可能一直没有存储数据。加载因子要尽可能地小一些。

举例：

1. 加载因子是 0.4 。那么 16 * 0.4 = 6 如果数组中满 6 个空间就会扩容会导致数组利用率非常低。
2. 加载因子是 0.9 。那么 16 * 0.9 = 14 这样会导致链表过多。导致查找元素效率降低。
3. threshold 计算公式： capacity（数组长度默认 16）* loadFactor（负载因子默认 0.75）。这个值时当前已占用数组长度的最大值。当 Size >= threshold 的时候，那么就要考虑数组的 resize（扩容）也就是说，这个的意思就是 衡量数组是否需要扩容的一个标准 。扩容后的 HashMap 容量是之前容量的两倍。

4.10 构造方法

HashMap 中重要的构造方法如下：

4.10.1 空构造

构造默认的初始容量为 16，默认负载因子为 0.75

public HashMap() {
	//将默认的加载因子0.75赋值给loadFactor，并没有创建数组
	this.loadFactor = DEFAULT_LOAD_FACTOR;
}

4.10.2 🈯️初始容量和负载因子

//指定"容量大小"的构造函数
public HashMap(int initalCapacity) {
	this(initalCapacity, DEFAULT_LOAD_FACTOR);
}

/*
	指定"容量大小"和"加载因子"的构造函数
	initalCapacity：指定的容量
	loadFactor：指定的加载因子
 */
public HashMap(int initalCapacity, float loadFactor) {
	//判断初始化容量initalCapacity是否小于0
	if(initalCapacity < 0)
		//如果小于0，则抛出非法的参数异常
		throw new IllegalArgumentException("Illegal inital capacity: " + initalCapacity);
	//判断初始化容量initalCapacity是否大于最大容量(2^30)
	if(initalCapacity > MAXIMUN_CAPACITY)
		//如果超过回滚容量大小
		initalCapacity = MAXIMUN_CAPACITY;
	//判断负载因子loadFactor是否小于等于0或者是否为一个数值
	if(loadFactor <= 0 || FLoat.isNaN(loadFactor))
	//如果满足上述条件之一则跑出异常
		throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
	//将特定的加载因子赋值给HashMap成员变量的负载因子loadFactor
	this.loadFactor = loadFactor;
	//调用tableSizeFor()方法对初始化容量initalCapacity进行调整与判断
	this.threshold = tableSizeFor(initalCapacity);
}
static final int tableSizeFor(int cap) {
	//int cap = 10
	int n = cap - 1;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return (n < 0) ? 1 : (n >= MAXIMUN_CAPACITY) ? MAXIMUN_CAPACITY : n + 1;
}

说明： 对于 this.threshold = tableSizeFor(initalCapacity); 的解释：

tableSizeFor(initalCapacity) 判断制定的初始化容量是否为 2 的 n 次幂，如果不是那么会变为比指定初始化容量稍小一点的 2 的 n 次幂。上文已提及过。 但是注意，在 tableSizeFor 方法体内部将计算后的数据返回给调用这里了，并且直接复制给 threshold 边界值。 但很多人会认为应该这样写： this.threshold = tableSizeFor(initalCapacity) * this.loadFactor 但是，在 jdk8 以后的构造方法中，并没有对 table 这个成员变量进行初始化，table 的初始化被推迟到了 put 方法中，在 put 方法中会对 threshold 重新计算，put 方法的具体实现见下文。

4.10.3 包含另一个"Map"构造

//构造一个映射关系与指定 Map 相同的新的 HashMap
//利用协变将泛型向上转变
public HashMap(Map<? extends K, ? extends V> m) {
	//负载因子loadFactor编委默认的负载因子0.75
	this.loadFactor = DEFAULT_LOAD_FACTOR;
	putMapEntries(m, false);
}

最后调用 putMapEntries() 方法：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
	//获取参数集合的长度
	int s = m.size();
	if(s > 0) {
		//判断参数集合长度是否大于0
		if(table == null）{
			//判断table是否已经初始化 pre-size
			//未初始化，s为m的实际元素个数
			float ft = ((float)s / loadFactor) + 1.0F;
			int t = ((ft < (float)MAXIMUN_CAPACITY) ? (int)ft : MAXIUM_CAPACITY);
			//计算得到的t大于阈值，则初始化阈值
			if(t > threshold)
				threshold = tableSizeFor(t);
		} else if(s > threshold)
			//已初始化，并且m元素的个数大于阈值，进行扩容处理
			resize();
		//将m中的所有元素添加至HashMap中
		for(Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
			K key = e.getKey();
			V value = e.getValue();
			putVal(hash(key), key, value, false, evict);
		}
	}
}