前
HashMap作为kv形式非常常用及方便,所以秉着知其所以然的态度,了解一下内部流程。
数据结构
HashMap的内部是数组+单链表,又叫哈希桶、哈希表、散列表。
看一眼结构图。
图转自: https://www.jianshu.com/p/7dcff1fd05ad
结构图分三块,一一进行拆分:
- 黄色区域:哈希桶中的数组
- 绿色区域:哈希桶中的单链表
- 黑红区域:哈希桶中的红黑树(JDK1.8之后增加) //先不看这个
源码常量
数据结构瞧一眼之后,记下,数组+单链表,后续咱们再把它带入到代码中。
下面介绍一下一些定义:
一共有6个常量,目前只看这三个常量:
- 初始长度: 理解为初始化的时候数组的length == 16
- 最大长度: 桶不能无限大,不然服务炸了
- 扩容比例:每次扩容75%后续
流程
现在按照一个流程来解读hashMap源码, 流程不搞复杂,简简单单的:
- Map map = new HashMap();
- map.put(0, 1);
- map.put(null, 2);
特意挑了两个特殊的key,用这三步来追踪代码。
Map map = new HashMap();
1 | /** |
map.put(0, 1);
对象已经初始化了,现在追踪put方法。
1 | public V put(K key, V value) { |
调用了.putValue()方法,putValue()方法里hash(key), 追:
1 | /** |
分析之前补充一下语法:
^异或运算符: 规则为1^0 = 1 , 1^1 = 0 , 0^1 = 1 , 0^0 = 0, 相同为0 不同为1
>>> 无符号右移运算符: 15 >>> 2 15是00001111 >>> 2 = 00000011; 15 >>> 3 = 00000001
继续,
看hash这个方法, 如果key == null 则赋值0, 所以hashMap,key 可以为空;
所以这个方法的意思是key 进行hash之后 再与 哈希之后的key右移16位, 在进行异或运算。
不深究,这一步是让hash更均匀。
继续,
1 | /** |