1.概述
HashMap位于java.util
包中,HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用null键和null值,因为key不允许重复,因此只能有一个键为null,另外HashMap不能保证放入元素的顺序,它是无序的,和放入的顺序并不能相同。HashMap是线程不安全的。它的底层为哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。JDK1.8之后,当链表长度超过 8 时,链表转换为红黑树。
HashMap主要属性:
1 | public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable { |
2.Node
JDK 1.8采用的是Node数组,实质上还是Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next
指针,可以连接下一个Entry实体,以此来解决Hash冲突的问题。
一个桶中链表的长度<8时:
一个桶中链表的长度>=8时:
数组存储区间是连续的,占用内存严重,故空间复杂度很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;
链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(n)。链表的特点是:寻址困难,插入和删除容易。
HashMap的设计正是分别结合了数组和链表的优点。
1 | static class Node<K,V> implements Map.Entry<K,V> { |
3.hash算法
首先获取对象的hashCode()值,然后将hashCode值右移16位,然后将右移后的值与原来的hashCode做异或(^)运算,返回结果。(其中h>>>16,在JDK1.8中,优化了高位运算的算法,使用了零扩展,无论正数还是负数,都在高位插入0)
1 | static final int hash(Object key) { |
4.put()
HashMap并没有直接提供putVal接口给用户调用,而是提供的put方法,而put方法就是通过putVal来插入元素的。
- 判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
- 根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向6,如果table[i]不为空,转向3;
- 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向4,这里的相同指的是hashCode以及equals;
- 判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向5;
- 遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
- 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。HashMap的数据存储实现流程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//put函数的核心处理函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//HashMap是懒加载,所有的put先检查table数组是否已经初始化,没有初始化则进行扩容数组初始化table数组,保证table数组一定初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过hash算法(n - 1) & hash找到数组下标得到数组元素,为空则新建
//(n-1)&hash就等价于hash%n。&运算的效率高于%运算。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//找到数组元素,hash相等同时key相等,则直接覆盖,执行赋值操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// hash值不相等,即key不相等
//判断链表是否是红黑树
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) {
//在尾部插入结点(JDK1.8之前采用头插法,JDK1.8之后采用尾插法,使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环)
p.next = newNode(hash, key, value, null);
//当链表长度超过8(阈值),就会将链表便转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//记录修改次数
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} - 根据key计算得到key.hash =
(h = k.hashCode()) ^ (h >>> 16)
; - 根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1),这样就找到该key的存放位置了
① 如果该位置没有数据,用该数据新生成一个节点保存新数据,返回null;
② 如果该位置有数据是一个红黑树,那么执行相应的插入 / 更新操作;
③ 如果该位置有数据是一个链表,分两种情况一是该链表没有这个节点,另一个是该链表上有这个节点,注意这里判断的依据是key.hash是否一样:
如果该链表没有这个节点,那么采用尾插法新增节点保存新数据,返回null;如果该链表已经有这个节点了,那么找到该节点并更新新数据,返回老数据。
注意:
HashMap的put会返回key的上一次保存的数据,比如:
1 | HashMap<String, String> map = new HashMap<String, String>(); |
5.get()
HashMap同样并没有直接提供getNode接口给用户调用,而是提供的get方法,而get方法就是通过getNode来取得元素的。
1 | public V get(Object key) { |
基本流程:
- 根据key计算hash;
- 检查数组是否为空,为空返回null;
- 根据hash计算bucket位置,如果bucket第一个元素是目标元素,直接返回。否则执行4;
- 如果bucket上元素大于1并且是树结构,则执行树查找。否则执行5;
- 如果是链表结构,则遍历寻找目标
6.resize()
1 | final Node<K,V>[] resize() { |
7.面试题
- Object若不重写hashcode()的话,hashcode是如何计算出来的?
Object的hashcode()方法是本地方法,该方法直接返回对象的内存地址,如果不重写hashcode(),则任何对象的hashcode都不相等。(然而hashmap想让部分值的hashcoe值相等,所以需要重写) - 为什么重写equals()还要重写hashcode()?
HashMap中比较key先求出key的hashcode(),比较其值是否相等,相等则比较equals(),若相等则认为它们是相等的,若equals()不相等则认为它们是不相等的。
如果只重写equals()不重写hashcode(),就会导致相同的key值被认为不同(如果不重写hashcode(),则任何对象的hashcode都不相等),就会在HashMap中存储相同的key值(map中key值不能相同)。
①如果两个对象相同(equals()比较返回true),那么它们的hashcode值一定相同;
②如果两个对象的hashcode值相同,它们并不一定相同(equals()比较返回false)