一、基础认知1. HashMap 定位实现Map接口键值对存储key 唯一value 可重复基于哈希表实现查询、插入、删除平均时间复杂度O(1)线程不安全多线程并发读写会出现死循环、数据丢失、数据错乱JDK1.7 和 JDK1.8 底层做了颠覆性优化是面试核心考点。2. 基础使用特性Key、Value 允许null最多一个 key 为 nullvalue 可以无限 null无序不保证存入顺序每次扩容重哈希后顺序会变化元素不排序有序需求使用LinkedHashMap排序用TreeMap存储元素NodeK,V保存 key、value、hash、下一个节点指针。3. 核心参数常量 成员变量静态常量java// 默认初始容量16必须是2的幂 static final int DEFAULT_INITIAL_CAPACITY 1 4; // 最大容量 2^30 static final int MAXIMUM_CAPACITY 1 30; // 默认负载因子 0.75 static final float DEFAULT_LOAD_FACTOR 0.75f; // 链表转红黑树阈值链表长度8 触发树化 static final int TREEIFY_THRESHOLD 8; // 红黑树退链表阈值元素6 退化为链表 static final int UNTREEIFY_THRESHOLD 6; // 最小树化容量数组长度64才允许树化否则只扩容 static final int MIN_TREEIFY_CAPACITY 64;成员变量transient NodeK,V[] table哈希主数组也叫桶数组transient SetMap.EntryK,V entrySet缓存 entry 集合int size当前存储键值对总数int threshold扩容阈值 容量 * 负载因子size 超过阈值触发扩容final float loadFactor负载因子控制数组填满程度。4. 负载因子 0.75 为什么是默认值负载因子越大数组填满更多节省空间但哈希冲突概率飙升链表变长查询变慢 负载因子越小冲突少查询快但空间利用率低频繁扩容消耗性能。 0.75 是空间与查询效率的均衡值数学泊松分布证明冲突概率最低。二、底层存储结构JDK1.7 VS JDK1.8 核心差异JDK1.7 结构数组 单向链表桶数组Entry[]冲突元素挂单向链表无红黑树链表无限拉长极端情况退化为链表查询 O (n)头插法插入新节点扩容重哈希会逆序链表多线程扩容死循环。JDK1.8 优化结构数组 单向链表 红黑树核心改进桶数组Node[]哈希冲突时同一桶下元素组成单向链表链表长度达到 8且数组长度≥64链表转为红黑树TreeNode红黑树查询 O (logn)解决长链表查询慢的问题链表元素减少到 6红黑树退回链表改为尾插法解决多线程扩容死循环问题优化哈希扰动函数降低冲突概率。结构示意图plaintexttable[0] → Node1 - Node2 - Node3链表 table[1] → TreeNode1 红黑树根节点树结构 table[2] → null空桶三、哈希寻址如何计算元素存放的数组下标1. 两步哈希算法目的将 hashCode 高低位混合减少低位重复降低哈希冲突javastatic final int hash(Object key) { int h; // 原hashCode 异或 hashCode无符号右移16位 return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }2. 计算数组下标数组长度 n 永远是 2 的幂n-1二进制全是 1与 hash 做与运算等价取模javaint index hash (n - 1);等价于hash % n但位运算效率远高于取模。为什么容量必须是 2 的幂hash (n-1)快速定位下标若 n 不是 2 次幂n-1二进制存在 0 位部分下标永远无法访问浪费空间扩容时重哈希简化计算新下标只有两种可能原index/原index 旧容量无需重新计算 hash。四、哈希冲突完整解决方案1. 什么是哈希冲突不同 key 经过 hash 计算后得到相同数组下标需要存入同一个桶即为哈希冲突。2. HashMap 采用方案链地址法所有冲突元素挂载在同一个桶下形成链表 / 红黑树对比开放寻址法、再哈希法优势明显开放寻址冲突时向后寻找空桶删除复杂不适合大量冲突再哈希冲突重复计算新 hash性能差拉链法冲突元素单独链表存储增删改查简单是 HashMap 最终选择。3. 冲突处理完整流程计算 key 的 hash 值定位数组下标 index判断桶table[index]是否为空空直接新建 Node 放入桶结束桶不为空判断第一个节点 key 是否完全相等hash相等 ( || equals)key 相同覆盖原有 value返回旧 value头节点 key 不匹配判断当前桶是红黑树还是链表红黑树调用树的 putTreeVal树上查找 / 新增节点链表循环遍历链表逐个对比 key找到相同 key覆盖 value遍历到链表尾部无匹配 key尾插新增节点插入新节点后判断链表长度是否≥8数组长度 64不树化直接扩容数组长度≥64链表转为红黑树 treeifyBinsize 自增判断 size threshold执行扩容 resize ()。4. 链表转红黑树的两个硬性条件链表节点数量 ≥ 8哈希数组容量 ≥ 64 为什么加第二条 数组很小时扩容成本极低扩容后冲突自动分散无需复杂树结构数组小于 64 时优先扩容避免树化带来额外开销。5. 红黑树退回链表条件删除元素后桶内节点数量 ≤ 6执行untreeify转为单向链表 留 6 和 8 中间的差值 7避免频繁树化、退化震荡损耗性能。五、扩容机制 resize ()1. 扩容触发条件新增元素后size thresholdthreshold 容量 * 负载因子 例默认容量 16负载 0.75阈值 12存储第 13 个元素触发扩容。2. 扩容规则新容量 旧容量 * 2始终维持 2 的幂 最大容量限制MAXIMUM_CAPACITY 2^30达到上限后不再扩容阈值改为 Integer.MAX_VALUE。3. JDK1.8 扩容优化扩容需要将旧数组所有元素重新分配到新数组重哈希 旧数组长度 n新数组 2n 元素 hash (2n-1) 只有两种结果hash n 0下标不变留在原 indexhash n ! 0下标 原 index n无需重新计算 hash直接拆分链表 / 红黑树分成两条链表直接挂载新桶效率大幅提升 同时尾插法保证链表顺序不变解决 JDK1.7 多线程扩容死循环 BUG。4. JDK1.7 扩容致命缺陷头插法 无高低位拆分逻辑多线程并发扩容时链表指针互相引用形成环形链表后续 get () 无限循环CPU100%。六、核心源码方法拆解1. put () 顶层入口java运行public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }putVal实现全部插入逻辑第四个参数 onlyIfAbsenttrue 不覆盖旧值putIfAbsent。2. get () 查询逻辑计算 hash 定位桶头节点匹配 key 直接返回判断树 / 链表分别遍历查找找不到返回 null。3. remove () 删除逻辑定位桶区分树 / 链表找到匹配节点删除如果是红黑树删除后检查节点数是否≤6满足则退化为链表size--。七、关键问题equals () 和 hashCode () 重写规范规则前提HashMap 判断 key 相等两个条件必须同时成立(p.hash hash) ((p.key key) || (key ! null key.equals(p.key)))若两个对象equals()返回 truehashCode () 必须相等 否则相等对象 hash 不同分到不同桶无法覆盖存两份数据逻辑错误若两个对象 hashCode 相等equals 可以不等哈希冲突正常现象只重写 equals 不重写 hashCode 是典型错误。示例错误场景自定义实体类只重写 equals不重写 hashCode放入 HashMap 无法正常去重。八、线程不安全所有表现HashMap 没有同步锁并发场景禁止使用问题如下数据丢失多线程同时 put同一位置节点互相覆盖无限循环 CPU100%JDK1.7 独有扩容头插法环形链表数据错乱size 计数并发更新不准确size 小于实际元素空指针异常并发扩容时数组 table 被重置访问空数组并发替代方案Hashtable全方法加 synchronized锁粒度大性能差Collections.synchronizedMap(new HashMap())方法加同步锁全局锁并发性能一般ConcurrentHashMap分段锁 / CASsynchronized高并发推荐生产首选。九、null key/value 底层原理key 为 nullhash 方法直接返回 0永远存放在数组下标 0 的桶 只能存一个 null key重复 put (null,val) 会覆盖value 允许 null无任何限制key 正常即可存储Hashtable 不允许 key/value 为 null底层判断直接抛空指针。十、常见高频拓展细节树节点 TreeNode 结构继承 Node额外存储红黑树所需父、左、右、颜色、前驱节点平衡二叉搜索树保证查询 logntransient 修饰 table 数组数组不参与序列化序列化时手动遍历存储元素因为容量是 2 的幂反序列化需要重新计算容量直接序列化数组会浪费大量空桶空间初始化容量构造函数new HashMap(10)不会直接创建容量 10 数组内部方法tableSizeFor()向上取最近 2 的幂实际容量 16TLAB 无关HashMap 是堆上对象所有节点全部分配堆内存遍历方式entrySet keySet valuesentrySet 效率最高一次获取 keyvalue。十一、完整层级总结梳理入门定义、特性、常量参数、null 规则中层底层数组 链表 红黑树结构、hash 扰动、下标计算核心哈希冲突解决方案拉链法、树化 / 退化条件、put 完整流程进阶扩容 resize 原理、JDK1.7 与 1.8 核心差异高阶equalshashCode 规范、线程不安全问题、并发替代、序列化、面试易错点。