浅显易懂HashMap的数据结构

HashMap 就像一个大仓库，里面有很多小柜子（数组），每个小柜子可以挂一串链条（链表），链条太长的时候会变成更高级的架子（红黑树）。下面用超简单的例子解释：

​壹. 排列方式

• ​数组：一排固定的小柜子（比如柜子0、柜子1、柜子2...）。
• ​链表：如果多个东西要放在同一个柜子里，它们会串成一条链子。
• ​红黑树：当某个柜子的链子太长（比如超过8个），链子会变成一个小架子（树结构），找东西更快。

​贰. 存数据的过程

假设我们要存一个键值对 ("name", "小明")：

1. ​找柜子：先算 "name" 的哈希值（类似身份证号），比如得到柜子3。
2. ​放数据：
   • 如果柜子3是空的，直接放进去。
   • 如果柜子3已经有东西，检查链条上的每个元素：
     • 如果有相同的键（比如已经有 "name"），替换它的值。
     • 如果没有，把新键值对挂到链子末尾。
3. ​链条转架子：如果链子长度超过8，就把链子变成红黑树架子。

​叁. 取数据的过程

假设要取 "name" 对应的值：

1. ​找柜子：算 "name" 的哈希值，确定是柜子3。
2. ​找数据：
   • 如果柜子3是链子，遍历链子找 "name"。
   • 如果柜子3是架子（红黑树），用树的快速查找方法。

​肆. 代码简化版（Java）​

// 小柜子（数组）
Node[] table = new Node[16];

// 链表节点（如果链子太长，会变成 TreeNode）
class Node {
    String key;
    String value;
    Node next; // 下一个节点
}

// 红黑树节点（架子结构）
class TreeNode extends Node {
    TreeNode parent;
    TreeNode left;
    TreeNode right;
}

// 存数据示例
void put(String key, String value) {
    int hash = key.hashCode();
    int index = hash % table.length; // 计算柜子位置
    
    if (table[index] == null) {
        // 柜子是空的，直接放进去
        table[index] = new Node(key, value);
    } else {
        // 柜子非空，挂到链子末尾或更新值
        // 如果链子太长，转成红黑树
    }
}

​伍. 一句话总结

HashMap​ 的数组是主干，链表解决哈希冲突，红黑树解决链表过长时的性能问题！

陆. 源码：HashMap的putVal()方法

    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

柒、我们来拆解 ​​“哈希冲突时，链表如何挂到数组上”​​ 的详细过程，用大白话 + 例子解释：

​1. 核心原理：用链表串联冲突的键值对

• 当两个不同的键（比如 "name" 和 "age"）通过哈希计算后，分配到 ​同一个数组位置（同一个柜子）​​ 时，就会发生 ​哈希冲突。
• 此时，HashMap 会用 ​链表​ 把这些冲突的键值对串起来，挂在数组的这个位置上（类似挂一串钥匙）。

​2. 具体挂链表的步骤（逐行分析）​

假设数组的某个位置 index 已经有数据，现在要存入新的键值对 (key2, value2)：

1. ​检查是否重复：遍历链表，对比每个节点的 key：

   • 如果发现某个节点的 key 和 key2 ​相同​（用 equals() 判断），直接覆盖它的值。
   • 如果链表中没有相同的 key，则把新节点 ​挂到链表末尾​（Java 8 之后是尾插法）。

2. ​链表挂载示意图：

   // 数组的某个位置 index 已经有一个节点 Node1
   table[index] = Node1(key1, value1) -> null;
   
   // 存入新节点 Node2（冲突）
   Node1.next = Node2(key2, value2); // 挂到链表尾部
   table[index] = Node1 -> Node2 -> null;

3. ​代码逻辑简化版：

   Node existingNode = table[index]; // 获取数组当前位置的链表头
   
   // 遍历链表，检查是否已有相同的 key
   while (existingNode != null) {
       if (existingNode.key.equals(newKey)) {
           existingNode.value = newValue; // 覆盖旧值
           return;
       }
       existingNode = existingNode.next;
   }
   
   // 如果没有重复 key，把新节点挂到链表末尾
   Node newNode = new Node(newKey, newValue);
   newNode.next = table[index]; // Java 8 之前是头插法（新节点变成链表头）
   table[index] = newNode;      // Java 8 之后是尾插法（直接挂在链表尾部）

​3. 关键细节：头插法 vs 尾插法

• ​Java 8 之前：新节点插入链表头部（头插法）。
  • 问题：多线程下可能导致链表成环（死循环）。
  • 示例：table[index] = 新节点 -> 旧节点 -> null。
• ​Java 8 之后：新节点插入链表尾部（尾插法）。
  • 改进：避免多线程下的链表成环问题。
  • 示例：旧节点 -> 新节点 -> null。

​4. 链表转红黑树的条件

• 当链表长度 ​超过 8，且 ​数组总长度 ≥ 64​ 时，链表会转换成红黑树。
• ​如果数组长度 < 64，即使链表长度 > 8，HashMap 也会优先选择 ​扩容数组​（而不是转树），因为扩容能直接减少哈希冲突的概率，成本更低。
• 这正说明 HashMap 的设计是 ​先尝试扩容解决冲突，实在不行再转树。😄

  • 为什么这样设计？

    • ​小数组时扩容更高效：

      • 数组较小时，哈希冲突可能只是因为数组容量不足，直接扩容能快速缓解问题。
      • 红黑树结构复杂，维护成本高，小规模数据下不如扩容划算。

    • ​大数组时优化查询：

      • 数组足够大（≥64）后，如果仍有长链表，说明哈希冲突难以通过扩容解决（如多个 key 哈希值相同）。
      • 此时转为红黑树，将查询复杂度从 O(n) 降为 O(logn)。

​5. 完整流程示例

假设存入 ("name", "小明") 和 ("age", 18)，它们的哈希值冲突（都映射到数组位置 3）：

1. ​存入第一个节点：

   table[3] = Node("name", "小明") -> null;

2. ​存入第二个节点（冲突）​：

   // 检查链表，发现没有重复 key，挂到链表末尾
   table[3] = Node("name", "小明") -> Node("age", 18) -> null;

3. ​查找时：遍历链表，逐个对比 key，找到对应值。

​6.总结

• ​链表挂在数组上：通过节点的 next 指针串联冲突的键值对。
• ​插入位置：Java 8 之后用尾插法，避免多线程问题。
• ​转红黑树：链表过长时优化查找速度（从 O(n) 优化到 O(log n)）。

捌、再帮你用 ​​“仓库管理员” 的比喻​ 总结一下，确保彻底理解：

​终极傻瓜版总结

1. ​仓库（数组）​：管理员有一排柜子（比如16个），每个柜子有编号（0到15）。
2. ​存东西（键值对）​：
   • 管理员用 ​哈希函数​（比如 key.hashCode() % 16）算出东西应该放哪个柜子。
   • 如果柜子空，直接放进去。
3. ​柜子冲突（哈希冲突）​：
   • 如果柜子已经有东西，管理员会拿一根 ​链条（链表）​​ 把新东西和旧东西绑在一起，挂在柜子里。
   • ​链条的挂法：新东西挂在链条的尾部（Java 8之后）。
4. ​链条太长怎么办：
   • 如果链条长度超过8，管理员会把链条换成 ​高级货架（红黑树）​，这样找东西更快。
   • 但如果仓库的柜子总数太少（比如小于64个），管理员会直接 ​扩建仓库（扩容数组）​，而不是换货架。

​关键逻辑图示

// 数组（柜子列表）
Node[] table = [柜子0, 柜子1, ..., 柜子15];

// 柜子里的内容（链表或树）
柜子3 -> Node1("name", "小明") -> Node2("age", 18) -> null  // 链表形式
柜子5 -> TreeNode("id", 1001)  // 树形式（如果链表转成了红黑树）

​容易混淆的点

1. ​覆盖值：如果两次存同一个 key（比如两次存 "name"），会直接覆盖旧值。
2. ​哈希函数：hashCode() 决定柜子位置，但不同对象可能算出相同的哈希值（冲突）。
3. ​扩容：当仓库的柜子被填满超过一定比例（默认75%），管理员会扩建仓库（数组长度翻倍），重新分配所有东西的位置。

玖、结合 ： 面试被问 Java中hashmap数据结构 

        URL： 地基：Java中hashmap数据结构（面试被问）-CSDN博客

兄弟们，理解好了。rt.jar包里的hashmap源码的putval方法的方式，有厉害的同学可以学以致用哈！向大家致敬！

（望各位潘安、各位子健/各位彦祖、于晏不吝赐教！多多指正！🙏）

-----分界线----------------------------------------------------------------------------------------------------

兄弟们，上面的足以应付面试了，如何还想更深入，可以看下面的。

拾. 为什么数组长度 ≥64 时不扩容，而是转树？

​1 扩容的局限性**

• ​扩容的本质：通过扩大数组长度，将节点分散到新数组中，减少哈希冲突。
• ​局限性：如果多个键的哈希值本身就冲突（例如哈希算法导致碰撞），即使扩容也无法分散它们。

  // 例如：键A和键B的哈希值不同，但取模后仍落在同一个桶
  hash(A) % 64 = 5;
  hash(B) % 64 = 5;  // 即使数组扩容到128，依然可能 hash(A) % 128 = 5，hash(B) % 128 = 5

​2) 转树的优势**

• ​解决哈希碰撞：当哈希冲突无法通过扩容避免时（如多个键哈希值相同），红黑树将查询复杂度从链表O(n)降到O(logn)。
• ​成本权衡：
  • ​扩容成本高：需新建数组、重新哈希所有节点（时间复杂度O(n)）。
  • ​转树成本低：只处理单个冲突严重的桶，其他桶不受影响。

​3) 阈值为什么是64？**

• ​经验值：基于测试和性能权衡：
  • 数组长度较小时（<64），哈希冲突可能因数组容量不足，优先扩容更高效。
  • 数组长度≥64时，认为哈希冲突更可能是哈希算法导致（而非数组容量问题），转树更合理。

4. 源码逻辑验证

HashMap的treeifyBin()方法中会先检查数组长度是否≥64，再决定转树或扩容：

// HashMap 源码片段
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { // MIN_TREEIFY_CAPACITY=64
        resize(); // 数组长度<64时，选择扩容
    } else {
        // 数组长度≥64时，将链表转为红黑树
        TreeNode<K,V> hd = null, tl = null;
        // ...（具体转树逻辑）
    }
}

5. 举例说明

​场景1：数组长度=16，链表长度=9

• 数组长度16 < 64 → ​触发扩容​（数组扩大到32），而不是转树。

​场景2：数组长度=64，链表长度=9

• 数组长度≥64 → ​链表转为红黑树，不再扩容。

6、​总结

• ​转树的条件：链表长度>8 ​且​ 数组长度≥64。
• ​转树的目的：针对哈希算法导致的不可分散冲突，用空间换时间（红黑树优化查询）。
• ​扩容的优先级：数组较小时，扩容是更经济的解决方案。

拾壹、数组扩容是否重新计算哈希值？

在 HashMap 中，当数组长度小于 64 时触发扩容，哈希值本身不会重新计算，但元素在数组中的位置（索引）会根据新的数组长度重新确定。以下是具体机制：

​1. 哈希值如何生成？

• ​哈希值来源：
  HashMap 中每个键（Key）的哈希值由以下两步生成：

  1. 调用键对象的 hashCode() 方法，得到原始哈希值。
  2. 通过 ​扰动函数​（位运算）对原始哈希值进行二次处理，增加随机性，减少哈希冲突。

     // HashMap 的扰动函数实现
     static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }

• ​哈希值的存储：
  这个最终哈希值会在键值对被插入 HashMap 时计算一次，并存储在 Node 或 TreeNode 对象中，后续不再重新计算。

​2. 扩容时如何确定新位置？

当数组长度从 oldCap（例如 16）扩容到 newCap（例如 32）时，元素的索引位置会按以下规则重新分配：

1. ​索引计算公式：
   新索引 = hash & (newCap - 1)
   （newCap - 1 是新的掩码，例如 32 → 0b11111）。

2. ​优化计算技巧：
   由于扩容是翻倍（newCap = oldCap << 1），新掩码比旧掩码多出一个高位 1（例如 16 → 0b1111，32 → 0b11111）。
   因此，新索引只需判断哈希值中新增的高位是 0 还是 1：

   • 如果高位是 0：新索引 = ​原位置。
   • 如果高位是 1：新索引 = ​原位置 + oldCap。

   ​源码逻辑：

   // 遍历旧数组中的每个桶
   for (int j = 0; j < oldCap; j++) {
       Node<K,V> e;
       if ((e = oldTab[j]) != null) {
           // 检查哈希值高位是 0 还是 1
           if ((e.hash & oldCap) == 0) {
               // 高位为 0 → 留在原位置（j）
           } else {
               // 高位为 1 → 移动到新位置（j + oldCap）
           }
       }
   }

​3. 示例说明

假设原数组长度 oldCap = 16（二进制 0b10000），扩容后 newCap = 32（二进制 0b100000）。

• ​键的哈希值：假设为 0b10101。
• ​旧索引计算：
  hash & (oldCap - 1) = 0b10101 & 0b1111 = 0b00101 → 索引 5。
• ​新索引计算：
  hash & (newCap - 1) = 0b10101 & 0b11111 = 0b10101 → 索引 21。
  或者直接通过高位判断：
  hash & oldCap = 0b10101 & 0b10000 = 0b10000 ≠ 0 → 高位为 1，新索引 = 5 + 16 = 21。

​4. 为什么哈希值不重新计算？

• ​性能优化：哈希值的计算涉及 hashCode() 方法和扰动函数，重新计算会带来额外开销。
• ​一致性保障：哈希值在键的生命周期内应保持不变（除非键对象被修改，但这违反 HashMap 的设计前提）。

5、​总结

• ​哈希值固定：在键插入时计算一次，后续不再变更。
• ​索引重新分配：扩容时利用原哈希值的高位判断新位置，无需重新计算哈希值。
• ​设计目标：以最小成本重新分布元素，同时减少哈希冲突。

兄弟辛苦，🙇‍♂️。 点烟！

（望各位潘安、各位子健/各位彦祖、于晏不吝赐教！多多指正！🙏）