说一下HashMap的底层原理

本文是常见的HashMap原理面试题的总结，文章清晰易懂且详细

部分内容来源：JavaGuide

说一下HashMap的实现原理

JDK1.7版本

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。

如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，

链表的查询时间是O(n)，所以冲突很严重时一个索引上的链表非常长，查询效率就很低了

JDK1.8版本优化

所以在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过8的时候就转换数据结构，不再使用链表存储，而是使用红黑树

查找时使用红黑树时间复杂度为O（log n），可以提高查询性能

但是在数量较少时即数量小于6时，会将红黑树转换回链表

为什么我们不直接使用红黑树代替链表？

红黑树的实现比链表复杂得多，涉及节点的旋转、颜色调整等操作。

对于少量数据，红黑树的性能优势不明显，反而增加了实现的复杂性和运行时的开销

这就是为啥我们数量过8要变成红黑树，数量小于6要回退成链表

说一下HashMap的底层实现-红黑树

JDK1.7之前--拉链法

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可

我们的Map是由数组和链表组合成的列表散列

遇到Hash冲突的时候，如果我们的Key不相同，我们往链表里面加就行了

如果Key相同，那么就覆盖原来的位置。

存入逻辑：计算Hash值，找到桶的位置，遍历链表，存放键值对

（链表里存放的是一个键值对，我们Hash冲突时，用Hash值找到桶的位置，再遍历链表，通过key找到我们对应的键值对）

JDK1.8之后--红黑树

我们的数组长度小于64，我们的链表长度在超过阈值(默认是8），会优先选择数组扩容

数组扩容后我们的Map就会对现有的所有键值对重新计算Hash，然后放入到我们的数组

当我们的长度大于等于64的时候，我们的链表就变成红黑树

优先数组扩容，数组长度到64，我们的链表再变成红黑树

常见的Hash冲突解决方法有哪些

1.链接法（拉链法）

使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。

2.开放寻址法

在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。

3.再哈希法（Rehashing）

当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。

4.哈希桶扩容

当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap是线程安全的吗（头插法） 

hashmap不是线程安全的，hashmap在多线程会存在下面的问题：

1.扩容策略导致的线程不安全（头插法的死链问题）

2.多线程下的put方法使用不当导致的线程不安全,导致前一个key被后一个key覆盖

JDK1.7（头插法）

JDK 1.7 HashMap 采用数组 + 链表的数据结构，多线程背景下，在数组扩容的时候，存在 Entry 链死循环和数据丢失的问题。

数组进行扩容的时候，链表使用的是头插法

• 线程A和线程B同时对 HashMap 进行扩容操作，重新计算哈希值并重新分配数组。
• 由于没有同步机制，线程A和线程B可能会同时操作同一个链表节点，导致链表节点的 next 引用指向自身或形成循环链表

我们扩容的时候采用的是头插法

例如我们链表的顺序从上往下是A,B

那我们扩容的时候就从上往下遍历，然后依次往头节点插入，也就是从A,B变成了B,A

我们单线程扩容肯定没问题，但是我们多线程的情况下就会出问题了

例如我们有两个线程进行扩容

线程A记录信息，e是A，next（）是B，此时发生了线程的上下文切换

线程B进行扩容，线程B已经扩容结束，把我们的链的顺序变成了B,A

即使此时顺序变了，但我们此时线程A记录的信息还没变

我们遍历e，把A插入头，然后e变成B，一般来说此时我们的B的next应该为空，但是我们线程B弄好了，所以我们的B的next是为A

我们遍历B，然后B插入头节点，此时我们的e继续往下一个遍历，我们的B的next是为A，所以我们的还要再把B的下一个节点A插入到我们的头，所以就造成了我么的呢A,B,A现象

我们的A节点的信息是一样的，因为都是同一个地址，所以可以省略一个A

我们的A节点的信息指向B，也就是我们的末尾节点指向了上一个节点造成了循环链表，直接形成了死链

JDK1.8

JDK 1.8 HashMap 采用数组 + 链表 + 红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，也就是从头插法->尾插法

解决了 Entry 链死循环和数据丢失问题。

但是多线程背景下，put 方法存在数据覆盖的问题。

保证线程安全的方法

如果要保证线程安全，可以通过这些方法来保证：

多线程环境下可以使用Collections.synchronizedMap同步加锁的方式，还可以使用HashTable，但是同步的方式显然性能不高，而ConcurrentHashMap更适合高并发场景使用。

ConcurrentHashMap在JDK1.7和1.8的版本改动比较大，1.7使用Segment+HashEntry分段的方式实现，1.8则抛弃了Segment，改为使用CAS+synchronized+Node实现，同时也加入了红黑树，避免链表过长导致性能的问。

Hashmap的扩容长度为什么是2的幂次方 

扩容

主要是扩容后的重新分配的均匀性

例如我们的16扩容到32，我们有一半元素留在原地，有一半元素移动

例如，我们13移动到13+16，因为我们扩容了16

高效的哈希值计算

HashMap 通过哈希函数将键（key）映射到数组的索引位置。为了将哈希值均匀分布到数组中，通常需要对哈希值取模运算（hash % capacity）。当容量为 2 的幂次方时，取模运算可以优化为位运算，效率更高。

位运算为什么效率高？

逻辑与（&）、逻辑或（|）、逻辑非（~）、左移（<<）、右移（>>）等操作，这些指令可以直接在硬件层面高效执行，比取模运算效率高

优化原理

取模运算：hash % capacity

位运算优化：hash & (capacity - 1)

• 当 capacity 是 2 的幂次方时，capacity - 1 的二进制形式是全 1（例如，16 - 1 = 15，二进制为 1111）。
• 通过 hash & (capacity - 1)，可以直接截取哈希值的低位，效果等同于取模运算

均匀分布哈希值-减少哈希冲突

当容量为 2 的幂次方时，hash & (capacity - 1) 能够更好地利用哈希值的所有位，从而减少哈希冲突的概率。

• 如果容量不是 2 的幂次方，某些索引位置可能永远不会被使用，导致哈希分布不均匀。
• 例如，如果容量为 10（非 2 的幂次方），hash % 10 的结果只会依赖于哈希值的低 4 位，而高位的哈希信息被浪费

HashMap调用get（）方法一定安全吗 

空指针异常（NullPointerException）

如果你尝试用 null 作为键调用 get（） 方法，而 HashMap 没有被初始化（即为 null），那么会抛出空指针异常。

不过，如果 HashMap 已经初始化使用 null 作为键是允许的，因为 HashMap 支持 null 键。

线程安全

HashMap 本身不是线程安全的。如果在多线程环境中，没有适当的同步措施，同时对 HashMap 进行读写操作可能会导致不可预测的行为。

例如，在一个线程中调用 get 方法读取数据，而另一个线程同时修改了结构（如增加或删除元素），可能会导致读取操作得到错误的结果或抛出 ConcurrentModificationException。如果需要在多线程环境中使用类似 HashMap 的数据结构，可以考虑使用 ConcurrentHashMap。

说一下HashMap的懒加载机制 

桶的初始化

当你创建一个 HashMap 对象时，它并不会立即初始化所有的桶（数组）。例如，默认情况下，HashMap 会创建一个长度为 16 的数组，但这些桶最初的状态是空的。

这意味着 HashMap 不会为每个桶分配内存，直到需要存储数据时，相应的桶才会被使用

HashMap的动态扩容

当向 HashMap 添加键值对时，如果当前的元素数量超过了负载因子（通常是 0.75），HashMap 会进行扩容。

在扩容时，HashMap 会创建一个新的、更大的数组，并将现有的元素重新哈希到新的桶中。这种扩容是在实际需要时才发生的，因此称为懒加载

链表与红黑树

在 HashMap 中，当某个桶中的元素数量超过一定阈值（通常是8），会将该桶中的链表转换为红黑树，以提高查找效率。

这一转换也是在需要时才进行的

HashMap和HashTable的区别

1.线程是否安全：HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；

2.效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；

3.对 Null key 和 Null value 的支持：

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；

Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException

4.初始容量大小和每次扩充容量大小的不同：

① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。

5.底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。Hashtable 没有这样的机制。

6.哈希函数的实现：HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 Hashtable 直接使用键的 hashCode() 值

HashMap和HashSet的区别

HashSet的底层就是由HashMap实现的

HashMap和TreeMap的区别 

连接了sortedMap接口，增强了排序功能

连接了Navigable接口，增强了搜索功能

NavigableMap 接口提供了丰富的方法来探索和操作键值对:

1. 定向搜索: ceilingEntry(), floorEntry(), higherEntry()和 lowerEntry() 等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对。
2. 子集操作: subMap(), headMap()和 tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。
3. 逆序视图:descendingMap() 方法返回一个逆序的 NavigableMap 视图，使得可以反向迭代整个 TreeMap。
4. 边界操作: firstEntry(), lastEntry(), pollFirstEntry()和 pollLastEntry() 等方法可以方便地访问和移除元素。

这些方法都是基于红黑树数据结构的属性实现的，红黑树保持平衡状态，从而保证了搜索操作的时间复杂度为 O(log n)，这让 TreeMap 成为了处理有序集合搜索问题的强大工具

HashSet的put（）方法 

在 JDK1.8 中，实际上无论HashSet中是否已经存在了某元素，

HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素