【Java基础】集合框架： HashMap核心原理：JDK1.7 vs 1.8+ 区别、数据结构、哈希函数、扩容机制、put/get全流程、红黑树转换阈值（附《思维导图》+《面试高频考点清单》）

文章目录HashMap核心原理JDK1.7 vs 1.8 系统性知识体系一、整体概述二、核心数据结构对比1. JDK1.7数组单向链表2. JDK1.8数组单向链表红黑树三、哈希函数对比1. JDK1.7 哈希函数2. JDK1.8 哈希函数四、数组下标计算五、扩容机制对比1. 核心参数2. JDK1.7 扩容机制3. JDK1.8 扩容机制六、put方法全流程对比1. JDK1.7 put流程2. JDK1.8 put流程七、get方法全流程对比1. JDK1.7 get流程2. JDK1.8 get流程八、红黑树转换与退化阈值1. 链表转红黑树阈值2. 红黑树退化为链表阈值九、其他重要区别1. 插入方式2. 遍历方式3. 性能4. 并发问题十、常见面试考点HashMap面试版必背核心要点高频题标准答案一、面试必背核心要点3分钟速记版1. 核心数据结构2. 哈希函数3. 扩容机制核心考点4. 红黑树转换阈值必考5. put流程核心差异6. 插入方式二、高频面试题标准答案直接背诵1. HashMap的底层实现原理2. JDK1.8对HashMap做了哪些重大优化3. 为什么HashMap的数组长度必须是2的幂4. HashMap的扩容过程是怎样的1.7和1.8有什么区别5. 为什么链表转红黑树的阈值是8退化为链表是66. HashMap为什么线程不安全1.7和1.8的并发问题有什么不同7. HashMap和HashTable的区别8. HashMap和ConcurrentHashMap的区别9. HashMap的负载因子为什么是0.7510. HashMap中key的hashCode()和equals()方法有什么作用HashMap核心原理JDK1.7 vs 1.8 系统性知识体系一、整体概述HashMap是Java集合框架中最常用的键值对存储结构基于哈希表实现允许null键和null值线程不安全。JDK1.8对其进行了重大重构解决了1.7中链表过长导致的性能退化问题同时优化了哈希冲突处理和扩容机制。特性JDK1.7JDK1.8核心数据结构数组单向链表数组单向链表红黑树哈希冲突解决链地址法头插法链地址法尾插法红黑树插入方式头插法尾插法扩容时链表顺序反转保持原顺序并发问题死循环、数据丢失数据覆盖、丢失平均时间复杂度O(1)~O(n)O(1)~O(logn)二、核心数据结构对比1. JDK1.7数组单向链表底层实现Entry[] table数组每个元素是单向链表的头节点Entry节点结构staticclassEntryK,VimplementsMap.EntryK,V{finalKkey;Vvalue;EntryK,Vnext;inthash;// ...}问题当哈希冲突严重时链表会变得很长get操作时间复杂度退化为O(n)2. JDK1.8数组单向链表红黑树底层实现Node[] table数组链表长度超过阈值时转换为红黑树Node节点结构链表节点staticclassNodeK,VimplementsMap.EntryK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;// ...}TreeNode节点结构红黑树节点staticfinalclassTreeNodeK,VextendsLinkedHashMap.EntryK,V{TreeNodeK,Vparent;// 父节点TreeNodeK,Vleft;// 左子节点TreeNodeK,Vright;// 右子节点TreeNodeK,Vprev;// 前驱节点用于删除时维护链表booleanred;// 颜色标记// ...}优势红黑树的查找、插入、删除时间复杂度均为O(logn)解决了链表过长的性能问题三、哈希函数对比1. JDK1.7 哈希函数finalinthash(Objectk){inthhashSeed;if(0!hkinstanceofString){returnsun.misc.Hashing.stringHash32((String)k);}h^k.hashCode();// 多次扰动4次位运算5次异或h^(h20)^(h12);returnh^(h7)^(h4);}特点使用hashSeed随机种子可通过JVM参数配置对key的hashCode进行9次扰动目的是让高位参与运算减少哈希冲突对String类型有特殊优化2. JDK1.8 哈希函数staticfinalinthash(Objectkey){inth;// 1次位运算1次异或return(keynull)?0:(hkey.hashCode())^(h16);}特点简化为2次扰动将hashCode的高16位与低16位进行异或去掉了hashSeed随机种子null键的哈希值固定为0因此null键总是存放在数组第0个位置设计思想数组长度总是2的幂计算数组下标时使用(n-1) hash高16位参与运算可以让高位信息也影响下标计算减少哈希冲突1.8的扰动函数虽然简单但配合红黑树已经足够应对大部分场景四、数组下标计算两个版本的数组下标计算方式相同// n是数组长度总是2的幂intindexhash(n-1);为什么用而不是%位运算效率远高于取模运算为什么数组长度必须是2的幂保证n-1的二进制表示全是1这样hash (n-1)的结果才能均匀分布在[0, n-1]范围内五、扩容机制对比1. 核心参数参数含义默认值initialCapacity初始容量16loadFactor负载因子0.75fthreshold扩容阈值capacity * loadFactor2. JDK1.7 扩容机制触发条件当size threshold且当前插入位置已有元素时扩容大小原容量的2倍newCapacity oldCapacity * 2扩容过程创建新数组长度为原数组的2倍遍历原数组的每个链表对每个Entry重新计算哈希值和数组下标使用头插法将Entry插入到新数组的对应位置致命问题头插法会导致链表顺序反转多线程并发扩容时可能形成环形链表导致get操作时死循环3. JDK1.8 扩容机制触发条件当size threshold时无论当前插入位置是否有元素扩容大小原容量的2倍优化点不需要重新计算每个节点的哈希值利用hash oldCap的结果判断节点在新数组中的位置结果为0新下标 原下标结果为1新下标 原下标 原容量使用尾插法插入节点保持链表原顺序红黑树处理扩容时会对红黑树进行拆分如果拆分后树的节点数小于等于6则退化为链表并发问题尾插法避免了环形链表和死循环但仍然存在数据覆盖、丢失等问题因此HashMap仍然线程不安全六、put方法全流程对比1. JDK1.7 put流程判断table数组是否为空若为空则初始化计算key的哈希值和数组下标遍历该下标处的链表若key已存在hash相等且equals返回true则更新value并返回旧value若key不存在则继续判断是否需要扩容size threshold且当前位置已有元素若需要扩容则创建新数组并将原数组元素转移到新数组使用头插法将新Entry插入到链表头部size加1返回null2. JDK1.8 put流程1. 判断table数组是否为空若为空则调用resize()初始化 2. 计算key的哈希值和数组下标i 3. 若table[i] null则直接创建新Node插入转步骤8 4. 若table[i] ! null a. 若第一个节点的key与待插入key相同hash相等且equals返回true则直接覆盖value b. 若第一个节点是TreeNode则调用putTreeVal()插入红黑树 c. 若第一个节点是普通Node则遍历链表 i. 若找到相同key的节点则覆盖value ii. 若遍历到链表尾部仍未找到则创建新Node插入尾部 iii. 插入后判断链表长度是否 8若是则调用treeifyBin()尝试转换为红黑树 5. 若步骤4中找到了相同key的节点则返回旧value 6. 若步骤4中未找到相同key的节点则size加1 7. 判断size是否 threshold若是则调用resize()扩容 8. 返回null七、get方法全流程对比1. JDK1.7 get流程若key为null则遍历table[0]处的链表查找否则计算key的哈希值和数组下标遍历该下标处的链表找到hash相等且key.equals()返回true的节点返回节点的value若未找到则返回null2. JDK1.8 get流程计算key的哈希值和数组下标i若table[i] null则返回null若table[i]的key与待查找key相同则直接返回该节点的value若table[i]是TreeNode则调用getTreeNode()在红黑树中查找若table[i]是普通Node则遍历链表查找找到则返回value否则返回null八、红黑树转换与退化阈值1. 链表转红黑树阈值链表长度阈值TREEIFY_THRESHOLD 8数组容量阈值MIN_TREEIFY_CAPACITY 64转换条件当链表长度 8且数组容量 64时才会将链表转换为红黑树为什么是8根据泊松分布在负载因子0.75的情况下链表长度达到8的概率约为0.00000006红黑树的节点占用空间比普通Node大因此只有在链表足够长时才转换2. 红黑树退化为链表阈值阈值UNTREEIFY_THRESHOLD 6触发时机扩容时红黑树拆分后若节点数 6则退化为链表为什么是6避免频繁在链表和红黑树之间转换当节点数为6时链表的平均查找长度(3.5)已经优于红黑树的平均查找长度(log2(6)≈2.6)但考虑到红黑树的额外开销此时退化为链表更划算九、其他重要区别1. 插入方式JDK1.7头插法优点实现简单不需要遍历链表到尾部缺点扩容时链表反转并发时可能形成环形链表JDK1.8尾插法优点保持链表原顺序避免并发扩容时的环形链表问题缺点需要遍历链表到尾部才能插入2. 遍历方式JDK1.7使用Iterator遍历基于EntrySetJDK1.8新增forEach方法支持Lambda表达式3. 性能JDK1.7最坏情况下O(n)JDK1.8最坏情况下O(logn)在哈希冲突严重时性能提升明显4. 并发问题JDK1.7死循环、数据丢失、数据覆盖JDK1.8数据丢失、数据覆盖解决了死循环问题十、常见面试考点HashMap的底层数据结构1.7是数组链表1.8是数组链表红黑树HashMap的工作原理通过key的hashCode计算哈希值再通过哈希值计算数组下标然后在对应位置的链表或红黑树中查找为什么数组长度必须是2的幂保证n-1的二进制全是1使哈希结果均匀分布JDK1.8对HashMap做了哪些优化引入红黑树、简化哈希函数、尾插法、扩容优化HashMap的扩容机制触发条件、扩容大小、1.7和1.8的区别红黑树的转换阈值链表转红黑树是8红黑树退化为链表是6HashMap为什么线程不安全1.7的死循环1.8的数据覆盖HashMap和HashTable的区别线程安全、null键值、性能、父类HashMap和ConcurrentHashMap的区别线程安全实现方式、性能、锁粒度HashMap面试版必背核心要点高频题标准答案一、面试必背核心要点3分钟速记版1. 核心数据结构JDK1.7数组单向链表Entry数组JDK1.8数组单向链表红黑树Node数组核心解决1.7链表过长导致O(n)性能退化1.8红黑树将最坏时间复杂度降至O(logn)2. 哈希函数1.79次扰动4次位运算5次异或 hashSeed随机种子String特殊优化1.8简化为2次扰动h key.hashCode() ^ (h 16)去掉hashSeed共同null键哈希值固定为0存于数组第0位下标计算hash (n-1)n为数组长度3. 扩容机制核心考点维度JDK1.7JDK1.8触发条件size≥threshold且当前插入位置有元素size≥threshold无条件扩容大小原容量×2始终保持2的幂原容量×2节点迁移重新计算hash头插法→链表反转无需重算hashhash oldCap判断新位置尾插法→保持原顺序并发问题头插法导致环形链表死循环解决死循环仍存在数据覆盖/丢失4. 红黑树转换阈值必考链表转红黑树链表长度≥8且数组容量≥64缺一不可红黑树退链表扩容拆分后节点数≤6设计原因泊松分布下链表长度达8的概率≈0.0000066-8的缓冲区间避免频繁转换5. put流程核心差异1.7先判断扩容→再头插扩容后插入新数组1.8先插入→再判断扩容插入原数组后再扩容插入后检查链表长度≥8则尝试树化6. 插入方式1.7头插法实现简单无需遍历尾部1.8尾插法解决扩容死循环需遍历到尾部二、高频面试题标准答案直接背诵1. HashMap的底层实现原理标准回答HashMap基于哈希表实现采用链地址法解决哈希冲突。JDK1.7底层是Entry数组单向链表通过key的hashCode计算数组下标冲突时用链表存储。JDK1.8底层是Node数组单向链表红黑树当链表长度≥8且数组容量≥64时链表转换为红黑树将最坏查找时间复杂度从O(n)优化到O(logn)。2. JDK1.8对HashMap做了哪些重大优化标准回答数据结构优化引入红黑树解决链表过长的性能退化问题哈希函数优化简化为高16位异或低16位减少计算开销插入方式优化头插法改尾插法解决并发扩容时的环形链表死循环扩容机制优化无需重新计算每个节点的哈希值通过hash oldCap直接判断新位置原下标或原下标原容量put流程优化先插入后扩容避免不必要的扩容操作3. 为什么HashMap的数组长度必须是2的幂标准回答提高计算效率数组下标计算使用hash (n-1)位运算远快于取模运算hash % n保证哈希均匀分布当n是2的幂时n-1的二进制表示全为1此时hash (n-1)的结果能均匀分布在[0, n-1]范围内减少哈希冲突简化扩容计算1.8中扩容时可通过hash oldCap直接判断节点新位置无需重新计算哈希值4. HashMap的扩容过程是怎样的1.7和1.8有什么区别标准回答共同当元素个数size达到扩容阈值容量×负载因子0.75时扩容为原容量的2倍1.7扩容创建新数组长度为原数组2倍遍历原数组每个链表对每个Entry重新计算哈希值和下标用头插法将Entry插入新数组导致链表顺序反转多线程并发时易形成环形链表引发死循环1.8扩容创建新数组长度为原数组2倍遍历原数组每个节点无需重新计算哈希值通过hash oldCap判断结果为0则留在原下标结果为1则移到原下标原容量用尾插法插入保持链表原顺序解决了死循环问题红黑树拆分后节点数≤6时退化为链表5. 为什么链表转红黑树的阈值是8退化为链表是6标准回答阈值8的原因根据泊松分布在负载因子0.75的情况下链表长度达到8的概率约为0.00000006几乎不可能发生。因此只有在极端哈希冲突情况下才会转换为红黑树平衡了时间和空间开销红黑树节点占用空间比普通Node大阈值6的原因设置6-8的缓冲区间避免频繁在链表和红黑树之间转换。当节点数为6时链表的平均查找长度(3.5)与红黑树的平均查找长度(log₂6≈2.6)差距不大但红黑树有额外的空间和维护开销此时退化为链表更划算6. HashMap为什么线程不安全1.7和1.8的并发问题有什么不同标准回答HashMap没有任何同步机制多线程并发操作时会出现数据不一致问题JDK1.7并发扩容时头插法会导致链表反转形成环形链表get操作时陷入死循环并发插入时可能导致数据丢失JDK1.8解决了环形链表死循环问题尾插法并发插入时若两个线程同时计算到同一个数组下标后插入的线程会覆盖先插入的线程的数据并发扩容时仍可能出现数据丢失7. HashMap和HashTable的区别标准回答维度HashMapHashTable线程安全不安全安全方法加synchronized性能高低全表锁并发效率差null键值允许1个null键多个null值不允许任何null键或null值父类AbstractMapDictionary迭代器快速失败(fail-fast)快速失败初始容量1611扩容方式×2×218. HashMap和ConcurrentHashMap的区别标准回答线程安全HashMap不安全ConcurrentHashMap线程安全锁机制JDK1.7 ConcurrentHashMap分段锁Segment锁粒度是段JDK1.8 ConcurrentHashMapCASsynchronized锁粒度是数组头节点性能更高性能HashMap单线程性能最高ConcurrentHashMap并发性能远高于HashTablenull键值HashMap允许null键和null值ConcurrentHashMap不允许任何null键或null值数据结构两者1.8后都是数组链表红黑树但ConcurrentHashMap多了辅助扩容机制9. HashMap的负载因子为什么是0.75标准回答负载因子是容量和时间开销的平衡负载因子过高如1.0数组填满才扩容哈希冲突概率大幅增加链表变长查找性能下降负载因子过低如0.5数组只用一半就扩容空间利用率低频繁扩容影响性能0.75是经过大量测试得出的最优值在空间利用率和查找性能之间取得了最佳平衡。同时0.75×1612是整数计算方便。10. HashMap中key的hashCode()和equals()方法有什么作用标准回答hashCode()计算key的哈希值用于确定元素在数组中的下标。如果两个key的hashCode不同一定是不同的keyequals()解决哈希冲突问题。如果两个key的hashCode相同哈希冲突需要通过equals()判断是否是同一个key约定如果两个对象通过equals()返回true那么它们的hashCode()必须相同但hashCode()相同equals()不一定返回true注意如果重写了equals()方法必须重写hashCode()方法否则会导致HashMap无法正确工作