面试官问我HashMap的底层原理，我答了30分钟

# 面试官问我HashMap的底层原理，我答了30分钟 ## 前言 上周面试，面试官上来就问：“说说HashMap的底层原理？”我心想这不是送分题吗，结果被追问了30分钟，差点答不上来。把面试复盘整理一下，希望对大家有帮助。 ## 底层数据结构 JDK 1.8之后，HashMap = **数组 + 链表 + 红黑树** ```java // Node节点结构 static class Node implements Map.Entry { final int hash; // 哈希值 final K key; // 键 V value; // 值 Node next; // 下一个节点（链表） } ``` ## 哈希冲突怎么解决？ 当两个key的hash值对数组长度取模后相同，就会发生哈希冲突： ```java // hash计算 - 高16位异或低16位，减少冲突 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 定位数组下标 - 用位运算代替取模 int index = (n - 1) & hash; ``` ## 踩坑：链表转红黑树的条件 > 面试官问我链表什么时候转红黑树，我只答了“链表长度大于8”，被追问后才知道还有一个条件：**数组长度必须大于等于64**，否则优先扩容。 ## 扩容机制 ```java // 默认容量16，负载因子0.75 // 当元素个数 > 容量 * 0.75 时触发扩容 // 扩容为原来的2倍 int newCap = oldCap << 1; ``` 扩容时元素要么在原位置，要么在原位置+旧容量的位置，这个设计很巧妙。 ## 面试高频问题 - **为什么容量是2的幂？** 因为 `(n-1) & hash` 等价于 `hash % n`，位运算更快 - **为什么负载因子是0.75？** 时间和空间的折中，泊松分布计算得出 - **HashMap线程安全吗？** 不安全，多线程用ConcurrentHashMap ## 总结 HashMap是Java面试的重灾区，建议大家把源码至少看一遍，理解比死记硬背重要得多。