java.lang.HashMap类

java.lang.HashMap类


(一)底层数据结构

1.JDK8之前

数组 + 链表

  1. key.hashCode()经过扰动函数处理过后得到hash

    JDK7扰动函数扰动了4次,性能会差一些。

1
2
3
4
static final int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
  1. hash & (n-1)(相当于hash % nn是数组长度,取值需要是2的n次方),得到当前元素存储的位置

  2. 如果当前位置已有元素,判断key是否相同,相同则覆盖;hash相同、key不相同则说明是哈希冲突,通过加链解决

2.JDK8之后

  • 数组 + 链表/红黑树
  • 当链表长度大于阈值(默认是8),将链表转为红黑树,以减少搜索时间
  1. key.hashCode()经过扰动函数处理过后得到hash

    JDK8的扰动函数:

hashCode()高16位与低16位异或,目的是为了防止一些实现较差的hashCode()方法,让元素分布更均匀,减少碰撞。

1
2
3
4
5
6
static final int hash(Object key) {
int h;
//key.hashCode()经过扰动函数处理后得到的就是hash值
//“>>>”:无符号右移,忽略符号位,空位以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  1. hash & (n-1)(相当于hash % nn是数组长度,取值需要是2的次方),得到当前元素存储的位置

  2. 如果当前位置已有元素,判断key是否相同,相同则覆盖;hash相同、key不相同则说明是哈希冲突,通过加链解决;当链表长度超过阈值(默认8)会转为红黑树

(1)类属性

①常量
  • 默认初始容量:16

  • 最大容量:2^30

    容量即数组长度n,必须是2的次方,方便hash & (n - 1)操作。
    但是由于数组长度不能超过Integer.MAX_VALUE = 2^31 -1,所以最大容量只能是2^30,不能达到2^31

  • 负载因子:float loadFactor

  • 默认填充因子(负载因子):0.75

    负载因子(Load Factor)描述的是元素的稀疏程度;

  • 负载因子越大(趋近于1),元素越密集,空间利用率就越低,但是相应地,链表长度就越长(或红黑树高度越高),导致搜索效率降低;*

  • 负载因子越小(趋近于0),元素越稀疏,链表长度就越短(或红黑树高度越低),搜索效率越高,但是相应的,空间利用率就越小。*
    默认值0.75是官方给出的一个比较好的临界值。

  • 链表转红黑树长度:8

  • 红黑树还原为链表高度:6

  • 最小红黑树容量:2^6 = 64

②变量
  • 存储元素的数组:Node<k, v>[] table
  • 存储具体元素的集:Set<map.entry<k,v>> entrySet
  • 实际存放元素的个数:int size
  • 每次扩容和更改HashMap的计数器:int modCound
  • 临界值:int threshold

    临界值 = 容量 x 负载因子
    默认容量16,默认负载因子0.75,所以临界值初始值就是12。

当实际大小超过临界值时,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
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
//序列号
private static final long serialVersionUID = 362498820763181265L;
//默认初始容量:16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量:2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认填充因子(负载因子):0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当链表长度超过8会转为红黑树
static final int TREEIFY_THRESHOLD = 8;
//当红黑树高度小于6会重新转为链表
static final int UNTREEIFY_THRESHOLD = 6;
//最小红黑树容量:即2^6 = 64
static final int MIN_TREEIFY_CAPACITY = 64;
//存储元素的数组,长度总是2的次方
transient Node<k, v>[] table;
//存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
//实际存放元素的个数
transient int size;
//每次扩容和更改HashMap的计数器
transient int modCount;
//临界值 = 容量 x 负载因子
int threshold;
//负载因子
final float loadFactor;
}

(2)链表节点类(Node

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
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; //哈希值,用于比较两key是否相同
final K key; //键
V value; //值
Node<K, V> next;//下一个节点
//Constructor
//getter: key、value

//toString
public final String toString() {
return key + "=" + value;
}

//hashCode:key的hashCode异或上value的hashCode()
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

//equals
public final boolean equals(Object o) {
if(o == this) return true; //1.内存地址相同返回true
if(o instanceof Map.Entry) {
Map.Entry<?, ?> e = (Map.Entry<?, ?>)o;
if(Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue())) return true;
//2.key和value都相同,返回true
}
return false;
}

//setter
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue; //返回旧值
}
}

(3)红黑树节点类(TreeNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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> pre; //删除时需要取消下一个链接
boolean red; //是否是红色节点

TreeNode(int hash, K key, V value, Node<K, V> next){
super(hash, key, value, next);
}

//返回root
final TreeNode<K, V> root() {
for(TreeNode<K, V> r = this, p;;) {
if((p = r.parent) == null) return r;
r = p;
}
}

}

(二)API

1.构造方法

  1. HashMap():默认构造函数,负载因子为DEFAULT_LOAD_FACTOR
  2. HashMap(int initalCapacity):指定初始容量的HashMap
  3. HashMap(int initCapacity, float loadFactor):指定初始容量和负载因子的HashMap
  4. HashMap(Map<? extends K, ? extends V>):包含另一个Map的构造函数
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
//默认构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}

//指定初始容量的构造函数
public HashMap(int initCapacity) {
this(initalCapacity, DEFAULT_LOAD_FACTOR);
}

//指定初始容量和负载因子的构造函数
public HashMap(int initCapacity, float loadFactor) {
//初始容量不能为负数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//初始容量大于最大容量,取最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子不能为负,也不能为NaN
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//【tableSizeFor():初始化阈值,同时会保证数组长度是一个2的幂次方】
this.threshold = tableSizeFor(initialCapacity);
}

//包含另一个Map的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFacotor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

//将Map插入HashMap
final void putMapEnties(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if(s > 0) {
//判断元素数组table是否已经初始化
//没有初始化就初始化
if(table == null) {
float ft = ((float) s / loadFactor) + 1.0F;
//容量不超过最大容量
int t = (ft < (float)MAXIMUM_CAPACITY) ?
(int) ft : MAXIMUM_CAPACITY;
//如果实际容量超过阈值,初始化阈值
if(t > threshold) threshold = tableSizeFor(t);
}
//元素数组table已经初始化,且m元素大于阈值
else if(s > threshold) resize(); //扩容
//将m中所有元素添加到HashMap中
for(Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//【putVal()具体用法见下一节】
putVal(hash(key), key, value, false, evict);
}
}
}

//返回一个能够容纳cap的最小的2的幂次方
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2.put:添加元素

  • public V put(K key, V value)

  1. 如果存储元素的数组没有初始化,则需要resize()初始化。
  2. 如果定位到的数组位置没有元素,直接插入;
  3. 如果定位到的数组位置有元素,比较两者的key
  4. 如果key相同则直接覆盖;
  5. 如果key不同,判断p是否是一个树节点:
  6. 如果p是一个树节点,调用e = ((TreeNode<K, V>)p).putTreeVal(this, tab, hash, key, value)将元素插入;
  7. 如果p是一个链表节点,遍历链表,尾插
  8. 插入后如果链表长度超过阈值,转变为红黑树
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
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

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,则初始化
if((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//hash对数组长度取模,确认在数组中的位置
//如果为空,直接插入
if((p = tab[i = hash & (n - 1)]) == 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;
//key不相同,hash冲突,是红黑树节点
else if(p instanceof TreeNode)
e = ((TreeNode<K, V>)p).putTreeVal(this, tab, hash, key, value);
//key不相同,hash冲突,是链表节点
else{
//尾插
for (int binCount = 0; ; ++binCount) {
//到达尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度超过阈值,转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);
break;
}
//判断链表中节点的key值是否与插入元素key相等
if (e.hash == hash && (k = e.key) == key
|| (key != null && key.equals(k)))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //新值替换旧值
//访问后回调
afterNodeAccess(e);
return oldValue; //返回旧值
}
}
++modCound;
if (++size > threshold) resize();
afterNodeInsertion(evict);
return null;
}

如果HashMap实际容量(初始容量 x 负载因子)超过了阈值,就会进行扩容(每次扩容为原来的2倍)。扩容伴随着重新hash分配,会遍历整个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
75
76
77
78
79
80
81
//resize
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值不能扩容,只能任由碰撞
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值,就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
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) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
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;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

3.get:获取元素

  • public V get(Object key):通过key获取value
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
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 元素等于数组元素
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 元素不等于数组元素,但数组该位置存在链表或红黑树
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

(三)HashMap的遍历

  1. 获取所有key:map.keySet()
  2. 获取所有value:map.values()
  3. 获取所有key/value:map.entrySet()

    如果是需要用到key/value的情况,最好是直接通过entrySet()获取,而不是获取keySet()然后再调用get(key)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
HashMap<String, String> map = new HashMap<String, String>();
//获取HashMap中的所有key,通过key获取value
Set<String> keys = map.keySet();
for (String key : keys) {
System.out.println("key:" + key + " ,value:" + map.get(key));
}
//获取HashMap中的所有value
Collection<String> values = map.values();
for(String value : values) {
System.out.println("value:" + value);
}
//获取HashMap中所有的key/value,以entry的形式
Set<java.util.Map.Entry<String, String>> entrys = map.entrySet();
for(java.util.Map.Entry<String, String> entry : entrys) {
System.out.println("key:" + entry.getKey() + " ,value:" + entry.getValue());
}

(四)常见问题

1.为什么HashMap的大小一定要是2的幂次方?

参考位运算-对2的整数次幂取模

HashMap中,存储一个键值对,首先会将key.hashCode()经过扰动函数处理得到hash值,然后hash值对数组长度(n)取模,以此来确定键值对在Entry数组中的下标 —— 而我们知道,如果n是2的幂次方,那么hash % n可以用hash & (n - 1)替代,从而大大提高效率。


2.HashMap扩容需要重新计算hash值吗?

当然要!扩容时HashMap底层数组长度变了,需要重新让hashCode()对数组长度取模,以确定元素位置


3.为什么HashTable不支持null K/V,而HashMap支持?

  1. HashTableConcurrentHashMap采用的是fail-safe机制,每次读到的数据不一定是最新的 —— 如果你使用null值就无法判断key是不存在还是为空,因为你无法再次调用contain(key)key是否存在进行判断,所以这两者在我们put(null)时会直接抛出NullPointerException
  2. HashMap在我们put(null)时做了特殊处理,如果对象是null会将hash值取0
1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode() ) ^ (h >>> 16);
}

(五)应用

以空间换时间:以存储为代价换取查询速度

  • HashMap空间复杂度O(N)
  • HashMap时间复杂度O(1)

比如我们要从一个数组中找到和为target的两数的下标,如果暴力需要两次遍历,时间复杂度O(N^2)

1
2
3
4
5
6
7
8
9
10
public int twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length; i++) {
for(int j = 0; j < nums.length; j++) {
if(nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
throw new IllegalArgumentException("No Solution");
}

如果我们采用HashMap进行存储的话,我们就可以将查询时间复杂度简化到O(1),相应的只需要O(N)的空间复杂度。

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
//两次遍历版本:
//第一次遍历 —— 将nums[i]作为key,i作为value存入HashMap
//第二次遍历 —— 查找
public int[] twoSumWithHM(int[] nums, int target) {
//key : nums[i],数值; value: i,下标
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for(int i = 0; i < nums.length; i++) {
//需要查找的数
int want = target - nums[i];
if(map.containsKey(want)
&& map.get(want) != i) { //不能是nums[i]本身
return new int[]{i, map.get(want)};
}
}
throw new IllegalArgumentException("No Solution");
}

//优化版本:【在一次遍历中完成存储和查找】
public int[] twoSumWithHMBetter(int[] nums, int target) {
//key : nums[i],数值; value: i,下标
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++) {
//直接判断需要查找的数是否存在
int want = target - nums[i];
if(map.containsKey(want)) { //先查后存,不需要判断是否等于自身
return new int[]{map.get(want), i};
}
//存储
map.put(nums[i], i);
}
throw new IllegalArgumentException("No Solution");
}
-------------本文结束感谢您的阅读-------------

本文标题:java.lang.HashMap类

文章作者:DragonBaby308

发布时间:2019年08月24日 - 20:40

最后更新:2020年01月16日 - 22:28

原始链接:http://www.dragonbaby308.com/java-util-HashMap/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%