目录
哈希表是什么，常见哈希表及其区别
哈希函数、哈希碰撞（哈希冲突解决方法：两个）
hashmap底层实现（发生哈希冲突、是线程安全的吗、和concurrentHashMap的区别、和hashtable的区别、可以存null值吗、为什么、锁机制）
一、哈希表是什么
哈希表是一种基于数组+哈希函数+冲突策略实现的键值对存储结构。插入、查找、删除操作都接近O(1)时间复杂度。
JVM视角：哈希表存在哪里？
在java中，一般new出来的哈希表对象，是分配在堆内存里的。哈希表对象本身在堆上，内部的数据结构（如数组Node[]）也是对象，也在堆上，每个节点（next、key、value、hash）本身也是堆上的对象。
【用在哪里】
【底层原理简述】
在堆内存上，哈希表本质是一个数组，数组的每一个元素称为一个桶（bucket）。
插入元素时，会先通过哈希函数（通常调用key.hashCode()方法）计算出key的哈希值，再通过哈希值取模（或位运算）映射到数组的下标（即桶的位置）
若这个位置没有元素，就直接存储。
若冲突了，需要通过冲突解决策略处理，比如拉链法（链地址法）、开放地址法（线性探测、二次探测）。
取元素时也是一样：用key计算hash，找对应值，桶里链表或树查找。
【更具体看】
计算key的hashCode-->哈希表把hashCode转成数组下标（桶的位置），这里会进行一次加工（避免分布太集中，提高随机性）。
// JDK8源码大致流程
int hash = hash(key.hashCode()); // 进一步扰动一下hashCode
int index = (table.length - 1) & hash; // 取模，定位到桶（数组下标），这种方法比% 求余要快得多。
二、不同哈希表
类名是否线程安全底层结构特点适用场景
HashMap
❌ 非线程安全
数组 + 链表/红黑树（Java 8+）
查询快，允许null键null值，负载因子0.75
单线程场景，最常用
Hashtable
✅ 线程安全（方法加锁）
数组 + 链表
每个方法都是同步的（synchronized），效率低
早期多线程用，现在少用
ConcurrentHashMap
✅ 高效线程安全
分段锁（JDK7），CAS+红黑树（JDK8）
线程安全，性能高，允许并发读写
高并发场景
LinkedHashMap
❌ 非线程安全
HashMap + 双向链表（维护插入顺序）
可以保持元素插入顺序
有顺序要求时
TreeMap
❌ 非线程安全
红黑树（有序）
自动按 key 排序（自然顺序或自定义比较器）
需要排序时
2.1 HashSet和HashMap的区别
HashSet只关心元素是否存在，不关心键值对。HashMap存储键值对，每个键都唯一。
HashSet实际上是基于HashMap实现的，只使用了键，将值设为固定的常量。
两个都允许存储null。
HashSet的性能收到哈希分布和哈希冲突的影响，但由于只存储键，通常比HashMap的性能稍好。
2.2 HashTable和HashMap的区别
HashTable是同步的（线程安全），在每个方法上添加同步关键字，性能较低。HashMap不是线程安全的，性能较高。
HashTable不允许存null。
HashTable的初始容量和加载因子是固定的。HashMap允许通过构造方法设置初始容量和加载因子，以便更好调整性能。
2.3 ConcurrentHashMap和HashMap的区别
线程安全性区别。同步机制。
HashMap若在迭代过程中有其他线程对其进行修改，可能抛出ConcurrentModificationException异常。而前者允许在迭代时并发的插入和删除操作，不会抛异常。但它不保证迭代器的顺序，因为不同的段可能会以不同的顺序完成操作。
前者在Java 8之后版本引入了构造方法设置初始容量、负载因子和并发级别。
低并发情况下，后者性能比前者稍好。在高并发情况下，前者性能通常更好。
三、哈希函数、哈希冲突
3.1 链地址法【java中的HashMap用这个】
在数组的每个位置维护一个链表，当发生冲突时，新的元素会被添加到链表的尾部。
优点：哈希表负载因子可以超过1，冲突元素统一管理。不需要频繁扩容，插入简单，不要移动大量元素。支持高效删除操作。
缺点：链表太长时，查询效率退化为O(N）。可以自定义或优化哈希函数，降低冲突率。
适合场景：适合元素数量不确定、且频繁插入删除的场景。
3.2 线性探测法
当发生冲突时，根据某种探测算法在哈希表中寻找下一个空闲位置来存储元素，按照一定步长（通常是1）向后探查下一个槽位，顺序为 (h(x)+1) mod M，(h(x)+2) mod M，依次类推。直到找到空槽为止。
插入：先用哈希函数计算初始位置h（x），若该位置被占用了则向后找第一个空槽，直到找到为止。
查找：计算初始化位置h（x），若当前元素是目标元素，则返回；否则按插入时的探测顺序继续查找，直到找到。
删除：不能直接简单标记为空，一般采用懒惰删除（标记为已删除），查找时继续跳过，插入时可复用。
优点：连续内存访问，结构简单，占用内存少（不用建链表）（你找座位，不需要拿个笔记本记录空座，直接扫一眼往后走，看到空位就坐下，很快！）
缺点：慢；负载因子不能太高；删除要小心。
四、常见的哈希表
4.1 HashMap（最常用）
底层结构：数组+链表+红黑树。每个桶里是一个链表（当冲突少时）或者红黑树（当冲突多时）。
JDK8之后优化：当同一个桶中的链表长度超过8，并且数组长度大于64时，会把链表转换成红黑树（O(n)变O(logn)查询加速）。
为什么数组长度要大于64？——如果数组长度不够大，不管哈希函数多优秀，冲突概率都非常高！这时候根源是：数组太小，桶数量太少，不是链表太慢的原因。此时最好的优化方法是扩容数组，让更多的元素均匀分散到更多桶中，从源头减少冲突，而不是过早引入红黑树增加维护开销。
为什么HashMap是非线程安全的？
若两个线程同时put不同的key到同一个桶，线程A读到table[x]是null，准备插入；线程B也读到table[x]是null，也准备插入。两个线程同时插入，最后只有一个节点真正保存在了桶里，另一个数据就丢失了。
HashMap的get方法本身也是没有加锁的，若正在扩容或插入新元素，get到的是中间状态的数据，可能：查不到本来已经插入的元素；查到了一个逻辑上已经不存在的元素。
若多个线程同时触发扩容条件，搬运时链表的next指针被线程A\B互相篡改，出现链表环，HashMap的某个桶变成无限循环，程序卡死、CPU飙升！！
如何实现线程安全?
//1. 方法一：对hashMap加锁/对map的操作加锁Map
public V get(Object key) { //使用时
synchronized (this) {
return map.get(key);
}
}
public V put(K key, V value) {
synchronized (this) {
return map.put(key, value);
}
}
//优点：简单
//缺点：粒度粗，每次读写都加锁，性能低，多线程并发性差
//2. 使用concurrentHashMap
Map
// ConcurrentHashMap是专门为“多线程环境”设计的一个线程安全的哈希表。它能让很多线程同时进行查找和插入，且性能很高。//JDK1.7之前：分段锁：整个表被划分成很多小块，每一块维护自己的数据并有自己的锁。优点是比整个表都加锁要快得多；缺点是锁的粒度还是不够细。//JDK1.8之后：//- 读：不加锁。用volatile保证写现场修改了table引用后，所有读线程能立刻看到最新的table，并且且读写顺序正确，避免读取到扩容中途或损坏的结构。//- 写：桶是空的（用CAS原子操作尝试放，根据版本号，性能高）；桶不空（若是链表，加锁synchronized整个桶头节点，顺着链表插入新节点；若是红黑树，也加锁桶头节点，// 但用红黑树的插入逻辑插入新节点）。这样其他桶的线程可以继续并发插入，不互相影响。//- 扩容：当元素数量超过负载因子时触发扩容。若桶是链表，会加锁桶头节点（确保搬运时不会有其他线程改动这个桶）。若桶是红黑树，也是加锁桶头节点，若拆完后树节点少于6则降级为链表。【注意】扩容时是多个线程同时看到需要扩容，每个线程去抢一段搬运工作，分工搬不同的桶，并发执行。
//在工程项目里，多线程场景推荐用 ConcurrentHashMap，比如：缓存系统、请求计数器、配置中心。
//3.手动自己加锁（外部加锁）
//自己在访问 HashMap 时，手动加锁保护，比如用 synchronized 或者 ReentrantLock。
//用synchronized
private final Map
public synchronized void put(K key, V value) {
map.put(key, value);
}
public synchronized V get(K key) {
return map.get(key);
}
//用ReentrantLock
private final Map
private final ReentrantLock lock = new ReentrantLock();
public void put(K key, V value) {
lock.lock();
try {
map.put(key, value);
} finally {
lock.unlock();
}
}
public V get(K key) {
lock.lock();
try {
return map.get(key);
} finally {
lock.unlock();
}
}
//优点：可以灵活控制锁的粒度和时机（性能理论上最高，但现实没这么理想）
//缺点：自己控制复杂，容易出错，比如忘记unlock导致死锁
HashMap的扩容机制
java1.7：数组 + 链表。若size > 容量x负载因子则触发扩容。
新建数组（为原来容量的2倍），把旧数组里的每一个链表节点，按头插法搬迁到新数组（搬过来后顺序反了）。
问题：扩容时是单线程的，若多线程同时触发扩容，没有锁保护！可能会互相篡改链表，容易导致：链表断裂、形成环。
java1.8：数组+链表+红黑树。触发扩容条件一样。
新建数组（2倍），把旧数据里的元素搬到新数组。搬迁时不用头插，而是保持链表原本顺序。（因为引入了红黑树，红黑树节点不能随便改入插入顺序，否则树结构会被破坏。保持顺序，可以兼容普通链表和红黑树统一的迁移逻辑。）
如果原来是链表：就顺序迁移，变成新的链表。如果原来是红黑树：也有专门的 TreeNode 迁移逻辑，迁移完保持树形。
为什么 JDK1.8不会形成死循环？——因为不再头插，避免了旧链表和新链表互相引用的机会。注意：JDK1.8的HashMap扩容在多线程下也不是线程安全的！只是死循环这种致命问题被规避了。
Java优化了链表转移，可以将链表拆分为高位链和低位链，保持原有顺序。
因为将原本的数组长度从n变到2时，元素新位置只有可能变成：保持原索引（低位）、原索引+原数组长度（高位）。这个计算是通过将原本（key的hash & oldCap），若结果为0则保持原索引；若不为0，则为新索引。
【举例】
# 假设老数组 oldTable 容量是 16，现在要扩容成 32。
# 在 oldTable[2] 位置，有一个链表：
A (key=2) -> B (key=18) -> C (key=34) -> null
# 节点 hash hash & oldCapacity（16） 说明
# A (key=2) 2 2 & 16 = 0 继续留在2号桶
# B (key=18) 18 18 & 16 = 16 搬到2+16=18号桶
#C (key=34) 34 34 & 16 = 16 搬到2+16=18号桶
# 【搬A】
newTable[2] = A;
A.next = null;
# 【搬B】
newTable[18] = B;
B.next = null;
# 【搬C】
B.next = C;
C.next = null;
# 搬迁后最终 newTable[18] 变成：
B -> C -> null
# 下标 内容
# 2 A -> null
# 18 B -> C -> null
【注意】先统一计算每个节点对应到新哈希表的位置，然后看一个节点下哈希冲突的元素是否超过8个，若超过则生成一个新的红黑树，并将根节点添加到新数组的对应位置；若不超过8，则生成一个链表，并将链表的头节点添加到数组的对应位置。
// 伪代码表示
Node
// ...执行元素转移...
table = newTable;
HashMap内部实际是通过一个Node数组来存储数据的，扩容后需要将引用指向新的更大的数组。这个赋值操作是一个原子操作，可以确保hashmap从一个稳定状态瞬间切换到另一个稳定状态。【妙！！】
# 搬迁前
oldTable[3]: 红黑树
3
/ \
19 35
\
51
# 搬迁后
newTable[3]: 3 -> null（链表）
newTable[19]: 19 -> 35 -> 51 -> null（链表）
当哈希冲突链表长度超过8（且数组长度大于64时）变成红黑树过程
在二叉搜索树的基础上，定义了每个节点的颜色。规则如下：
根和叶子节点（null）都是黑色（左根右，根叶黑）
不存在连续的两个红色节点（不红红）
从任一节点到叶节点所有路径黑节点数量相同（黑路同）
最长路径不超过最短路径的两倍。
AVL树查询更高效，红黑树插入和删除更高效。
插入节点默认为红色。（相对于插入黑色节点，影响较小）
红黑树插入：
插入节点是根节点：直接变黑
插入节点的叔叔是红色：叔父爷相反变色，爷爷变cur插入节点（这里还要判断根是否为黑，不是则要变为黑）
插入节点的叔叔是黑色：（LL、RR、LR、RL）旋转
LL：以爷爷作为旋转点右旋，对父亲和爷爷变色，
RR：以爷爷作为旋转点左旋，对父亲和爷爷变色
LR：先左旋爷爷的左孩子（链接爷爷和cur），然后右旋爷爷节点，对旋转点（爷爷）和中心点（cur）进行变色
RL：先右旋爷爷的右孩子（链接爷爷和cur），然后左旋爷爷节点，对旋转点（爷爷）和中心点（cur）进行变色
参考：https://www.bilibili.com/video/BV1Xm421x7Lg/?spm_id_from=333.337.search-card.all.click&vd_source=99ec55b57f4eeedd9ed62c43e87cb6ff
【联想知识】
1. 堆是所有线程共享的，可以方便GC（垃圾回收）统一管理生命周期。
2. JVM内存模型：
程序计数器（线程私有）：记录当前线程正在执行的字节码的指令地址
虚拟机栈（线程私有）：管理java方法调用过程（局部变量、操作栈、方法出口等）——若栈太深会报错stackOverFlowError；栈空间不足OutOfMemoryError
本地方法栈（线程私有）：为本地方法服务，存放其他语言编写的代码
堆（线程共享）：存放对象实例（所有new出来的对象）
分代:
新生代：又分为Eden区（新生对象最初进入的地方）、Survivor0区（第一次从Eden过来的对象，Eden区满的时候触发小型垃圾回收，幸存下来的对象移动到Survivor区）、Survivor1区（第二次转移过来的对象）----->对象如果在Survivor区经过多次（一般为15次）GC后还活着，就会晋升到老年代。
老年代：保存的是存活很久的对象。老年代GC叫做Major GC或Full GC（更重、更慢）。因为对象存活时间长，不适合频繁复制回收，所以通常采用 标记-清除 或 标记-整理 算法。
永久代（java 8之间存在）：
问题：大小固定，不易扩展（它的大小通常是启动JVM时通过参数固定的，如果一开始设置太小了，类加载太多如反射、动态代理等，很容易报OOM错误）；容易出现内存泄露，理论上这些元信息应该跟着旧项目一起收回掉，但有些静态变量偷偷拿着”档案”不还，GC发现有的档案能回收，有的不能回收，非常混乱；除了JVM自己，其他语言也想用Java堆，但每种语言管理自己Class元信息的方式不一样，永久代太死板、封闭式管理不适合多语言生态发展。
做法：将永久代撤掉，搬到方法区。
方法区（又叫元空间）：存放类信息、常量、静态变量、JIT编译后的代码
3. 内存泄露：程序中有一些本来已经不需要的对象或内存空间，但因为还有引用指向它，导致GC无法回收，从而造成内存白白占用。最严重时，会导致内存溢出，程序崩掉。
举个例子：假如有一个在线商城系统，系统里有一个【在线用户列表】，用户登录时addUser、用户退出时removeUser，但开发小王粗心了，忘记写removeUser。于是用户一旦登录就骄傲到onlineUsers列表里，即使用户已经断开连接，User对象依然在列表里。
解决方法：
VisualIVM：安装后，先启动一个java程序（或者模拟一个容易内存泄漏的例子，不断像一个静态集合里塞数据，不清理）。打开VisualVm并连接我的程序。点击程序，选中Monitor面板，观察到堆内存曲线不断上涨，即使GC后也降不下来-->很可能是内存泄露。看到内存异常上涨后，点Heap Dump，VisualIVM会把当前堆的内存镜像保存下来。
public class LeakSimulator {
private static List
public static void main(String[] args) throws InterruptedException {
while (true) {
memoryLeakList.add(new byte[1024 * 1024]); // 每次加1MB
Thread.sleep(100);
}
}
}
4. 垃圾回收算法
标记-清除：遍历所有对象，找出还活着的对象。遍历内存，把没有标记的对象清除，回收他们的空间。
优点：实现简单
缺点：会产生内存碎片：清除后剩下的内存是不连续的，长时间运行后导致无法分配大对象。
复制-清除：把内存划成两半，每次只用一半。GC时，把存活的对象从一块复制到另一块，然后把原来的整个空间一次性清除。
优点：没有碎片（因为只复制活着的对象）；分配速度快。
缺点：内存浪费（一半空间始终闲置）；适合新生代，因为新对象生命周期短，死亡率高，复制活的对象开销小。
标记-整理：标记活着的对象-->把所有活着的对象往一端移动，整理出连续的空间-->清理后面的垃圾。
优点：彻底解决内存碎片。
缺点：移动对象需要额外开销，GC暂停时间长。
分代收集：对象分代管理，不同年代采用不同的GC策略。新生代使用复制算法；老年代使用标记-整理或标记-清除。
G1回收器算法（JAVA 9+默认的垃圾回收器，JDK11之后）：把堆划分成很多小块，每个Region独立管理。优先回收垃圾最多的Region，最大限度减少回收时间；同时兼顾吞吐量和延迟。
特点：并行、并发GC（利用多核CPU）；可以预测最大停顿时间；适合大内存服务器。
【注意】在垃圾回收期间，应用程序所有线程被暂停的时间长度为停顿时间（Stop The World，STW）。若停顿时间太长，用户会感觉到卡顿，尤其是对实时性要求高的系统需要尽量缩短停顿时间。
几乎所有GC都会引发STW，只是停多久的问题。
低停顿GC：G1、AGC（java11+）、Shenandoah（java12+）——why？
传统GC的问题（Serial GC等）需要全程STW，所有用户线程停下来，GC线程独占CPU，把垃圾对象标记、回收、整理。
CMS（Concurrent Mark-Sweep）GC：把GC过程拆成几步，其中"标记"和"清除"阶段，可以跟应用线程并发进行。只有初始标记和重新标记需要短暂STW，大部分时间，程序是能继续运行的！
G1（Garbage First）GC：更进一步，不光是标记垃圾，回收（清理Region）时也支持并发进行。目标是：应用停顿越短越好，甚至可以通过参数控制（比如 -XX:MaxGCPauseMillis=200ms）。可以通过设置参数 -XX:MaxGCPauseMillis=
假设堆上有1000个Region：
G1并不会一口气扫描1000个Region。
它可能只扫描50个"脏"得最厉害的Region。
每次小批量清理，应用程序只需要停顿极短时间（几十到几百ms）。
CMS靠的是"一边扫地一边办公"，减少一次扫完的停顿； G1不仅"一边扫一边办公"，还"先扫最脏的地方"，而且"每次只扫一点点"，这样程序基本不会被扫地打断，很丝滑。
若有理解或表达偏差之处，恳请大家批评指正，不胜感激！