HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null，此外，HashMap 中的映射不是有序的。

jdk1.8 之前 HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突（两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用）而存在的（“拉链法”解决冲突）。jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8 ）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用红黑树存储。

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

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

当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于 8 并且数组长度大于 64 时，链表转换为红黑树时，效率也变的更高效。

1、采用的是头部插入法：当计算得到的索引值相同时，即Hash碰撞，引入链表结构解决Hash冲突，新加入的值会插入到旧数据的头部。 链表的时间复杂度是O(n): 当要找的数据是“金莲”，那么在链表上就要遍历3次才能找到，时间复杂度是O(3) HashMap中并不是用取模计算索引位置，而是用位运算 位运算的效率 > 取模

为什么HashMap的容量一定要转成2的指数次幂？ 因为hash值是随机的值，在与数组长度做与运算时，只有两种结果

（1）h & length h = 0001 0101 0111 0010 1110 l = 0000 0000 0000 0001 0000 这种情况得到的结果是要么0，要么16

（2）h & (length - 1) h = 0001 0101 0111 0010 1110 l = 0000 0000 0000 0000 1111 这种情况得到的结果是散列随机的，0-15之间的随机值。从而减少hash碰撞。

2、扩容机制 （1）达到扩容条件后，则扩容为原数组长度的两倍 （2）将原来老的数据移入到新的数组中，在移植的过程中还要进行一次rehash()运算 （3）

这个值是根据空间和时间，通过泊松分布算法得到的一个折中的值。

会在数据迁移的过程中导致链表形成一个环，导致整个HashMap无法使用。 建议在多线程环境下面，使用ConcurrentHashMap

小结：

HashMap 特点：

存储无序的。

键和值位置都可以是 null，但是键位置只能存在一个 null。

键位置是唯一的，是底层的数据结构控制的。

jdk1.8 前数据结构是链表+数组，jdk1.8 之后是链表+数组+红黑树。

阈值（边界值）> 8 并且数组长度大于 64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

示例代码：

输出结果：

分析：

1、当创建 HashMap 集合对象的时候，HashMap 的构造方法并没有创建数组，而是在第一次调用 put 方法时创建一个长度是16 的数组 Node[] table （jdk1.8 之前是 Entry[] table）用来存储键值对数据。

2、假设向哈希表中存储 数据，根据柳岩调用 String 类中重写之后的 hashCode() 方法计算出值，然后结合数组长度采用某种算法计算出向 Node 数组中存储数据的空间的索引值。如果计算出的索引空间没有数据，则直接将存储到数组中。（举例：计算出的索引是 3 ）

3、向哈希表中存储数据 ，假设算出的 hashCode() 方法结合数祖长度计算出的索引值也是3，那么此时数组空间不是 null，此时底层会比较柳岩和刘德华的 hash 值是否一致，如果不一致，则在空间上划出一个结点来存储键值对数据对 ，这种方式称为拉链法。

4、假设向哈希表中存储数据 ，那么首先根据柳岩调用 hashCode() 方法结合数组长度计算出索引肯定是 3，此时比较后存储的数据柳岩和已经存在的数据的 hash 值是否相等，如果 hash 值相等，此时发生哈希碰撞。那么底层会调用柳岩所属类 String 中的 equals() 方法比较两个内容是否相等：

相等：将后添加的数据的 value 覆盖之前的 value。

不相等：继续向下和其他的数据的 key 进行比较，如果都不相等，则划出一个结点存储数据，如果结点长度即链表长度大于阈值 8 并且数组长度大于 64 则将链表变为红黑树。

5、在不断的添加数据的过程中，会涉及到扩容问题，当超出阈值（且要存放的位置非空）时，扩容。默认的扩容方式：扩容为原来容量的 2 倍，并将原有的数据复制过来。

6、综上描述，当位于一个表中的元素较多，即 hash 值相等但是内容不相等的元素较多时，通过 key 值依次查找的效率较低。而 jdk1.8 中，哈希表存储采用数组+链表+红黑树实现，当链表长度（阈值）超过8且当前数组的长度大于64时，将链表转换为红黑树，这样大大减少了查找时间。

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。如下图所示：

1.8 HashMap结构图：

7、jdk1.8 中引入红黑树的进一步原因：

jdk1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。

针对这种情况，jdk1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

8、总结：

说明：

1、HashMap 中 hash 函数是怎么实现的？还有哪些hash函数的实现方式？ 答：对于 key 的 hashCode 做 hash 操作，无符号右移 16 位然后做异或运算。还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移 16 位异或运算效率是最高的。

2、当两个对象的 hashCode 相等时会怎么样？ 答：会产生哈希碰撞。若 key 值内容相同则替换旧的 value，不然连接到链表后面，链表长度超过阈值 8 就转换为红黑树存储。

3、什么是哈希碰撞，如何解决哈希碰撞？ 答：只要两个元素的 key 计算的哈希码值相同就会发生哈希碰撞。jdk8 之前使用链表解决哈希碰撞。jdk8之后使用链表 + 红黑树解决哈希碰撞。

4、如果两个键的 hashCode 相同，如何存储键值对？ 答：通过 equals 比较内容是否相同。相同：则新的 value 覆盖之前的 value。不相同：则将新的键值对添加到哈希表中。

HashMap继承关系如下图所示：

说明：

序列化版本号

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

构造一个具有指定的初始容量和负载因子的 HashMap。

说明：

​ 1、HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。 所以我们重点看 putVal 方法。

​ 2、我们可以看到在 putVal 方法中 key 在这里执行了一下 hash 方法,来看一下 hash 方法是如何实现的。

从上面可以得知 HashMap 是支持 key 为空的，而 HashTable 是直接用 Key 来获取hashCode 所以 key 为空会抛异常。

解读上述hash方法：

我们先研究下 key 的哈希值是如何计算出来的。key 的哈希值是通过上述方法计算出来的。

这个哈希方法首先计算出 key 的 hashCode 赋值给 h，然后与 h 无符号右移 16 位后的二进制进行按位异或得到最后的 hash 值。计算过程如下所示：

在 putVal 函数中使用到了上述 hash 函数计算的哈希值：

计算过程如下所示：

说明：

1、key.hashCode()；返回散列值也就是 hashcode，假设随便生成的一个值。

2、n 表示数组初始化的长度是 16。 3、&（按位与运算）：运算规则：相同的二进制数位上，都是 1 的时候，结果为 1，否则为0。

4、^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为 0，不同为 1。

扩容机制：

​ 1、什么时候才需要扩容

​ 当 HashMap 中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor 的默认值是 0.75。

删除方法就是首先先找到元素的位置，如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除，树小于 6 的时候要转链表。

删除 remove() 方法：

removeNode() 方法：

查找方法，通过元素的 key 找到 value。

代码如下：

get 方法主要调用的是 getNode 方法，代码如下：

小结：

get 方法实现的步骤：

a. 通过 hash 值获取该 key 映射到的桶 b. 桶上的 key 就是要查找的 key，则直接找到并返回 c. 桶上的 key 不是要找的 key，则查看后续的结点：

2、上述红黑树结点调用的是 getTreeNode 方法通过树形结点的 find 方法进行查找：

2、使用 Iterator 迭代器迭代(推荐使用)

3、通过 get 方式（不建议使用）

如果我们确切的知道我们有多少键值对需要存储，那么我们在初始化 HashMap 的时候就应该指定它的容量，以防止 HashMap 自动扩容，影响使用效率。

默认情况下 HashMap 的容量是 16，但是，如果用户通过构造函数指定了一个数字作为容量，那么 Hash 会选择大于该数字的第一个 2 的幂作为容量（3->4、7->8、9->16）。这点我们在上述已经进行过讲解。

关于设置 HashMap 的初始化容量：

我们上面介绍过，HashMap 的扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件就是当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会有可能发生多次扩容，而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表，是非常影响性能的。

但是设置初始化容量，设置的数值不同也会影响性能，那么当我们已知 HashMap 中即将存放的 KV 个数的时候，容量设置成多少为好呢？

关于设置 HashMap 的初始化容量大小：

可以认为，当我们明确知道 HashMap 中元素的个数的时候，把默认容量设置成 initialCapacity/ 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。

而 Jdk 并不会直接拿用户传进来的数字当做默认容量，而是会进行一番运算，最终得到一个 2 的幂。