HashMap 数据结构非常重要,经常被用来面试。因为它综合了数组以及链表的知识,还有非常重要的hash算法,在以后的工作中也经常被用到,其中还有很多非常高效的算法。但是hashMap对于很多人来说比较困难,可能会用,但是并不清楚怎么实现,或者不清楚他的执行逻辑。 我就通过语句的执行以及函数的调用顺序来一步步揭开 hashMap的面纱,跟着我的思路走,至少hashMap的基本逻辑就知道了,校招相关的面试基本也能答得上来 注释应该非常非常细了,因为我基本判断语句以及一些不清楚的变量逻辑都进行了中文注释 文件地址在我的 github 上(目前只更新了put和get):https://github.com/leosanqing/StructAndAlgorithm/tree/master/Struct/hashMapDemo github上原文点击 『阅读原文』获取
Node
命名,但是我使用的是 Entry
,不过逻辑还是1.8的逻辑存放在我的 github 上:
https://github.com/leosanqing/StructAndAlgorithm/tree/master/Struct/hashMapDemo
类似于这种格式
当然是为了快,为了效率
数组在知道下标之后查询速度尤其快,O(1)的时间复杂度
链表在增删的时候速度非常快,找到位置后(前提),处理只需要O(1)的时间复杂度,因为不需要移动数据的位置,只需要更改指向的地址即可。但是链表在遍历对比的时候非常慢,时间复杂度为O(n),所以用来做 哈希冲突时的解决方法
所以查询一个数据的时间复杂度为 O(1)+O(n)。不过因为哈希算法的非常巧妙,会让冲突尽可能地均匀分布,所以链一般极其短。所以后面遍历链表的时间可以忽略不计,而且在 JDK8 之后,如果冲突的链表长度大于 8,那么就会转化为 红黑树,他的遍历的时间复杂度为O(log n)
数组的话,源码中使用的是 table
命名,你也可以称之为 桶
1Node[] table;
链表的话,JDK 1.7中使用的是 Entry
,JDK1.8采用的是 Node
命名。基本一样,只是名字不同,结构定义如下.
(我是按照1.7的命名, 不过其他逻辑是1.8的)
1/**
2 * Entry 类 为map中基本的单元
3 *
4 * key 为键,value 为值
5 * next 是在哈希冲突时,指向的下一个 Entry
6 * h 为传入的hash值,源码中为 hash
7 */
8static class Entry{
9 Object key;
10 Object value;
11 Entry next;
12 int h;
13}
1// 初始默认的数组容量
2static final int INIT_CAPACITY = 1<<4;
3//数组最大的容量,因为 数组设置为 2的整次方倍,而 32 次方为负数,所以最大只能为 1 << 30,即2的31次方
4static final int MAX_CAPACITY = 1<<30;
5// 默认的装填因子
6static final float DEFAULT_LOADFACTOR = 0.75f;
7
8// table 桶中的个数--数组的大小;
9int size;
10
11// 修改次数
12int modCount;
13
14// 扩容的阈值, capacity * load factor
15int threshold;
16
17// 装填因子
18float loadFactor;
如果你看懂了这个过程,那么基本上 HashMap 的主要逻辑就算是基本理解了
table[0]
的位置,如果不为空,经过运算确定其在table
中的下标key
值是否相等,相等的话,直接覆盖value
,不相等的话遍历链表(红黑树),并插入到链表最后稍微详细些的步骤看下方思维导图,同样缩进的为 if-else 关系
还有的细节没有写,待会儿跟着源码再细讲,我就跟着源码的调用顺序分析
1import java.util.HashMap;
2
3public class Test {
4 public static void main(String[] args) {
5 HashMap hashMap = new HashMap();
6 hashMap.put("name","zhangSan");
7
8 }
9}
1public MyHashMap(int initCapacity,float loadFactor) {
2 if(initCapacity<0)
3 throw new IllegalArgumentException("初始化容量失败: "+
4 initCapacity);
5 if(initCapacity>= MAX_CAPACITY)
6 initCapacity= MAX_CAPACITY;
7 if(loadFactor<=0||Float.isNaN(loadFactor))
8 throw new IllegalArgumentException("装填因子不合法"+
9 loadFactor);
10 this.loadFactor=loadFactor;
11 this.threshold=tableSizeFor(initCapacity);
12
13 }
14public MyHashMap(int initCapacity) {
15 this(initCapacity,DEFAULT_LOADFACTOR);
16}
17
18/**
19 * 无参的,全部默认
20 */
21public MyHashMap() {
22 this.loadFactor=DEFAULT_LOADFACTOR;
23}
24
25
26public MyHashMap(Map m){
27 this.loadFactor=DEFAULT_LOADFACTOR;
28
29}
如果没有传入参数,他就会调用无参的构造器,那么默认的长度为 16,DEFAULT_INITIAL_CAPACITY
,默认的装填因子为 0.75,DEFAULT_LOAD_FACTOR
,传入范围(0,1];
注意:这个时候,数组还没有初始化,仅仅是定义了一个Entry类型的数组
执行hashMap.put("name","zhangSan")
首先他在源码中是这样的,他又调用了putVal
函数,专门存入元素的函数(ps:源码 611行)
1public V put(K key, V value) {
2 return putVal(hash(key), key, value, false, true);
3}
他传入了5个值,但是我们先重点关注前三个值,第一个是要存入的key的hash
值,第二个是key,第三个是value,至于K,V泛型如果不了解,你可以理解为 Object类型,如果按照测试的语句,你就可以把它当成 String
类型。
这个put函数,他有返回值,返回值是null,或者oldValue,看了下面的putValue
函数你就知道了
传入这个参数是为了创建节点node以及计算索引时用
源码(第337 行)
1static final int hash(Object key) {
2 int h;
3 // 将key 的高16位和低16位进行异或
4 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
5}
这个也是 JDK 1.8的改进,1.7不是这样的。
主要是从速度、功效、质量来考虑的,这么做可以在数组table的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中(为了是分布更均匀),同时不会有太大的开销。
1private Object putVal(int hash, Object key, Object value, boolean onlyIfAbsent, boolean evict) {
2 Entry[] tab;
3 Entry p;
4 int n,i;
5 // 如果第一次 进行存放数据,进行初始化,table 被延迟到进行数据存放时才初始化
6 if((tab = table) == null || (n = table.length)==0){
7 n = (tab = resize()).length;
8 }
9 if((p = table[i = ((n - 1) & hash)]) == null){
10 tab[i] = newEntry(hash,key,value,null);
11 }
12
13 else {
14 Entry e;
15 Object k;
16 // 如果 key 相同,那么就直接将 value 覆盖
17 // 为什么要比较这么多次
18
19 // 1.首先判断 哈希值是否相同
20 if(p.h == hash &&
21 // 2.判断两个key是否相等,使用 '==' 是非字符串情况,之比较两个的内容,使用'equals' 是针对字符串
22 (((k = p.key) == key) || (key != null && key.equals(k))))
23 // 覆盖value值
24 e = p;
25
26 // 这个是树的情况
27 //else if(p instance of TreeNode)
28
29 // 链
30 else{
31 for(int binCount=0;;++binCount){
32 // 遍历到最后,插入
33 if((e = p.next) == null){
34 p.next = newEntry(hash,key,value,null);
35
36 /*
37 如果 binCount >=转化树的阈值-1 ,则将链表转化为树
38
39 if(binCount >= TREEIFY_THRESHOLD-1)
40 treeifyBin(tab,hash);
41
42 */
43 break;
44 }
45 if(p.h == hash &&
46 (((k = p.key) == key) || (key != null && key.equals(k))))
47 break;
48 // 移动到下一个
49 p = e;
50 }
51
52
53
54 // 如果有相应的映射,即key相同
55 if(e != null){
56 Object oldValue = e.value;
57 if(!onlyIfAbsent || oldValue == null)
58 e.value = value;
59 return oldValue;
60 }
61
62 }
63
64 }
65 // 修改次数 ++
66 ++ modCount;
67
68 // 大于阈值就扩容
69 if(++size >threshold)
70 resize();
71
72 //afterNodeInsertion(evict);
73
74 return null;
75
76}
看了上面的源码分析你就能解决上面的疑问,put函数有返回值,返回值为null
或者oldValue
。
先记住答案:当他不产生覆盖的时候,返回null;当他产生覆盖的时候返回 oldVal,即原来被覆盖的值
我们先进行测试,你就大概知道意思了
1import java.util.HashMap;
2
3public class Test {
4 public static void main(String[] args) {
5 HashMap hashMap = new HashMap();
6 hashMap.put("name","张三");
7
8 Object oldValue1 = hashMap.put("name","李四");
9 Object oldValue2 = hashMap.put("age",18);
10 System.out.println("oldValue = " + oldValue1);
11 System.out.println("oldValue2 = " + oldValue2);
12 }
13}
我想现在你应该清楚了,当输入的key的内容相同,hash值也相同的时候,他就会覆盖之前的Value值,并且返回被覆盖前的value值。(假设输入的只是String类型,如果是自定义的对象,需要重写 hashCode 和 equals 方法)
这个的关键代码在上面函数的++modCount
一行上面,我有注释
1//如果有相应的映射,即key相同
2if(e != null){
3 Object oldValue = e.value;
4 if(!onlyIfAbsent || oldValue == null)
5 e.value = value;
6 return oldValue;
7}
首先要判断table数组是否初始化了,即这条语句if ((tab = table) == null || (n = tab.length) == 0)
,
resize
方法(后面分析).可以直接看索引为 `resize函数`的内容将 key 的 hash 值和table.length-1
相与,相与的结果就是要存入的元素的table中的 位置tab[(n - 1) & hash]
。
这个时候看源码,它分为两种情况:
第一种:相应的索引上没有元素(只有这个时候 size才++,相应索引上有元素,size是不会 ++ 的)
1// 如果table 数组的相应的索引上没有元素,那么直接创建一个新的节点
2if ((p = tab[i = (n - 1) & hash]) == null)
3 tab[i] = newNode(hash, key, value, null);
4// 修改次数++
5++modCount;
6// 判断是否需要扩容
7if (++size > threshold)
8 resize();
9afterNodeInsertion(evict);
10return null;
现在知道啥时候返回 null了吧
第二种:相应的索引上有元素
这个时候就要判断元素的key是否相等
if(p.h == hash &&(((k = p.key) == key) || (key != null && key.equals(k))))
1else {
2 Entry e;
3 Object k;
4 // 如果 key 相同,那么就直接将 value 覆盖
5 // 为什么要比较这么多次
6
7 // 1.首先判断 哈希值是否相同
8 if(p.h == hash &&
9 // 2.判断两个key是否相等,使用 '==' 是非字符串情况,之比较两个的内容,使用'equals' 是针对字符串
10 (((k = p.key) == key) || (key != null && key.equals(k))))
11 // 覆盖value值
12 e = p;
13
14 // 这个是树的情况
15 //else if(p instance of TreeNode)
16
17 // 链
18 else{
19 for(int binCount=0;;++binCount){
20 // 遍历到最后,插入
21 if((e = p.next) == null){
22 p.next = newEntry(hash,key,value,null);
23
24 /*
25 如果 binCount > 转化树的阈值 ,则将链表转化为树
26
27 if(binCount >= TREEIFY_THRESHOLD-1)
28 treeifyBin(tab,hash);
29
30 */
31 break;
32 }
33 if(p.h == hash &&
34 (((k = p.key) == key) || (key != null && key.equals(k))))
35 break;
36 // 移动到下一个
37 p = e;
38 }
39
40
41 // 如果有相应的映射,即
42 if(e != null){
43 Object oldValue = e.value;
44 if(!onlyIfAbsent || oldValue == null)
45 e.value = value;
46 return oldValue;
47 }
48 }
49}
这就是返回 oldValue的情况,当然上面的也有情况并不会返回oldValue
这个是进行扩容的函数,也是非常重要的,要确保每次扩容前后容量大小都是2的n次方
。并且在JDK 1.8中,对这个函数进行了优化,使得算法非常的高效
putVal
函数中
1if (++size > threshold) 2 resize();忽略了树的逻辑,只有相应的条件
1final Entry[] resize() {
2 // 定义旧的数组为 Entry 类型的数组,oldTab
3 Entry[] oldTab = table;
4 // 如果oldTab==null 则返回 0,否则返回数组大小
5 int oldCap = (oldTab==null) ? 0 : oldTab.length;
6
7 int oldThreshold = threshold;
8
9 int newCap=0,newThreshold=0;
10
11 // 说明已经不是第一次 扩容,那么已经初始化过,容量一定是 2的n次方,所以可以直接位运算
12 if(oldCap>0){
13 // 如果 原来的数组大小已经大于等于了最大值,那么阈值设置为 Integer的最大值,即不会再进行扩容
14 if(oldCap >= MAX_CAPACITY){
15 threshold = Integer.MAX_VALUE;
16 return oldTab;
17 }
18
19 // 因此已经不是第一次扩容,一定是2的n次方
20 else if ((newCap = oldCap << 1) < MAX_CAPACITY &&
21 oldCap >= INIT_CAPACITY)
22
23 newThreshold = oldThreshold << 1;
24
25 }
26 // 如果oldThreshold > 0,并且oldCap == 0,说明是还没有进行调用resize方法。
27 // 说明输入了初始值,且oldThreshold为 比输入值大的最小的2的n次方
28 // 那么就把 oldThreshold 的值赋给 newCap ,因为这个值现在为 比输入值大的最小的2的n次方
29 else if(oldThreshold>0)
30 newCap = oldThreshold;
31
32 // 满足这个条件只有调用无参构造函数,注意只有;
33 else{
34 newCap = INIT_CAPACITY;
35 newThreshold = (int) (INIT_CAPACITY * DEFAULT_LOADFACTOR);
36 }
37
38 if(newThreshold == 0){
39
40 float ft = (float) (newCap * loadFactor);
41 newThreshold =(newCap < MAX_CAPACITY && ft < (float) MAX_CAPACITY ?
42 (int )ft : Integer.MAX_VALUE);
43 }
44
45 threshold = newThreshold;
46
47 Entry newTable[] = new Entry[newCap];
48 table=newTable;
49
50 // 将原来数组中的所有元素都 copy进新的数组
51 if(oldTab != null){
52 for (int j = 0; j < oldCap; j++) {
53 Entry e;
54
55 if((e = oldTab[j]) != null){
56 oldTab[j] = null;
57
58 // 说明还没有成链,数组上只有一个
59 if(e.next == null){
60 // 重新计算 数组索引 值
61 newTable[e.h & (newCap-1)] = e;
62
63 }
64 // 判断是否为树结构
65 //else if (e instanceof TreeNode)
66
67
68 // 如果不是树,只是链表,即长度还没有大于 8 进化成树
69 else{
70 // 扩容后,如果元素的 index 还是原来的。就使用这个lo前缀的
71 Entry loHead=null, loTail =null;
72
73 // 扩容后 元素index改变,那么就使用 hi前缀开头的
74 Entry hiHead = null, hiTail = null;
75 Entry next;
76 do {
77 next = e.next;
78 if((e.h & oldCap) == 0){
79 // 如果 loTail == null ,说明这个 位置上是第一次添加,没有哈希冲突
80 if(loTail == null)
81 loHead = e;
82 else
83 loTail.next = e;
84 loTail = e;
85 }
86 else{
87 if(hiTail == null)
88 loHead = e;
89 else
90 hiTail.next = e;
91 hiTail = e ;
92 }
93
94 }while ((e = next) != null);
95
96
97 if(loTail != null){
98 loTail.next = null;
99 newTable[j] = loHead;
100 }
101
102 // 新的index 等于原来的 index+oldCap
103 else {
104
105 hiTail.next = null;
106 newTable[j+oldCap] = hiHead;
107 }
108
109 }
110 }
111
112 }
113 }
114
115 return newTable;
116}
1// 将原来数组中的所有元素都 copy进新的数组
2if(oldTab != null){
3 for (int j = 0; j < oldCap; j++) {
4 Entry e;
5
6 if((e = oldTab[j]) != null){
7 oldTab[j] = null;
8
9 // 说明还没有成链,数组上只有一个
10 if(e.next == null){
11 // 重新计算 数组索引 值
12 newTable[e.h & (newCap-1)] = e;
13
14 }
15 // 判断是否为树结构
16 //else if (e instanceof TreeNode)
17
18
19 // 如果不是树,只是链表,即长度还没有大于 8 进化成树
20 else{
21 // 扩容后,如果元素的 index 还是原来的。就使用这个lo前缀的
22 Entry loHead=null, loTail =null;
23
24 // 扩容后 元素index改变,那么就使用 hi前缀开头的
25 Entry hiHead = null, hiTail = null;
26 Entry next;
27 do {
28 next = e.next;
29 //这个非常重要,也比较难懂,将它和原来的长度进行相与,就是判断他的原来的hash的上一个 bit 位是否为 1.下面我再详细说
30 if((e.h & oldCap) == 0){
31 // 如果 loTail == null ,说明这个 位置上是第一次添加,没有哈希冲突
32 if(loTail == null)
33 loHead = e;
34 else
35 loTail.next = e;
36 loTail = e;
37 }
38 else{
39 if(hiTail == null)
40 loHead = e;
41 else
42 hiTail.next = e;
43 hiTail = e ;
44 }
45
46 }while ((e = next) != null);
47
48
49 if(loTail != null){
50 loTail.next = null;
51 newTable[j] = loHead;
52 }
53
54 // 新的index 等于原来的 index+oldCap
55 else {
56
57 hiTail.next = null;
58 newTable[j+oldCap] = hiHead;
59 }
60
61 }
62 }
63
64 }
65}
从上面的代码可以看出来,他遍历数组。将每个元素和原来的数组长度进行与运算,判断是否为 0 如果为0,那么索引位置不变, 如果不为 0,那么索引位置等于 原来的索引+原来的数组长度, 你可能有点纳闷,为啥要这样,请参考下这篇文章。
不过阅读前,我觉得得了解这些前提,
文章链接:https://www.jianshu.com/p/4177dc15d658
上面的这个算法非常重要,也是JDK1.8之后的优化,效率非常高
至此,put一个元素的过程基本就完了,可能还有一些小细节没讲到(应该不太重要,可以自行查看我的注释)
如果你put
方法搞懂了,那么后面的get,contains,remove,iterator 这些基本没有啥大的障碍,这些搞懂,hashMap的 70% 至少都懂了
后面应该还有上述方法的源码分析以及回答一些疑问。
比如"为啥hashMap的数组长度一定是2的n次方",
"当我new HashMap()的时候,输入的初始容量 0,1,2,3,4,5,6。table初始化的值到底为多少"
等等
END