IT 面试题库

HashMap 的底层实现原理?JDK 1.8 做了哪些改动?

中级简答题Java开发工程师Java后端工程师后端开发工程师JavaHashMap集合源码

题目

请说明 HashMap 的数组+链表+红黑树结构、put 流程、扩容机制,以及 JDK 1.8 相比 1.7 的变化。

参考答案

内容深度:适中 · 无代码示例 · 来源:网络整理 · 未复核 · 24 天前更新

底层结构(JDK 1.8):数组(Node[] table,容量恒为 2 的幂)+ 链表 + 红黑树。哈希冲突的元素挂成链表(用 (n-1) & hash 定位桶,n 为容量,等效取模但更快)。

put 流程:计算 hash → 定位桶 → 空桶直接放 → 是红黑树按树插入 → 是链表尾插(1.7 是头插,并发扩容会成环死循环,1.8 改尾插)→ 链表长度 ≥8 且数组容量 ≥64 时树化(否则先扩容)→ size 超过 容量×0.75(负载因子)触发扩容翻倍,元素重新分布。

1.8 的主要改动:

  1. 引入红黑树:冲突严重时查询从 O(n) 降到 O(logn);
  2. 头插改尾插:修复并发扩容链表成环;
  3. 扩容优化:新位置要么在原下标、要么在原下标+旧容量(利用 hash 高位 bit),无需重算 hash。

常识追问:HashMap 非线程安全(并发用 ConcurrentHashMap);key 的对象须正确实现 equals/hashCode;容量设 2 的幂是为了位运算取模与扩容重分布。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题