HashMap是Java集合框架中最常用的类之一也是面试中出场率最高的考点。很多人能说出“数组链表红黑树”但再往下问哈希计算、扩容机制、线程安全就支支吾吾了。本文带你从底层彻底搞懂HashMap。一、数据结构数组 链表 红黑树HashMap的本质是一个哈希表用数组存储桶bucket每个桶指向一个链表或红黑树。当多个key的哈希值映射到同一个桶时就发生了哈希冲突采用链地址法解决。JDK 8之前链表插入是头插法JDK 8改为尾插法并引入红黑树。当链表长度达到8且数组长度达到64时链表转为红黑树查询复杂度从O(n)降为O(log n)。如果数组长度小于64则优先扩容而不是转树因为扩容能重新散列减少冲突。二、哈希计算扰动函数HashMap并没有直接用key的hashCode()而是做了一次扰动java复制下载static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }将hashCode的高16位与低16位异或让高位也参与运算。因为数组长度通常较小索引计算是(n - 1) hash只有低位参与。扰动后能减少碰撞让分布更均匀。索引计算index (n - 1) hash等价于hash % n但位运算更快。这也解释了为什么容量必须是2的幂次——这样n-1的二进制全是1与运算才能得到均匀的索引。三、put流程计算key的hash值。如果数组为空先初始化默认容量16负载因子0.75。定位桶(n-1) hash。如果桶为空直接新建节点放入。如果桶不为空修改次数modCount加1如果size超过阈值执行扩容。四、扩容机制默认负载因子0.75阈值 容量 × 负载因子。当size 阈值时扩容为原来的2倍。JDK 8对扩容做了优化不需要重新计算每个元素的hash而是利用hash oldCap判断元素在新数组中的位置。如果结果为0留在原索引否则移动到“原索引 oldCap”。这是因为容量是2的幂次扩容后相当于多了一个二进制位该位为0则索引不变为1则偏移旧容量。例如旧容量16新容量32。元素hash为501015 16 0留在5hash为211010121 16 16移动到21。这个设计避免了重新散列的开销。五、线程安全问题HashMap不是线程安全的。多线程并发put可能导致数据丢失两个线程同时put后一个覆盖前一个。JDK 7死循环头插法在并发扩容时可能形成环形链表导致get时无限循环。JDK 8改为尾插法修复了死循环但仍有数据覆盖问题。size不准并发修改导致size计数错误。因此并发场景应使用ConcurrentHashMap。它通过CAS synchronized保证线程安全锁粒度更细只锁桶的头节点。六、面试常问点为什么容量是2的幂次为了位运算替代取模且扩容时元素位置要么不变要么偏移旧容量。为什么负载因子是0.75时间和空间的折中太小浪费空间太大冲突增多。为什么链表转红黑树阈值是8根据泊松分布链表长度达到8的概率极低约千万分之一此时转树才划算。HashMap允许null键和null值吗允许null键的hash为0放在索引0的桶。总结HashMap的设计处处是权衡数组与链表的取舍、红黑树的引入、扩容的优化、负载因子的选择。理解这些背后的动机远比背诵结论重要。面试时能讲清楚“为什么”才是真正的掌握。