HashMap的底层原理学习

发表于 分类于 ， 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 3 分钟

HashMap的存储结构

JDK 1.8之前

在JDK 1.7，HashMap采用的是数组+链表(头插法) 的存储结构。HashMap通过key的hashCode经过hash方法处理过后得到hash值，然后通过 (n - 1) & hash 判断当前元素存放的位置（n指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存在的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。JDK 1.8之前的hash方法如下：

1
2
3
4
static int hash(int h) {
 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
}

存储结构如下：
在这里插入图片描述

所谓 “拉链法” 就是将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可

JDK 1.8

JDK 1.8之前的HashMapHashMap采用的是数组+链表(头插法)的存储结构，在链表很长时查询效率明显降低o(n)，所以JDK 1.8做了很多优化采用数组+链表(尾插法)+红黑树的存储结构。红黑树的查询时间复杂度是o(log n)。当链表长度大于阈值(默认8)时，如果当前数组的长度小于阈值(默认64)，那么会先进行数组扩容，否则会把链表转化为红黑树，以提高查询效率。当红黑树上的元素个数减少到阈值(默认6)时，会再转为链表。JDK 1.8的hash方法如下：

1
2
3
4
5
6
7
static final int hash(Object key) {
 int h;
 // key.hashCode() 返回散列值也就是hashcode
 // ^ 按位异或
 // >>> ⽆符号右移，忽略符号位，空位都以0补⻬
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

相对于JDK 1.7的hash方法的性能会稍微差一点点，因为扰动了4次。

存储结构如下：
在这里插入图片描述

常用变量

在 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
62
63
64
65
66
67
68
69
70
71
72
73
74
//默认的初始化容量为16，必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。
//若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
//若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

//当红黑树上的元素个数，减少到6个时，就退化为链表
static final int UNTREEIFY_THRESHOLD = 6;

//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。
//这是为了避免，数组扩容和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;

//存放所有Node节点的数组
transient Node<K,V>[] table;

//存放所有的键值对
transient Set<Map.Entry<K,V>> entrySet;

//map中的实际键值对个数，即数组中元素个数
transient int size;

//每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
//当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transient int modCount;

//数组扩容阈值
int threshold;

//加载因子
final float loadFactor;					

//普通单向链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
	//key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置
	final int hash;
	final K key;
	V value;
	//指向单链表的下一个节点
	Node<K,V> next;

	Node(int hash, K key, V value, Node<K,V> next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
}

//转化为红黑树的节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	//当前节点的父节点
	TreeNode<K,V> parent;
	//左孩子节点
	TreeNode<K,V> left;
	//右孩子节点
	TreeNode<K,V> right;
	//指向前一个节点
	TreeNode<K,V> prev;    // needed to unlink next upon deletion
	//当前节点是红色或者黑色的标识
	boolean red;
	TreeNode(int hash, K key, V val, Node<K,V> next) {
		super(hash, key, val, next);
	}
}

小结

  • HashMap是无序且线程不安全的

  • HashMap可以存null键和值，key重复会被覆盖，value可以重复

  • HashMap每次是成倍扩容，且长度都是2的幂次方
    这是为了尽量减少hash冲突考虑的。如果自己传的长度到HashMap构造方法，会返回大于等于参数的最小2次幂。

    1
    HashMap<String,String> map = new HashMap<>(13);//容量为16

  • JDK 1.7的HashMap在多线程环境下可能会出现链表死循环
    原因是采用头插法，多线程推荐使用ConcurrentHashMap(JDK 1.7使用Segment，JDK 1.8使用synchronized和CAS，synchronized只锁定当前链表或红黑树的首节点，效率提升n倍)

参考链接