← 返回目录

第 3 节:HashMap 源码分析(下)

第 56 / 320 卷作者:付政委日期:

第 3 节:HashMap 源码分析(下)

在上一章节我们讲解并用数据验证了,HashMap 中的,散列表的实现、扰动函数、

负载因子以及扩容拆分等核心知识点以及相应的作用。

除了以上这些知识点外,HashMap 还有基本的数据功能;存储、删除、获取、遍历,

在这些功能中经常会听到链表、红黑树、之间转换等功能。而红黑树是在 jdk1.8

引入到 HashMap 中解决链表过长问题的,简单说当链表长度>=8时,将链表转换

位红黑树 ( 当然这里还有一个扩容的知识点,不一定都会树化

[MIN_TREEIFY_CAPACITY])。

那么本章节会进行讲解以下知识点;

1.数据插入流程和源码分析 2.链表树化以及树转链表

3.遍历过程中的无序 Set的核心知识

一、插入

1. 疑问点&考题

通过上一章节的学习,大家对于一个散列表数据结构的 HashMap 往里面插入数据

时,基本已经有了一个印象。简单来说就是通过你的 Key 值取得哈希再计算下标,

之后把相应的数据存放到里面。

但再这个过程中会遇到一些问题,比如;

1.如果出现哈希值计算的下标碰撞了怎么办?

2.如果碰撞了是扩容数组还是把值存成链表结构,让一个节点有多个值存放呢?
3.如果存放的数据的链表过长,就失去了散列表的性能了,怎么办呢?
4.如果想解决链表过长,什么时候使用树结构呢,使用哪种树呢?

这些疑问点都会在后面的内容中逐步讲解,也可以自己思考一下,如果是你来设

计,你会怎么做。

2. 插入流程和源码分析

HashMap 插入数据流程图

图 83-1
图 83-1

公众号:bugstack 虫洞栈,HashMap 插入数据流程图

visio原版流程图,可以通过关注公众号:bugstack虫洞栈,进行下载

以上就是 HashMap 中一个数据插入的整体流程,包括了;计算下标、何时扩容、

何时链表转红黑树等,具体如下;

1. 首先进行哈希值的扰动,获取一个新的哈希值。(key == null) ? 0 : (h

= key.hashCode()) ^ (h >>> 16);

  1. 判断 tab 是否位空或者长度为 0,如果是则进行扩容操作。

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

3. 根据哈希值计算下标,如果对应小标正好没有存放数据,则直接插入即可

否则需要覆盖。tab[i = (n - 1) & hash])

4. 判断 tab[i]是否为树节点,否则向链表中插入数据,是则向树中插入节

点。

5. 如果链表中插入节点的时候,链表长度大于等于 8,则需要把链表转换为

红黑树。treeifyBin(tab, hash);

  1. 最后所有元素处理完成后,判断是否超过阈值;threshold,超过则扩容。

7. treeifyBin,是一个链表转树的方法,但不是所有的链表长度为 8 后都会

转成树,还需要判断存放 key 值的数组桶长度是否小于 64

MIN_TREEIFY_CAPACITY。如果小于则需要扩容,扩容后链表上的数据会被

拆分散列的相应的桶节点上,也就把链表长度缩短了。

JDK1.8 HashMap 的 put 方法源码如下:

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

// 初始化桶数组 table,table 被延迟到插入新数据时再进行初始化

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

// 如果桶中不包含键值对节点引用,则将新键值对节点的引用存入桶中即可

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else {

Node<K,V> e; K k;

// 如果键的值以及节点 hash 等于链表中的第一个键值对节点时,则将 e 指向该键值对

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

// 如果桶中的引用类型为 TreeNode,则调用红黑树的插入方法

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

else {

// 对链表进行遍历,并统计链表长度

for (int binCount = 0; ; ++binCount) {

// 链表中不包含要插入的键值对节点时,则将该节点接在链表的最后

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

// 如果链表长度大于或等于树化阈值,则进行树化操作

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

break;

}

// 条件为 true,表示当前链表包含要插入的键值对,终止遍历

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

全站分卷索引 · 320 卷
  1. 1介绍
  2. 23. 阅读建议
  3. 3目录
  4. 4第 5 章 JVM 虚拟机
  5. 5本书源码
  6. 6第 1 章 谈谈面试(4节)
  7. 7二、谢飞机简历
  8. 8三、面试框架
  9. 91. 自我介绍
  10. 103. 算法
  11. 114.1.2 Redis
  12. 124.2 框架
  13. 134.2.2 Mybatis
  14. 144.3.4 Hbase
  15. 154.5.4 分布式任务
  16. 165.3 技术沉淀
  17. 176. 个人&面试官
  18. 18第 2 节:认知自己的技术栈盲区
  19. 192. 汇总出来的技术栈列表
  20. 20二、汇总技术架构图
  21. 211. 负载
  22. 223. 架构
  23. 238. 环境
  24. 24一、我的简历都石沉大海
  25. 25二、修改后电话约面不断
  26. 26三、简历好也要做好准备
  27. 271.4 Rpc框架 - Dubbo
  28. 282. 源码理解
  29. 29五、总结
  30. 30第 4 节:大厂都爱聊啥
  31. 312. 地理位置
  32. 322. 大厂考题
  33. 332.1 阿里、百度、腾讯
  34. 343. 考点总结
  35. 35三、总结
  36. 36第 2 章 数据结构和算法(11节)
  37. 37二、资源下载
  38. 382. 来自stackoverflow的回答
  39. 393. Hash值碰撞概率统计
  40. 403.3 Hash碰撞概率计算
  41. 414. Hash值散列分布
  42. 424.1 哈希值分段存放
  43. 434.2.1 乘数2散列
  44. 44四、总结
  45. 45第 2 节:HashMap 源码分析(上)
  46. 461.1 代码实现
  47. 471.2 Hash散列示意图
  48. 481.3 这个简单的HashMap有哪些问题
  49. 492. 扰动函数
  50. 502.2 实验验证扰动函数
  51. 512.2.2 扰动函数散列图表
  52. 523. 初始化容量和负载因子
  53. 533.2 负载因子
  54. 544. 扩容元素拆分
  55. 554.2 数据迁移
  56. 56第 3 节:HashMap 源码分析(下)
  57. 573. 扩容机制
  58. 584. 链表树化
  59. 595. 红黑树转链
  60. 60二、查找
  61. 61三、删除
  62. 62四、遍历
  63. 633. 测试结果分析
  64. 64五、总结
  65. 65第 4 节:2-3树与红黑树学习(上)
  66. 662. 二叉搜索树退化链表
  67. 673. 2-3树解决平衡问题
  68. 68三、2-3树使用
  69. 692. 数据插入
  70. 703. 数据删除
  71. 714. 数据索引
  72. 72四、总结
  73. 73第 5 节:2-3树与红黑树学习(下)
  74. 741. 为什么既有2-3树要有红黑树
  75. 753. 复杂2-3树转红黑树
  76. 761.1 左旋转
  77. 771.3 左右旋综合运用
  78. 781.4 染色
  79. 793. 删除操作
  80. 803.2.1 被删节点兄弟为黑色&含右子节点
  81. 813.3. 删除右侧节点
  82. 82四、总结
  83. 83第 6 节:ArrayList 详细分析
  84. 84二、数据结构
  85. 851.1 方式01;普通方式
  86. 861.3.1 ArrayList构造函数
  87. 871.3.2 Arrays.asList
  88. 881.4 方式04;Collections.ncopies
  89. 892.2 插入时扩容
  90. 902.3 指定位置插入
  91. 912.3.2 元素迁移
  92. 923. 删除
  93. 934. 扩展
  94. 944.2 代码操作(获取元素)
  95. 95第 7 节:LinkedList、ArrayList,插入分析
  96. 96二、数据结构
  97. 97三、源码分析
  98. 982. 插入
  99. 992.1.1 源码
  100. 1002.1.2 验证
  101. 1012.2 尾插
  102. 1022.2.2 验证
  103. 1032.3 中间插
  104. 1042.3.1 源码
  105. 1052.3.2 验证
  106. 1063. 删除
  107. 1073.2 源码
  108. 1084. 遍历
  109. 1094.2 增强for循环
  110. 110四、总结
  111. 111第 8 节:双端队列、延迟队列、阻塞队列
  112. 112一、面试题
  113. 113二、数据结构
  114. 1141.1 功能使用
  115. 1151.2 源码分析
  116. 1162. 双端队列ArrayDeque
  117. 1172.1 功能使用
  118. 1182.2.1 初始化
  119. 1192.2.3 两倍扩容,数据迁移
  120. 1203. 双端队列LinkedList
  121. 1213.1 功能使用
  122. 1223.2 源码分析
  123. 1234. 延时队列DelayQueue
  124. 1244.2 源码分析
  125. 1254.2.2 元素出栈
  126. 1265. 还有哪些队列?
  127. 1275.2 使用案例
  128. 128四、总结
  129. 129第 9 节:java.util.Collections、排序、二分、洗牌、旋转算法
  130. 1301. Collections.sort 排序
  131. 1311.4 reverseOrder倒排
  132. 1322. Collections.binarySearch 二分查找
  133. 1332.2 源码分析
  134. 1343. Collections.shuffle 洗牌算法
  135. 1354. Collections.rotate 旋转算法
  136. 1364.1 功能应用
  137. 1374.2.1 旋转算法,rotate1
  138. 1384.2.2 旋转算法,rotate2
  139. 1395. 其他API介绍
  140. 1405.3 连续集合位置判断
  141. 141第 10 节:StringBuilder 与 String 对比
  142. 1421.1 String
  143. 1432. StringBuilder 比 String 快, 为什么?
  144. 144三、String 源码分析
  145. 1452. 不可变(final)
  146. 1463. intern()
  147. 1473.3 问题图解
  148. 1481. 初始化
  149. 1492.2 扩容操作
  150. 1502.4 toString()
  151. 151六、常用API
  152. 152七、总结
  153. 153第 11 节:ThreadLocal 源码分析
  154. 154二、ThreadLocal 分析
  155. 1551.1.1 线程不安全验证
  156. 1561.1.2 使用 ThreadLocal 优化
  157. 1571.2 链路追踪
  158. 1581.2.2 测试结果
  159. 1592. 数据结构
  160. 1603. 散列算法
  161. 1613.2 验证散列
  162. 1623.2.2 单元测试
  163. 1634. 源码解读
  164. 1644.2 设置元素
  165. 1654.2.2 源码分析
  166. 1664.3 扩容机制
  167. 1674.4 获取元素
  168. 1684.5 元素清理
  169. 1694.5.2 启发式清理[cleanSomeSlots]
  170. 170三、总结
  171. 171第 3 章 码农会锁(5节)
  172. 172二、volatile 讲解
  173. 1732. 加上volatile关键字
  174. 1743. volatile怎么保证的可见性
  175. 1754. 反编译解毒可见性
  176. 1764.2 查看汇编指令
  177. 1775. 不加volatile也可见吗
  178. 178三、总结
  179. 179第 2 节:synchronized
  180. 1801. 对象结构
  181. 1811.2 验证对象结构
  182. 1821.2.2 指针压缩关闭
  183. 1831.2.3 对象头哈希值存储验证
  184. 1841.3 Monitor 对象
  185. 1852. synchronized 特性
  186. 1862.2 可见性
  187. 1872.3 有序性
  188. 1882.4 可重入性
  189. 1893. 锁升级过程
  190. 1903.1 偏向锁
  191. 1913.2 轻量级锁
  192. 192四、傅诗一手
  193. 193第 3 节:ReentrantLock 和 公平锁
  194. 1942. ReentrantLock 知识链条
  195. 1953.2 公平锁、非公平锁,选择
  196. 196三、什么是公平锁
  197. 197四、公平锁实现
  198. 1981.3 代码讲解
  199. 1992. MCSLock
  200. 2002.1 代码讲解
  201. 2013. TicketLock
  202. 2023.3 代码讲解
  203. 203二、ReentrantLock 和 AQS
  204. 2042. 写一个简单的 AQS 同步类
  205. 2052.2 单元测试
  206. 2063. CAS 介绍
  207. 2074.2 lock
  208. 2084.3 compareAndSetState
  209. 2094.4 (AQS)acquire
  210. 2104.6 addWaiter
  211. 2114.7 acquireQueued
  212. 2124.8 parkAndCheckInterrupt
  213. 213第 5 节:AQS 共享锁,Semaphore、CountDownLatch
  214. 2142. Semaphore 共享锁使用
  215. 2153. Semaphore 源码分析
  216. 2163.3 acquire 释放信号量
  217. 2173.5 非公平锁实现
  218. 2183.6 获取信号量失败,加入同步等待队列
  219. 2194. CountDownLatch 共享锁使用
  220. 220三、总结
  221. 221第 4 章 多线程(4节)
  222. 222二、线程启动分析
  223. 223三、线程启动过程
  224. 2242. Java 层面 Thread 启动
  225. 2252.2 start0() 本地方法
  226. 2263. JVM 创建线程
  227. 2273.2 JavaThread
  228. 2283.3 os::create_thread
  229. 2293.4 java_start
  230. 2304. JVM 启动线程
  231. 2314.2 os::start_thread(thread)
  232. 2324.3 pd_start_thread(thread)
  233. 233四、总结
  234. 234第 2 节:Thread,状态转换、方法使用、原理分析
  235. 235三、Thread 状态测试
  236. 2364. WAITING
  237. 2375. TIMED_WAITING
  238. 2386. TERMINATED
  239. 2392. wait & notify
  240. 2403. join
  241. 241五、总结
  242. 242第 3 节:ThreadPoolExecutor
  243. 243二、线程池讲解
  244. 2442.2 实现代码
  245. 2453. 线程池源码分析
  246. 2463.2 高3位与低29位
  247. 2473.2 线程池状态
  248. 2483.3 提交线程(execute)
  249. 2493.5 添加执行任务(addWorker)
  250. 2503.6 执行线程(runWorker)
  251. 2513.7 队列获取任务(getTask)
  252. 252三、总结
  253. 253第 4 节:线程池讲解以及JVMTI监控
  254. 2542. newSingleThreadExecutor
  255. 2553. newCachedThreadPool
  256. 2564. newScheduledThreadPool
  257. 257三、线程池使用场景说明
  258. 258四、获取线程池监控信息
  259. 2592. 基于IVMTI方式监控
  260. 2602.1 先做一个监控例子
  261. 2612.2 扩展线程监控
  262. 262五、总结
  263. 263第 5 章 JVM 虚拟机(5节)
  264. 264三、JDK 目录结构和作用
  265. 265四、JDK 是什么?
  266. 266五、JRE 是什么?
  267. 267六、JVM 是什么?
  268. 2682. JVM 结构和执行器
  269. 269第 2 节:JVM 类加载实践
  270. 270二、类加载过程描述
  271. 271三、写个代码加载下
  272. 2722. 代码讲解
  273. 2732.3 压缩包形式路径(ZipEntry)
  274. 2742.4 混合形式路径(CompositeEntry)
  275. 2752.5 通配符类型路径(WildcardEntry)
  276. 2762.6 类路径解析(Classpath)
  277. 2772.7 加载类测试验证
  278. 278四、解析字节码文件
  279. 2793. 解析版本号信息
  280. 2804. 解析全部内容对照
  281. 281五、总结
  282. 282第 3 节:JVM 内存模型
  283. 283三、内存模型各区域介绍
  284. 2842. Java虚拟机栈
  285. 2853. 本地方法栈
  286. 2865. 常量池
  287. 2872. 重点代码
  288. 288五、jconsole监测元空间溢出
  289. 2892. 调整元空间大小
  290. 2904.2 测试结果
  291. 2914.3 监控截图
  292. 292第 4 节:JVM 故障处理工具
  293. 293二、基础故障处理工具
  294. 2941.2 jps -l,输出当前运行类全称
  295. 2951.4 jps -v,输出虚拟机进程启动时JVM参数[-Xms24m -Xmx256m]
  296. 2962. jcmd 虚拟机诊断命令
  297. 2972.1 jcmd pid VM.flags,查看JVM启动参数
  298. 2982.5 jcmd pid Thread.print,查看线程堆栈信息
  299. 2992.7 jcmd pid GC.heap_dump 路径,导出heap dump文件
  300. 3003. jinfo Java配置信息工具
  301. 3014.01 jstat -class,类加载统计
  302. 3024.04 jstat -gccapacity,堆内存统计
  303. 3034.06 jstat -gcnew,新生代垃圾回收统计
  304. 3044.08 jstat -gcoldcapacity,老年代内存统计
  305. 3054.11 jstat -printcompilation,JVM编译方法统计
  306. 3065.1 jmap,打印共享对象映射
  307. 3075.3 jmap -clstats,打印加载类
  308. 3085.4 jmap -dump,堆转储文件
  309. 3097. jstack Java堆栈跟踪工具
  310. 310三、可视化故障处理工具
  311. 3112. VisualVM,多合故障处理工具
  312. 312四、总结
  313. 313第 5 节:GC 垃圾回收
  314. 314三、JVM 垃圾回收知识框架
  315. 3151. 判断对象已死
  316. 3162. 垃圾回收算法
  317. 3172.2 标记-复制算法(mark-copy)
  318. 3183. 垃圾回收器
  319. 3193.2 老年代
  320. 320结尾