1. ArrayList：动态数组的扛把子

   • 底层结构：基于动态数组实现，初始容量 10，每次扩容 1.5 倍。
   • 性能特性：
     • 随机访问快（O(1)），但中间插入/删除需要移动元素（O(n)）。
     • 适合读多写少场景，例如缓存、配置项存储。
   • 线程安全：非线程安全，多线程环境下需手动同步。

2. LinkedList：链表的灵活艺术家

   • 底层结构：基于双向链表实现，无容量限制。
   • 性能特性：
     • 头尾插入/删除快（O(1)），但随机访问需遍历（O(n)）。
     • 额外实现 Deque 接口，可作队列/栈使用。
   • 适用场景：高频增删操作（如消息队列）、实现栈/双向队列。

3. Vector：过时的安全卫士

   • 底层结构：类似 ArrayList，但所有方法通过 synchronized 实现线程安全。
   • 缺点：
     • 性能差（同步开销大），扩容策略更激进（默认翻倍）。
     • 现代开发中已被 CopyOnWriteArrayList 或 Collections.synchronizedList() 取代。

4. CopyOnWriteArrayList：并发的读多写少专家

   • 底层机制：写时复制（COW），写操作加锁复制新数组，读操作无锁。
   • 优点：
     • 读性能极高（无锁并发），适合读多写少的高并发场景（如配置中心）。
   • 缺点：
     • 写操作性能差（需复制整个数组），内存占用高。

5. 关键对比与选型建议

   特性	ArrayList	LinkedList	Vector	CopyOnWriteArrayList
   数据结构	动态数组	双向链表	动态数组	动态数组（写时复制）
   线程安全	否	否	是（synchronized）	是（ReentrantLock）
   适用场景	高频随机访问	高频增删	遗留系统	高并发读、低频写
   扩容策略	1.5 倍	无需扩容	2 倍	写时动态复制

冷知识：LinkedList 的 get(index) 方法会触发「链表遍历杀」——越靠近中间越慢。
避坑指南：

• 🚫 用 ArrayList 遍历删除元素需用迭代器，否则触发 ConcurrentModificationException。
• ✅ 超大数据量优先测试不同实现的耗时（如 LinkedList 头插快，但中间插入可能比 ArrayList 慢）。

1. 遍历方式与修改规则

   • 普通 for 循环

     • ✅ 允许修改：通过索引直接调用 set() 修改元素（如 list.set(i, newValue)）。
     • ⚠️ 注意：中间插入/删除元素需手动维护索引（可能影响性能）。

   • 增强 for 循环（foreach）

     • ❌ 禁止结构性修改：直接调用 add()/remove() 会触发 ConcurrentModificationException。
     • ➕ 例外：仅修改对象属性（如 obj.setName()）不会触发异常。

   • 迭代器（Iterator/ListIterator）

     • ✅ 安全修改：通过 iterator.remove() 删除元素，listIterator.set() 修改当前元素。
     • ⚠️ 限制：只能用迭代器自身方法操作，直接调用 List 的增删方法仍会触发异常。

   • 线程安全 List（如 CopyOnWriteArrayList）

     • ✅ 无锁遍历：写时复制机制允许遍历时修改（读旧数据，写新副本），无异常。

2. 核心结论

   • 单线程场景：优先用普通 for 循环或迭代器操作。
   • 高并发场景：直接选 CopyOnWriteArrayList，无脑避免异常。
   • 开发规范：禁止在 foreach 中增删元素，Java 8+ 用 removeIf()/replaceAll() 更简洁。

底层原理补充（加分项）

• ConcurrentModificationException 根源：迭代器内部记录修改次数（modCount），与集合实际修改次数不一致时触发[1,2]。
• CopyOnWriteArrayList 通过复制新数组实现无锁读，但写操作性能较低（适合读多写少场景）。

1. ArrayList 删除指定下标元素

   • 方法：直接调用 remove(int index)。
   • 时间复杂度：O(n)（需移动后续元素）。
   • 优化建议：高频删除中间元素可改用 LinkedList，或反向遍历避免索引错位。

2. LinkedList 删除指定下标元素

   • 方法：调用 remove(int index)。
   • 时间复杂度：O(n)（需遍历链表）。
   • 头尾优化：用 removeFirst()/removeLast() 可将时间降至 O(1)。

3. 线程安全场景

   • CopyOnWriteArrayList：调用 remove(int index) 会创建新数组，适合读多写少，但写性能差（O(n)）。

4. 遍历时删除

   • 安全方法：使用迭代器的 Iterator.remove()，避免 ConcurrentModificationException。

5. 性能对比与选型

   操作	ArrayList	LinkedList	CopyOnWriteArrayList
   按索引删除	O(n)	O(n)	O(n)
   适用场景	随机访问	头尾删除	高并发读场景

面试核心点：

• ArrayList 和 LinkedList 按索引删除的时间复杂度均为 O(n)，但 LinkedList 头尾删除可优化至 O(1)。
• 高频删除优先选 LinkedList 或反向遍历 ArrayList。
• 线程安全场景权衡写性能，选 CopyOnWriteArrayList 或 ConcurrentLinkedDeque。

1. 非原子操作引发数据竞争

   • size 递增非原子性：size++ 操作实际由读取旧值、计算新值、写入新值组成，多线程同时执行可能导致最终结果小于实际增加次数
   • 元素存储覆盖：多个线程在相同索引位置执行 elementData[i] = e，后写入的线程会覆盖前者的数据

2. 动态扩容竞态条件

   • 重复扩容数据丢失：多个线程同时检测到容量不足，各自创建更大的新数组并复制数据，最终仅保留最后一个线程的扩容结果
   • 扩容间隙越界风险：线程 A 扩容过程中，线程 B 仍使用旧容量索引插入数据，触发数组越界异常

3. 内存可见性问题

   • 脏读现象：线程修改数组元素后未及时同步到主内存，其他线程可能读取到修改前的旧数据
   • 失效状态传播延迟：扩容后的新数组引用更新未使用同步机制，导致部分线程继续访问旧数组

4. 迭代器快速失败机制缺陷

   • 并发修改检测失效：迭代器的 expectedModCount 与集合的 modCount 在多线程环境下无法保持同步
   • 结构变更暴露风险：迭代过程中其他线程删除元素，可能导致当前迭代器访问到已被移除的索引位置

5. 复合操作非原子性

   • 检查-执行间隙干扰：如 if(!contains(e)) { add(e) } 操作中，条件判断与添加动作之间可能被其他线程插入新操作
   • 中间状态不一致：扩容过程中新旧数组交替阶段，其他线程可能读取到仅部分数据迁移完成的中间数组

6. 指令重排序干扰

   • 初始化顺序错乱：对象初始化过程中，JVM 优化可能打乱 elementData 赋值与 size 初始化的顺序
   • 写操作乱序执行：元素赋值与 size 更新的顺序被重排，导致其他线程看到 size 变化但对应位置数据未更新

1. 扩容机制核心流程

   • 当添加元素导致数组容量不足时触发扩容
   • 新容量计算规则：原始容量的 1.5 倍（位运算实现：oldCapacity + (oldCapacity >> 1)）
   • 特殊场景处理：若计算值仍不满足需求，则直接扩容至所需的最小容量

2. 执行步骤分解

   • 创建新数组：使用 Arrays.copyOf() 生成扩容后的新数组
   • 数据迁移：将旧数组元素全量复制到新数组
   • 引用切换：将内部存储的数组引用指向新数组对象

3. 性能关键点

   • 扩容时间复杂度：O(n)（与元素数量线性相关）
   • 最佳实践：初始化时预估容量避免多次扩容
   • 内存开销：每次扩容产生旧数组的垃圾对象（可能引发 GC）

4. 容量限制机制

   • 最大数组长度限制为 Integer.MAX_VALUE - 8
   • 超过限制时可能抛出 OutOfMemoryError
   • 虚拟机的数组对象头开销导致实际最大值小于理论值

5. 特殊初始化场景

   • 默认构造器创建的空数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）
   • 首次添加元素时直接扩容至默认容量 10
   • 显式指定初始容量为 0 时将使用特殊空数组标记

1. 底层数据结构

   • HashMap 的底层由数组 + 链表 + 红黑树组成：
     • 数组（哈希桶）：初始容量为 16，存储链表头节点或红黑树根节点，每次扩容翻倍。
     • 链表：解决哈希冲突，同一索引的键值对以链表形式存储。
     • 红黑树（JDK 1.8+）：链表长度超过 8 且数组容量 ≥ 64 时，链表转为红黑树，查询复杂度从 O(n) 优化为 O(log n)。

2. 哈希函数与索引计算

   • 哈希扰动：通过 hash(key) = (h = key.hashCode()) ^ (h >>> 16) 混合高低位，降低冲突概率。
   • 索引定位：index = (n - 1) & hash（n 为数组长度且保持 2 的幂次方），位运算替代取模提升效率。

3. 核心操作流程

   • Put 操作：
     1. 计算哈希值定位索引。
     2. 若桶为空则插入新节点；否则遍历链表/树：
        • 存在相同 key 时覆盖旧值（通过 equals 判断）。
        • 不存在则插入链表末尾或红黑树。
     3. 触发扩容条件：元素数量 ≥ 容量 × 负载因子（默认 0.75）。
   • Get 操作：
     1. 计算哈希值定位索引，遍历链表/树匹配 key。
     2. 返回 value 或 null。

4. 哈希冲突解决机制

   • 链地址法：冲突键值对存入同一桶的链表或红黑树。
   • 扩容：负载因子超标时数组翻倍，重新散列元素以减少冲突。

5. 线程安全问题

   • 多线程同时修改结构（如 put/remove）可能导致数据不一致或死循环（JDK 1.7 头插法）。
   • 解决方案：使用 ConcurrentHashMap 或 Collections.synchronizedMap 包装。

6. JDK 版本差异

   • JDK 1.7：头插法链表，多线程扩容易引发死循环。
   • JDK 1.8：尾插法，引入红黑树优化，降低并发风险。

7. 自定义 Key 的设计要求

   • 必须重写 hashCode() 和 equals()：确保相同逻辑的 key 哈希值一致且等价，否则数据可能丢失。
   • 示例：未重写时，内容相同的两个对象作为 key 会被视为不同，导致 get 返回 null。

8. 性能优化建议

   • 初始容量：预估数据量设置（如 new HashMap<>(1000)），避免频繁扩容。
   • 负载因子：内存充足时可降低负载因子以减少冲突。
   • 哈希分散性：优化 hashCode() 方法，使键分布均匀。

 详见 HashMap。

1. 线程安全性结论
   HashMap 不是线程安全的类。多线程环境下直接使用可能导致：

   • 数据丢失（多个线程 put 时覆盖写入）。
   • 数据不一致（读取到中间状态）。
   • 死循环（JDK 1.7 头插法扩容形成环形链表）。
   • 迭代器失效（遍历时修改结构抛出 ConcurrentModificationException）。

2. 非线程安全的核心原因

   • 操作非原子性：put 和扩容涉及多步骤且未加锁。
   • 共享资源竞争：多线程同时修改同一哈希桶（链表/红黑树）。
   • JDK 1.7 头插法缺陷：扩容时链表顺序反转易形成环。

3. 线程安全替代方案

   • ConcurrentHashMap：
     • JDK 1.7 使用分段锁，JDK 1.8+ 改用 CAS + synchronized 锁桶头节点。
     • 高并发场景首选，性能优异。
   • Collections.synchronizedMap：
     • 通过 synchronized 包装 HashMap 所有方法。
     • 简单但性能较差，适合低并发场景。
   • Hashtable（已过时）：
     • 全局锁机制导致性能极低，不推荐使用。

4. 面试回答要点

   • 明确结论：HashMap 非线程安全。
   • 核心问题：数据竞争导致覆盖/丢失，JDK 1.7 死循环问题。
   • 解决方案：优先推荐 ConcurrentHashMap，次选 SynchronizedMap。
   • 版本差异：JDK 1.8 尾插法解决死循环，但数据竞争仍存在。

1. 哈希值计算

   • 调用 key.hashCode() 获取原始哈希值，通过扰动函数 (h = key.hashCode()) ^ (h >>> 16) 混合高低位，降低冲突概率。
   • 若 key 为 null，哈希值固定为 0。

2. 定位桶索引

   • 计算索引：index = (n - 1) & hash，其中 n 为数组长度（保持 2 的幂次方）。
   • 若数组未初始化（首次插入），调用 resize() 初始化容量为 16，负载因子为 0.75。

3. 哈希冲突处理

   • 空桶：直接创建新节点存入数组。
   • 非空桶：
     • 链表：遍历链表查找相同 key（equals 匹配）：
       • 存在相同 key：覆盖旧 value。
       • 不存在：插入链表末尾。链表长度 ≥ 8 且数组容量 ≥ 64 时转为红黑树。
     • 红黑树：调用 putTreeVal() 插入或更新节点。

4. 扩容触发与迁移

   • 当元素数量超过阈值（容量 × 负载因子）时触发扩容，新容量为旧容量的 2 倍。
   • 迁移规则：根据 (e.hash & oldCap) 判断节点分配到原索引或原索引 + 旧容量的位置。

5. 返回结果与状态更新

   • key 存在时返回旧 value，否则返回 null。
   • 更新 modCount 计数器，用于迭代器的快速失败检测。

1. 哈希值计算与索引定位

   • 计算 key 的哈希值：key.hashCode() 经扰动函数 (h = key.hashCode()) ^ (h >>> 16) 混合高低位。
   • 若 key 为 null，哈希值固定为 0。
   • 计算索引：index = (n - 1) & hash（n 为数组长度，保持 2 的幂次方）。

2. 桶位元素检查

   • 根据索引定位数组中的桶，若桶为空（table[index] == null），直接返回 null。
   • 若桶非空，检查首节点的哈希值和 key 是否匹配（通过 == 或 equals）。若匹配则返回 value。

3. 链表或红黑树遍历

   • 链表：首节点不匹配时遍历链表，通过 equals 方法逐一比对 key，找到则返回 value，否则返回 null。
   • 红黑树（JDK 1.8+）：调用 getTreeNode() 递归查找树节点，基于哈希值和 key 大小决定子树方向。

4. 时间复杂度与性能

   • 无冲突时 O(1)，链表冲突时 O(n)，红黑树优化后 O(log n)。

5. 注意事项

   • 必须正确重写 hashCode() 和 equals() 以确保 key 匹配。
   • JDK 1.8 红黑树优化长链表查询效率。
   • 迭代器依赖 modCount 检测并发修改，触发 ConcurrentModificationException。

1. 纯读场景的理论安全性

   • 若所有线程仅执行 get() 且未发生扩容，理论上是线程安全的。此时 get() 不修改结构，仅遍历现有节点。

2. 并发写入的潜在风险

   • 死循环（JDK 1.7）：扩容时链表头插法可能形成环，get() 遍历陷入死循环。
   • 中间状态读取：扩容迁移过程中可能读到未完成迁移的旧数组或部分数据。
   • 数据不一致：并发 put() 导致覆盖写入或扩容未完成时 get() 返回 null 或旧值。

3. JDK 版本差异影响

   • JDK 1.7：头插法扩容存在成环风险，get() 高并发下可能死循环。
   • JDK 1.8+：尾插法避免成环，但 get() 仍可能读取到扩容中间状态。

4. 安全实践建议

   • 纯读场景：初始化后不修改 HashMap 可视为安全。
   • 读写混合场景：使用 ConcurrentHashMap 或 Collections.synchronizedMap 包装。
   • 预分配容量：减少扩容触发概率。

5. 根本原因与验证

   • 问题根源：HashMap 未对结构性修改（扩容）与读取操作做同步控制。
   • 复现方法：压力测试工具模拟并发读写，观察 CPU 占用或异常抛出。

1. 常用 Key 类型

   • String：最常用，因其不可变性和哈希计算高效。
   • Integer/Enum：基于数值的哈希值，简单高效。
   • 自定义不可变类：需严格实现 hashCode() 和 equals()。
   • 其他包装类（如 Long）：适用于简单键值场景。

2. String 适合作为 Key 的核心原因

   • 不可变性：
     • 创建后不可修改，哈希值稳定，避免数据丢失。
   • 哈希计算高效：
     • hashCode() 使用 31 的质数乘法，分布均匀且结果缓存复用。
   • 字符串常量池优化：
     • 相同字面量共享内存，加速比较（通过 == 判断引用相等性）。
   • 完善的 equals() 实现：
     • 字符逐位比对，性能高效且逻辑严谨。
   • 语义清晰：
     • 适用于配置、URL 等场景，易读且兼容性强。

3. 使用 Key 的注意事项

   • 优先选择不可变对象：可变对象可能导致哈希值变化，引发数据不一致。
   • 正确重写 hashCode() 和 equals()：
     • 确保逻辑一致，避免哈希表定位失败。
   • 避免复杂对象：增加冲突概率且维护成本高。

1. 插入与删除性能优势

   • 红黑树插入/删除最多需 2 次旋转，平衡二叉树（如 AVL 树）可能需多次旋转。红黑树允许局部不平衡（最长路径 ≤ 2 倍最短路径），降低调整频率，适合高频更新场景。

2. 查询效率的折中

   • 平衡二叉树查询略优（树更平衡），但 HashMap 树规模小（阈值 8，树高 ≤ 3），红黑树 O(log n) 效率已接近理想值。

3. 计算开销与内存优化

   • 红黑树通过颜色标记替代高度差计算，减少 CPU 开销。元素减少到 6 时转回链表，避免内存浪费。

4. 工程实现的成熟性

   • 红黑树在 Linux 内核、Java TreeMap 等广泛应用，实现经过长期验证。平衡二叉树旋转逻辑复杂，维护成本高。

5. 综合性能平衡

   • 红黑树在插入、删除、查询间平衡更优，适合 HashMap 动态存储需求（如扩容与数据迁移）。

1. 允许 null 键的机制

   • key 为 null 时，HashMap 通过 hash() 返回哈希值 0，避免空指针异常。
   • null 键存储在数组索引 0 的位置，且仅允许存在一个（键唯一性保证）。

2. 设计原因与场景

   • 灵活性：支持表示“未知键”或配置中的默认值。
   • 单线程优化：设计未考虑多线程下 null 键的二义性（如 get(key) 返回 null 时无法区分键是否存在）。

3. 与其他容器的对比

   • Hashtable：禁止 null 键/值，直接调用 key.hashCode() 会抛空指针异常。
   • ConcurrentHashMap：禁止 null 键/值，因多线程下无法消除二义性风险，且实用价值有限。

4. 使用注意事项

   • 线程安全：多线程操作 null 键需同步控制，否则可能导致数据覆盖或逻辑错误。
   • 代码可读性：建议用 Optional 类或明确业务语义替代，避免过度依赖 null 键。

1. 数据覆盖与丢失
   多线程同时插入相同哈希桶时，可能因同时检测空桶导致数据覆盖。并发扩容时节点迁移遗漏可能造成数据丢失。

2. 死循环
   (1)JDK 1.7 及之前：头插法扩容导致链表成环，触发 get() 或 put() 操作时陷入无限循环，CPU 占用率飙升。
   (2)JDK 1.8 之后：树化扩容时，也会出现死循环常见，不过概率很低。

3. ConcurrentModificationException 异常
   迭代器遍历期间其他线程修改结构，触发快速失败机制抛出异常。

4. 脏读与逻辑错误
   读取到扩容迁移中的中间状态数据，get(key) 返回 null 时无法区分键是否存在或值为 null。

5. 扩容性能下降
   多线程重复触发扩容导致哈希重计算和节点迁移，增加 CPU 负载。JDK 1.8 扩容时仍需锁定当前桶引发线程阻塞。

6. 结构破坏与内存泄漏
   并发修改可能导致链表断裂或树结构失衡，节点引用错误可能引发内存无法回收。

1. 扩容触发条件

   • 元素数量超过阈值（阈值 = 容量 × 负载因子，默认 0.75）。
   • 链表长度 ≥8 且数组长度 <64 时优先扩容而非树化。

2. 扩容流程

   • 新数组创建：容量翻倍（保持 2 的幂次方）。
   • 数据迁移：
     • 链表拆分（JDK8+）：采用高低位分组策略，将链表拆分为低位链（原索引）和高位链（原索引 + 旧容量）。
     • 红黑树处理：节点数 ≤6 时退化为链表，否则拆分迁移。
     • 尾插法优化：JDK8 用尾插法替代头插法，避免多线程成环问题。

3. 性能优化

   • 位运算 (n-1) & hash 替代取模运算，提升计算效率。
   • 默认负载因子 0.75 平衡空间利用率与冲突概率。
   • 初始化时建议预估容量（如 new HashMap<>(预估容量/0.75 +1)）。

4. 多线程风险

   • 并发插入或扩容可能导致数据覆盖、脏读。
   • JDK7 头插法扩容会引发死循环，JDK8 尾插法彻底解决。
   • 推荐使用 ConcurrentHashMap 保证线程安全。

5. 参数调优与监控

   • 强制禁用树化：通过 JVM 参数 -Djava.util.HashMap.treeifyThreshold=2147483647（牺牲查询性能）。
   • 负载因子调整：内存敏感场景可调高（如 0.9），时间敏感场景调低（如 0.6）。
   • 扩容性能监控：关注 GC 日志中 HashMap.resize() 耗时，优化容量规划。

1. 位运算优化与计算效率

   • 容量为 2 的 n 次方时，(n-1) & hash 等价于 hash % n，但位运算性能更优（避免除法运算开销）。
   • 示例：当容量为 16（二进制 10000）时，n-1 = 15（二进制 1111），位运算直接取哈希值低 4 位。

2. 哈希分布均匀性

   • 低位掩码（n-1 全 1）确保哈希值的所有位参与索引计算，减少哈希碰撞概率。
   • 若哈希值高位不同但低位相同，仍可能分配到同一桶，但掩码机制比非 2 幂次方容量更均衡。

3. 扩容迁移高效性

   • 新容量为旧容量 2 倍时，迁移只需判断哈希值最高有效位：
     • 最高位为 0：新索引 = 原索引。
     • 最高位为 1：新索引 = 原索引 + 旧容量。
   • 示例：旧容量 16，哈希值 10101 的索引从 5 变为 21（原索引 + 16）。

4. 容量自动对齐机制

   • 通过 tableSizeFor() 方法将用户输入容量对齐到最小 2 的幂次方。例如输入 21 时调整为 32。
   • 实现方式：通过位右移和或操作填充最高位后的所有位为 1，再加 1 得到目标容量。

5. 数据结构兼容性

   • 链表转红黑树、拆分迁移等操作依赖容量为 2 的幂次方，例如高低位拆分逻辑与位掩码计算直接关联。
   • 容量非 2 的幂次方时，扩容后无法保证高低位拆分规则的简洁性，增加迁移复杂度。

1. 初始容量与扩容触发条件

   • 默认初始容量为 16，负载因子为 0.75，扩容阈值为 容量 × 0.75。
   • 首次 put() 时初始化容量为 16（不视为扩容）。
   • 当元素数量超过阈值（如 16 × 0.75 = 12）时触发扩容。

2. 扩容过程分析（默认参数下存入 20 个元素）

   • 第一次扩容：存入第 13 个元素时触发，容量从 16 扩容至 32，新阈值更新为 32 × 0.75 = 24。
   • 后续操作：存入第 14~20 个元素时，元素数量始终 ≤24，不再触发扩容。

3. 特殊情况说明

   • 链表树化：若某链表长度达到 8 但数组长度 <64，会优先扩容而非树化，但仅计入一次扩容。
   • 手动指定容量：例如 new HashMap<>(32) 时，阈值 = 32 × 0.75 = 24，存入 20 个元素不会触发扩容。

4. 总结

   • 默认场景下存入 20 个元素仅触发 1 次扩容（容量 16 → 32）。
   • 扩容次数由元素数量是否超过阈值决定，与链表/树结构无关。

1. 负载因子的定义与作用

   • 负载因子是 HashMap 中元素数量与容量的比率，用于控制扩容时机。
   • 当元素数量超过 容量 × 负载因子 时触发扩容（容量翻倍并 rehash）。

2. 默认值 0.75 的权衡

   • 空间与时间平衡：
     • 过高（如 1.0）导致哈希冲突增多，查询效率降低。
     • 过低（如 0.5）导致扩容频繁，空间利用率下降。
   • 实践验证：0.75 是多数场景下减少冲突与避免频繁扩容的最优解。

3. 调整策略

   • 高并发场景：降低负载因子（0.5~0.6），减少冲突提升查询效率。
   • 内存敏感场景：提高负载因子（0.8~0.9），减少扩容频率但容忍更高冲突。
   • 初始化优化：通过构造函数指定（如 new HashMap<>(16, 0.6f)），或按 预估容量 / 负载因子 +1 计算初始容量。

4. 对性能的影响

   • 查询效率：负载因子越高，链表/红黑树遍历时间可能增加。
   • 扩容成本：负载因子越低，rehash 操作越频繁，CPU 消耗增加。

5. 设计依据

   • 源码注释明确 0.75 是空间利用率与时间复杂度的折衷选择。
   • 扩容机制（如 (n-1) & hash）需与负载因子设计兼容。

1. 底层数据结构

   • 基于数组 + 链表实现，数组元素为 Entry 对象（包含 key、value、hash 和 next 指针）。

2. 哈希函数与索引计算

   • 哈希值计算：key.hashCode()，再通过 (hash & 0x7FFFFFFF) % 数组长度 确定索引。
   • 0x7FFFFFFF 确保哈希值为非负数，避免索引为负。

3. 线程安全实现

   • 所有公共方法（如 put、get）添加 synchronized 关键字，保证单线程操作。
   • 高并发性能差，推荐改用 ConcurrentHashMap。

4. 扩容机制

   • 初始容量 11，负载因子 0.75，阈值 = 容量 × 负载因子。
   • 触发扩容后，新容量 = 旧容量 × 2 + 1，并重新哈希所有元素。

5. 哈希冲突处理

   • 链地址法：冲突的 Entry 对象以链表形式存储，新元素插入链表头部（JDK 1.8 前）。
   • 查找时遍历链表，时间复杂度 O(n)。

6. 特殊限制

   • key 和 value 均不允许为 null，否则抛出 NullPointerException。
   • 继承自 Dictionary 类（已过时），与 HashMap（继承 AbstractMap）不同。

1. 方法级同步锁

   • 所有公共方法（如 put、get）使用 synchronized 修饰，确保同一时间仅一个线程操作 HashTable。

2. 内存可见性保障

   • synchronized 保证锁释放时将本地修改刷新到主内存，获取锁时读取最新值，避免数据不可见问题。

3. 扩容机制

   • 初始容量 11，负载因子 0.75，扩容阈值为 容量 × 负载因子。触发扩容后，新容量 = 旧容量 × 2 +1。

4. 与其他容器的对比

   • ConcurrentHashMap：分段锁或 CAS 机制支持并发读写，性能更高。
   • synchronizedMap：对普通 HashMap 加对象级锁，性能与 HashTable 类似。

5. 使用限制与性能问题

   • 禁止 null 键/值，操作需显式处理空值。
   • 全表锁导致读写互斥，高并发场景性能差，推荐改用 ConcurrentHashMap。

1. 线程安全机制

   • JDK 1.7 分段锁：将哈希表划分为多个 Segment，每个段独立加锁，支持不同段并发操作。
   • JDK 1.8 细粒度锁 + CAS：取消分段锁，对哈希桶（Node）加锁。插入时先尝试 CAS 无锁插入头节点，冲突时用 synchronized 加锁处理链表或红黑树。

2. 数据结构与扩容

   • 数组 + 链表/红黑树：链表长度 ≥8 且数组容量 ≥64 时转为红黑树，查询效率提升至 O(log n)。
   • 渐进式扩容：容量翻倍，多线程协作迁移数据，迁移期间读写可同时访问新旧数组。用 ForwardingNode 标记已迁移的桶。

3. CAS 与原子操作

   • 无锁初始化：通过 CAS 确保单线程初始化哈希表。
   • 原子更新控制：插入空桶时 CAS 写入头节点，扩容时通过 sizeCtl 变量协调线程任务分配。

4. 内存可见性保障

   • 哈希桶数组声明为 volatile，确保读取最新状态。
   • 节点 next 字段使用 volatile 修饰，防止链表遍历时数据不一致。

5. 性能对比

   • 相比 Hashtable：ConcurrentHashMap 支持并发读写不同桶，读操作无锁（JDK 1.8），吞吐量更高。
   • 相比 synchronizedMap：细粒度锁减少竞争，支持迭代期间并发修改。

1. 定位分段与锁对象

   • 键的哈希值经过两次散列运算：
     • 第一次散列定位到具体的 Segment 分段（如 hash % concurrencyLevel，默认并发级别 16）。
     • 第二次散列在 Segment 内部定位到具体的 HashEntry 桶（链表头节点位置）。
   • 每个 Segment 继承自 ReentrantLock，包含独立的 HashEntry 数组和锁状态。

2. 获取分段锁流程

   • 写操作（如 put）调用 Segment.lock() 获取该分段的可重入锁。
   • 不同分段的操作并行执行（如操作 Segment[0] 和 Segment[3] 互不阻塞）。
   • 若分段被占用，当前线程阻塞直到锁释放。

3. 操作与释放锁

   • 加锁后在 Segment 的 HashEntry 链表中执行插入/删除/更新操作。
   • 操作完成后调用 Segment.unlock() 释放锁，其他线程可竞争该锁。

4. 并发性能优势

   • 不同分段操作完全并行，仅同一分段内触发锁竞争。
   • 读操作无锁，依赖 volatile 修饰的 HashEntry 字段（如 value）保证可见性。

1. 可重入性实现

   • JDK 1.7 的 Segment 锁继承自 ReentrantLock，具备可重入特性。
   • 内部维护计数器（state 变量）：同一线程多次获取锁时计数器递增，释放时递减，归零后释放资源。

2. 运作原理

   • 线程持有标记：ReentrantLock 记录当前持有锁的线程，同一线程重复获取时直接累加计数器。
   • 释放规则：每次 lock() 必须对应一次 unlock()，否则锁无法完全释放。

3. 对比非可重入锁

   • 非可重入锁（如简单互斥锁）无法识别持有者，同一线程重复获取会死锁。
   • 分段锁的可重入性避免此问题，支持递归或嵌套调用。

4. 实际意义

   • 避免死锁：例如 put 操作内部调用其他需加锁的逻辑时，线程可重入同一锁。
   • 简化编程：无需避免同一线程的重复加锁行为，降低代码复杂度。

1. JDK 1.7 分段锁（悲观锁）

   • 基于 ReentrantLock 实现，每个 Segment 独立加锁。
   • 写操作需获取分段独占锁，同一分段内线程竞争阻塞，不同分段可并行操作。

2. JDK 1.8 混合锁机制

   • CAS（乐观锁）：
     • 初始化数组、插入空桶头节点时使用 CAS 无锁操作。
     • 扩容时通过 CAS 更新 sizeCtl 协调多线程任务。
   • synchronized（轻量级悲观锁）：
     • 哈希冲突时（链表/红黑树操作）对当前桶加锁，锁粒度细化到单个桶。
   • 读操作无锁：依赖 volatile 修饰的 Node.val 和 next 字段保证可见性。

3. 锁选择逻辑与优势

   • 低冲突场景（如空桶插入）优先使用 CAS，避免线程阻塞。
   • 高冲突场景（如链表修改）使用 synchronized 保证数据一致性。
   • 混合机制减少上下文切换和自旋开销，提升并发性能。