hashmap底层数据结构，发生了哈希冲突怎么处理?

**HashMap 底层数据结构** 在 JDK 8 中，`HashMap` 主要由 **数组（Node\[] table） + 链表 + 红黑树** 组成： * **数组**：用于存储键值对的主结构，每个位置称为一个桶（bucket）。 * **链表**：当哈希冲突发生且桶中节点数量较少时，以链表形式存储冲突的元素。 * **红黑树**：当单个桶中链表长度超过 `TREEIFY_THRESHOLD`（默认 8）时，链表会转换为红黑树，提高查找效率。 **哈希冲突的处理方式** HashMap 采用 **链地址法（Separate Chaining）** 处理冲突： 1. **计算索引** * 通过 `hash(key)` 计算哈希值，再对数组长度取模（JDK 8 中是 `hash & (n - 1)`）确定桶位置。 2. **冲突时的插入** * 如果桶中无元素，直接插入。 * 如果有元素： * **比较 key**：如果 key 相同，则替换 value。 * **key 不同**：挂在链表末尾（JDK 7 是头插法，JDK 8 改为尾插法，避免并发下死循环）。 3. **链表转红黑树** * 当桶中链表节点数 > 8 且数组长度 ≥ 64 时，链表转红黑树，提升查询性能。 **JDK 7 vs JDK 8 的差异** | 版本 | 链表插入方式 | 冲突处理 | 树化条件 | | ----- | ------ | --------- | ---------------------------- | | JDK 7 | 头插法 | 数组+链表 | 无树化 | | JDK 8 | 尾插法 | 数组+链表+红黑树 | 链表长度 > 8 且 table.length ≥ 64 | **示意图** ``` table[0] -> Node(key1, val1) -> Node(key2, val2) table[1] -> Node(key3, val3) table[2] -> Node(key4, val4) -> Node(key5, val5) -> ... (链表/红黑树) ```