HashMap的基本原理是什么？

HashMap 基本原理

• 定义：
• HashMap 是 Java 中基于哈希表的键值对存储结构，实现 Map 接口，支持快速存取。
• 核心原理：
• 使用数组 + 链表/红黑树存储数据。
• 通过键的 hashCode 映射到数组索引，解决冲突用链表或红黑树。

什么时候进行 resize

• 时机：
• 元素数量超过阈值：size > threshold（threshold = capacity * loadFactor）。
• 链表转红黑树未触发扩容：插入时发现桶已满但未达阈值，可能提前扩容。

扩容机制

• 方式：
• 申请新内存块，创建新数组（容量通常翻倍）。
• 原数据重新哈希到新数组，非原地扩容。

复制过程中如何处理添加和查询

• 添加：
• 扩容期间仍可添加，新数据写入旧数组，复制完成后在新数组生效。
• 查询：
• 查询操作在旧数组执行，确保一致性。

HashMap 是否线程安全

• 答：
• 不安全。
• 原因：
• 多线程下，put/resize 操作可能导致数据覆盖、死循环（Java 7）或不一致。

核心点

• HashMap 高效但非线程安全，扩容需重新分配内存。

---

1. HashMap 基本原理详解

(1) 数据结构

• 数组（Node[] table）：
• 主存储结构，称为桶（Bucket）。
• 初始容量默认 16（2^4）。
• 链表：
• 解决哈希冲突，同一索引的键值对组成链表。
• 红黑树（Java 8+）：
• 当链表长度 ≥ 8（TREEIFY_THRESHOLD）且数组容量 ≥ 64（MIN_TREEIFY_CAPACITY），转为红黑树。
• 存储过程：
• 计算键的哈希值：hash = key.hashCode() ^ (key.hashCode() >>> 16)。
• 映射到索引：index = hash & (capacity - 1)。
• 存入桶，若冲突则加入链表/红黑树。

(2) 示例

HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
// 内部：
// 1. hash("Alice") -> index = 3
// 2. table[3] = Node("Alice", 25)

---

2. Resize 时机

• 阈值触发：
• threshold = capacity * loadFactor（默认 loadFactor = 0.75）。
• 插入时若 size > threshold，触发扩容。
• 例：容量 16，阈值 12（16 * 0.75），第 13 个元素触发。
• 特殊情况：
• 插入时发现链表过长（≥ 8）但容量 < 64，直接扩容而非转红黑树。
• 代码（简化）：

if (++size > threshold)
    resize();

---

3. 扩容机制

• 方式：
• 非原地扩容：
  • 创建新数组，容量通常为旧数组的 2 倍（如 16 → 32）。
  • 原数据重新哈希到新数组。
• 重新哈希：
• Java 7：遍历链表，逐个重新计算 hash & (newCapacity - 1)。
• Java 8：优化为高低位分离：
  • 元素要么留在原索引，要么移到 原索引 + oldCapacity。
  • 利用 hash & oldCapacity 判断（位运算高效）。
• 示例：
• 旧数组（16）：

index 3: ["Alice", 25] -> ["Bob", 30]

• 新数组（32）：

index 3: ["Alice", 25]
index 19: ["Bob", 30] // 3 + 16

---

4. 复制过程中添加和查询

(1) 添加数据

• 在旧数组上执行 put：
  • 在扩容开始时，哈希表会创建一个新数组（newTable），但新数组尚未生效（即尚未完全替代旧数组）。
  • 为了保持一致性，put 操作仍然基于旧数组（oldTable）的结构进行。
  • 新插入的数据（键值对）会被添加到旧数组的对应位置（通过哈希计算）。
  • 这确保了扩容期间的写操作不会直接在新数组上执行，从而避免新旧数组数据不一致。
• 新数据记录在旧数组：
  • 当调用 put(key, value) 时，数据被插入旧数组的桶（bucket）中。
  • 如果插入触发了哈希冲突（例如链表或红黑树），数据会按旧数组的冲突解决机制（如链地址法）追加。
  • 这些新数据在旧数组中被记录，并在后续的复制过程中一并迁移到新数组。
• 复制时迁移：
  • 扩容的复制过程会遍历旧数组的每个桶，将其中的键值对重新计算哈希值并分配到新数组的对应位置。
  • 因为新数据已经被记录在旧数组中，复制过程自然会包括这些新插入的数据。
• 维护旧表和新表：
  • 在 resize() 方法中，哈希表会初始化一个新数组（newTable），其大小通常是旧数组的 2 倍。
  • 旧数组（oldTable）在复制完成前仍然是操作的“主表”，即 put 和 get 等操作都基于 oldTable。
  • 新数组（newTable）在复制过程中逐步填充，但只有当所有数据迁移完成后，newTable 才会替代 oldTable 成为新的主表。
• 复制过程：
  • 复制通常按桶（bucket）逐一进行：
    1. 遍历 oldTable 的每个桶。
    2. 对桶中的每个键值对，重新计算哈希值（基于新数组的大小）。
    3. 将键值对插入到 newTable 的对应位置。
  • 如果扩容期间有 put 操作插入了新数据，这些数据会出现在 oldTable 的某个桶中，因此会被复制过程捕获。
• 确保新数据不丢失：
  • 由于 put 操作只修改 oldTable，所有新插入的数据都在 oldTable 中。
  • 复制过程是基于 oldTable 的快照（或逐步遍历），因此无论何时插入的数据，只要在复制到对应桶之前完成插入，就会被正确迁移。
  • 在单线程环境中，复制过程是顺序执行的，新数据一定会被包含。
  • 在多线程环境中（如 Java 的 ConcurrentHashMap），需要额外的同步机制（如分段锁或 CAS）来确保并发 put 和复制过程的正确性。
• 新表生效：
  • 只有当 oldTable 的所有数据（包括扩容期间插入的新数据）都迁移到 newTable 后，哈希表才会将 newTable 设置为主表。
  • 这一步通常通过原子操作完成（如将 table 引用指向 newTable）。
• 多次扩容的极端情况：
  • 在高并发或快速连续插入的场景下，如果 put 操作频繁触发扩容，可能会导致多次 resize() 调用。
  • 例如：
    • 插入数据导致负载因子（load factor）超过阈值，触发第一次扩容。
    • 在第一次扩容尚未完成时，新的 put 操作可能继续插入数据，填满旧数组，导致再次触发扩容。
  • 为了避免这种情况，现代哈希表实现（如 Java 的 HashMap 或 ConcurrentHashMap）通常会：
    • 在扩容期间暂停新的扩容请求，直到当前扩容完成。
    • 使用原子操作或锁机制确保扩容的单一性。
  • 极端情况下，多次扩容可能导致性能下降，但不会影响数据正确性，因为每次扩容都会基于最新的 oldTable 执行。
• 复制如何确保所有数据进入新数组：
  • 单线程环境：
    • 复制过程是线性的，遍历 oldTable 的每个桶。
    • 由于 put 操作只修改 oldTable，所有新数据都会在复制时被捕获。
    • 复制完成后，newTable 包含 oldTable 的所有数据（包括扩容期间插入的）。
  • 多线程环境：
    • 多线程场景（如 ConcurrentHashMap）需要额外的并发控制。
    • 例如，Java 的 ConcurrentHashMap（JDK 8+）在扩容时使用分段迁移：
      • 每个线程负责迁移一部分桶。
      • 使用 CAS（比较并交换）或同步块确保每个桶只被迁移一次。
      • 新插入的数据会根据当前扩容状态被记录在 oldTable 或直接插入 newTable（通过转发节点）。
    • 如果有新数据插入到正在迁移的桶，ConcurrentHashMap 会通过转发节点（Forwarding Node）确保迁移线程和插入线程的协作，最终所有数据都会被正确迁移到 newTable。
  • 间隙锁的类比：
    • 虽然哈希表扩容不直接使用数据库的间隙锁，但可以类比为一种“范围保护”机制。
    • 在复制过程中，oldTable 的桶可以看作一个个“范围”，扩容机制确保这些范围内的数据（包括新插入的）不会丢失，类似于间隙锁防止幻读的插入。

4. 可能的优化和注意事项

• 减少多次扩容：
  • 预估数据规模，设置合理的初始容量和负载因子，减少扩容频率。
  • 在高并发场景下，使用 ConcurrentHashMap 这样的并发友好结构，避免锁竞争。
• 性能优化：
  • 扩容期间的 put 操作可能因旧数组的链表过长而变慢，优化索引（如红黑树）可以缓解。
  • 分段迁移（ConcurrentHashMap 的做法）可以并行化复制，减少阻塞。
• 一致性保证：
  • 确保 resize() 的原子性（通过锁或 CAS）。
  • 在复制完成前，get 操作可能仍基于 oldTable，需要设计合理的查询路径。

(2) 查询数据

• 机制：
• 查询（如 get）在旧数组执行。
• 扩容未完成，新数组不可用，确保查询一致。
• 代码（简化）：

Node<K,V> get(Object key) {
    // 始终访问 table（旧数组直到扩容完成）
    int index = hash(key) & (table.length - 1);
    return table[index];
}

---

5. 线程安全性

(1) 是否线程安全

• 答：
• 不安全。

(2) 为什么不安全

• 原因：
• Put 覆盖：
  • 多线程同时 put，可能覆盖彼此数据。
  • 例：

map.put("key", 1); // 线程 A
map.put("key", 2); // 线程 B

   - 可能丢失 `1` 或 `2`。

1. Resize 冲突：
   • Java 7：多线程扩容可能形成链表环（死循环）。
   • Java 8：虽无死循环，但多线程扩容仍导致数据丢失。
2. Size 不一致：
   • size++ 非原子操作，线程竞争导致计数错误。
3. 示例：
4. 线程 A 和 B 同时插入，size 可能少增。

(3) 替代方案

• ConcurrentHashMap：
• 分段锁（Java 7）或 CAS + 同步（Java 8），线程安全。
• Collections.synchronizedMap：
• 包装 HashMap，全局锁，性能较低。
• Hashtable：
• 全局锁，效率低。

---

6. 延伸与面试角度

• 与 TreeMap：
• HashMap 无序，TreeMap 按键排序。
• 实际应用：
• 缓存：快速键值查询。
• 配置：存储参数对。
• 优化：
• 预估容量，减少扩容。
• 例：new HashMap<>(32)。
• 面试点：
• 问“原理”时，提数组 + 链表/红黑树。
• 问“线程”时，提覆盖和死循环。

---

总结

HashMap 基于哈希表，数组 + 链表/红黑树实现，扩容在 size > threshold 时触发，申请新数组重新哈希。扩容期间添加和查询在旧数组操作，非线程安全因多线程可能覆盖或丢失数据。面试时，可提扩容优化或画数据结构，展示理解深度。