HashMap表层分析

HashMap简单分析

是什么?

HashMap是通过一个数组和链表加上红黑树来实现的,通过计算散列码(hash)来决定存储位置,所以查询时只用根据散列码去找到指定的值,速度会比较快

当hash冲突之后 HashMap会自动转换成链表来解决hash冲突,jdk1.8版本之后HashMap的实现方式是数组和链表加红黑树来实现,当链表节点长度达到一定程度(8)时,会自动扩展成红黑树

这里得说一下JDK1.7版本的HashMap

1.7版本有一个缺点,就是当Hash冲突的时候,就会在当前桶上面创建链表,这样链表会越来越长,然后查询的效率会越来越低

1.7版本是采用的头插法,在插入时,新元素会放在链表头部,会改变链表上面的顺醋,如果扩容后,重新计算hash,则有可能会导致循环链路。例A节点的next指向B,B节点next指向C,C节点next指向A。1.8之后全部采用尾插法

思路

如果键值A计算得到的hash为1,放到map里面去,如果键值为B计算得到的hash也为1,此时hash冲突,B就会放到链表的第一个位置,A就会放到后面,如果继续往数组里面添加B,他的hash码一样,他的键值也一样,则会覆盖原来的值

源码

基本属性

数据结构

1
2
3
4
5
6
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}

默认初始的容量 因为底层的数组的实现,所以就是数组的默认大小

1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

数组最大的容量 1073741824

1
static final int MAXIMUM_CAPACITY = 1 << 30;

负载因子为0.75

因为HashMap的容量是有限的,在使用的过程中不断往里面存数据,当数据量达到了 容量\负载因子=16\0.75=12 时就需要进行扩容,而扩容设置的rehash,复制数据等操作,会很影响性能,所以建议提前预估好HashMap的的大小,避免扩容带来的性能损耗。

负载因子越大,Map的容量越大,填满的元素越多,空间利用率高,但是冲突的机会大了,所以链表会越来越长,导致查询的效率降低

反之,负载因子越小,Map的容量越小,很多表中的还没有用就开始扩容,那样冲突的机会小,链表不会很长,查询就相对快一点,但是不断扩容导致容量变大,内存消耗变大

取折中值,就是0.75

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

存放数据的数组

1
transient Node<K,V>[] table;

当前存放数量的大小

1
transient int size;

数组的大小,可以在初始化的时候,显示指定

1
int threshold;

hash表的负载因子,也可以在初始化的时候指定

1
final float loadFactor;

这是JDK1.8之后才有的一个属性,标识链表最大的节点,如果超过阈值,则自动将多余部分维护成红黑树

1
static final int TREEIFY_THRESHOLD = 8;

红黑树节点,转换成链表阈值为6

1
static final int UNTREEIFY_THRESHOLD = 6;

转红黑树时, table的最小长度

1
static final int MIN_TREEIFY_CAPACITY = 64;

构造方法

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
//所有其他字段都默认
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//指定Map大小,一般初始化HashMap都建议指定初始化大小
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//指定初始化大小以及指定负载因子
public HashMap(int initialCapacity, float loadFactor) {
//如果初始容量小于0,抛异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能大于默认的最大值,如果超过,则使用最大
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子不能小于等于0 或不能为其他字符,只能为数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//初始化负载因子
this.loadFactor = loadFactor;
//初始化容量
this.threshold = tableSizeFor(initialCapacity);
}

//指定一个HashMap去初始化
public HashMap(Map<? extends K, ? extends V> m) {
//默认的负载因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
//将m放到HashMap里面
putMapEntries(m, false);
}


final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
//如果table为空
if (table == null) { // pre-size
//算出容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果t大于阈值,则重新初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果m的容量大于阈值,则扩容
else if (s > threshold)
resize();
//将m的值遍历到当前的实例里面
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}

get方法

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
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判断这个hashmap是否为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断当前节点的hash值和key是否和参数里面的key值相等
//如果相等,直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果当前节点的下一个节点不为null
if ((e = first.next) != null) {
//判断当前节点是否为红黑树
if (first instanceof TreeNode)
//如果为红黑树则调用getTreeNode返回去返回
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//这里判断的是如果上面的没有找到,则不断循环到下一级去匹配,
//判断hash和key是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

//如果是树结构,则用这个获取节点
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}

//树的查找方法
//红黑树特点:右节点>根节点>左节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this; //获取当前实例的树
//循环直到p为null
do {
int ph, dir; K pk;
//首先获取到p的左右节点
TreeNode<K,V> pl = p.left, pr = p.right, q;
//如果h比p的hash值小,则将左边的值给到p,然后在去循环左边的值
if ((ph = p.hash) > h)
p = pl;
else if (ph < h) //如果大于的话,则将右边的值给到p,然后在去循环右边的值
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) //如果相等则返回
return p;
else if (pl == null) //如果左边节点为空,则去循环右边的,因为最后一排可能只有一边有值
p = pr;
else if (pr == null) //同上,去循环左边的
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}

put方法

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
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是否为空或者长度为0,如果是则调用resize进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//判断进行hash计算之后的tab索引处是否有值,如果为空则新建一个节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//表示该tab索引出有值
else {
Node<K,V> e; K k;
//依旧判断通过key的hashcode计算出来的hash值是否相等,还有key值是否相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果相等,则证明这个key在Map里面存在,直接覆盖就好了
e = p;
//判断这个节点是否为树节点,如果为树节点,则调用putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//表示p为一个普通的链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//新建一个节点。
//LinkedHashMap会复写这个newNode方法,
//去新建一个带有before和after的双向链表,维护列表顺序
p.next = newNode(hash, key, value, null);
//如果链表数量超过了转换为红黑树的阈值,在转换为红黑树
//treeifyBin里面会判断当前HashMap的长度,长度不足64则只会执行resize,即扩容数组
// 如果超过64则会转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//这里如果找到了相等的节点,则break;
//不然p=e则会不断循环,一直到上面if p.next==nul,把数据插入到链表最后
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//上面给e赋值之后,如果e不为null,则证明该hash处有值,直接覆盖,返回oldvalue
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(); //double threshold
afterNodeInsertion(evict);
return null;
}

resize扩容方法

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//如果oldTab的长度不为空
if (oldCap > 0) {
//长度小于或等于最大的阈值则设置成最大的值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果原来的长度*2小于最大的值并且大于默认的初始值。则将原来的长度扩容
//oldThr << 1 扩容两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果原来表的阈值大于0,则将新表的阈值设置为原来表的阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//如果小于0,则设置成默认,然后默认的负载因子*默认的初始容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新表的阈值为0
if (newThr == 0) {
//新的表的容量*负载因子,得到一个阈值
float ft = (float)newCap * loadFactor;
//如果新表的最大容量小于默认的最大容量,并且 阈值小于做大容量,则取ft,反之取最大
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将当前的阈值设为新表的阈值
threshold = newThr;
//抑制一些警告的关键字
@SuppressWarnings({"rawtypes","unchecked"})
//定义新表的容量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新表设置成当前的表
table = newTab;
//判断老的表是否为空
if (oldTab != null) {
//循环老表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果老表的这个地方不为null
if ((e = oldTab[j]) != null) {
//先将老表的j处设置为null,等待GC回收
oldTab[j] = null;
//e为当前节点
//如果e的下一节点为null
if (e.next == null)
//就将e赋值给新表的
newTab[e.hash & (newCap - 1)] = e;
//如果e是红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-------------本文结束感谢您的阅读-------------
0%