💡 核心逻辑：一句话先记住

不管是存数据（put）还是取数据（get），HashMap 的核心套路就三步：第一步算密码（Hash），第二步找柜子（桶位），第三步翻箱倒柜（找 Key）。 get 比较轻量，只负责找；put 比较沉重，找不到要塞进去，拿不下还要换大房子（扩容）。

📥 1. 存数据（put）的完整流程

当你想把一对数据（比如 Key="张三", Value="18岁"）放进去时：

1. 算密码（计算 Hash 值）： 拿“张三”去噼里啪啦一顿算，算出他的哈希密码。底层用了一个叫“扰动函数”的黑科技，把高位和低位的信息混合在一起，目的就是为了让密码更随机，不撞款。
2. 找柜子（定位索引）： 拿着密码去和柜子的总数做位运算 (n - 1) & hash。瞬间就能精准定位到“张三”应该去几号柜子。
3. 看柜子空不空： * 柜子是空的： 太棒了，直接把“张三”塞进去，完事！
   • 柜子被人占了（哈希冲突）： 只能去排队。如果里面是链表，就乖乖用“尾插法”排到队伍最后面；如果里面已经升级成了红黑树，就按照树的规矩二分查找塞进去。
4. 覆盖或升级： * 如果排队时发现有个人的 Key 也叫“张三”，那就用新的“18岁”把他的旧年龄覆盖掉。
   • 如果这是个新来的，且发现链表排队的人达到了 8 个（总容量也到了 64），就会把链表升级成红黑树。
5. 检查要不要换大房子（扩容）： 塞完之后，HashMap 会看一眼总人数。如果超过了地盘的 75%（负载因子 0.75），它就会调用 resize() 换一个大一倍的超级大柜子，并把所有人都重新分配一遍。

📤 2. 取数据（get）的完整流程

当你喊一句“把张三的年龄给我拿出来”时：

1. 算密码、找柜子： 前两步和 put 一模一样！先算“张三”的 Hash，再定位到他是几号柜子（这就是为什么存取能一样快的原因）。
2. 空柜直接返回： 如果那个柜子空空如也，说明根本没这个人，直接回复你 null。
3. 翻箱倒柜找人： 如果柜子里有人，先瞅一眼第一个人是不是“张三”（先比 Hash 值，再用 equals 比对名字）。
   • 如果是链表： 从头到尾挨个问：“你是张三吗？”，直到找到为止。
   • 如果是红黑树： 顺着树的分叉快速往下找，效率极高。
4. 给结果： 找到了就吐出“18岁”，到死也没找到就返回 null。

🧠 面试高频两个“为什么”

• 为什么先比 Hash，再比 equals()？

  因为 Hash 是整数比较，计算机算起来飞快，能瞬间过滤掉 99% 不合符的人；而 equals 比较复杂（比如比对长字符串），比较慢，所以放在最后用来当做“终极确认”。

• 为什么用 (n - 1) & hash 定位柜子，而不是用传统的取模 %？

  因为在计算机世界里，位运算的速度远快于算术取模。只要保证 HashMap 的容量 $n$ 永远是 2 的几次方（比如 16, 32, 64），这个位运算公式算出来的结果就和取模一模一样，属于极限压榨性能的骚操作。

🎯 秒记口诀

put 流程： 算 hash、定桶位、空桶插、有桶找、找到换、找不到插尾、检查树化和扩容。

get 流程： 算 hash、定桶位、空桶返 null、有桶找、链表挨个问、红黑树高效找。