Java常用类源码——HashMap源码解析(JDK1.8)

Java中存在几大非常有名的集合大佬,例如HashMap, HashTable,TreeMap等等,各大集合大佬们各有特色,那么他们的内部是怎么实现的呢?是不是非常好奇呢?当然本人也是非常好奇的,那么我们就慢慢的一步一步的了解他们吧,下面我们就先来了解HashMap这个集合。

HashMap的基本概述

首先,我们来看Java中对于HashMap的一个说明:

1
2
3
4
5
6
7
* Hash table based implementation of the <tt>Map</tt> interface. This
* implementation provides all of the optional map operations, and permits
* <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
* class is roughly equivalent to <tt>Hashtable</tt>, except that it is
* unsynchronized and permits nulls.) This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.

上面的这一段说明是说:Hash表是实现了 Map 接口的,实现了里面可选择的集合操作,其中允许了键和值为null的情况,HashMap除了不是线程安全和允许键和值可以为null的特殊性外,其他的和HashTable是非常现似的。当向集合中添加元素的时候,是不能保证集合中的元素是有序的,特别的是,它不能保证顺序是恒久不变的。

那么它的实现是怎么样的呢?接着往下看

HashMap的主要数据结构

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {

从上面的源码我们知道HashMap 实现了Map,序列化,可复制的接口,继承了抽象的AbstraMap
但是你们看

1
public abstract class AbstractMap<K,V> implements Map<K,V>

这个是不是比较有趣呢?HashMap不是再实现Map不是多余吗? 但是在Stack Overflow 上解释到:

在语法层面继承接口Map是多余的,这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的,起到了文档的作用

那么元素是怎么在HashMap中储存的呢?
我们从源码中可以找到以下的数据结构:
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
//哈希值,用来定位数组索引位置。
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;
//链表的下一个node
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//根据key和value计算hash值
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判断两个node元素是否是相同的,先判断是不是同一个对象,然后你比较key和value的值。
public final boolean equals(Object o) {
if (o == this)
return 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;
}
return false;
}
}
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
//存储(位桶)的数组
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;

从源码中可以知道,HashMap中有一个非常重要的字段(或者叫做 域),那个就是transient Node<K,V>[] table, 该字段是用于存储元素类型为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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
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);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
.....

JDK1.8版本对以前的HashMap进行了很大的修改,在JDK1.6中,HashMap采用桶+链表的实现,即:使用链表处理冲突,同时同一hash值的链表(Node)都存储在一个链表中,因此当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低,但是在JDK1.8中,HashMap采用桶+链表+红黑树实现,当链表长度超过阙值 8(为什么是8呢?后面会讲到HashMap中的重要属性)的时候,将转化为红黑树,而红黑树的查找和插入的效率都是非常高的,这样大大的减少了查找的时间。
HashMap内存结构图
看了上面的图了之后,记住哦!当链表的长度大于8的时候,将会将链表转换为红黑树。

1
2
3
4
5
6
7
8
9
10
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
//阙值:当数组中的元素大于8的时候,将数组中结构转化为树的结构。
static final int TREEIFY_THRESHOLD = 8;

从上面的三个数据结构可以知道,Node元素实现了Map.Entry,而Map.Entry(K,V)就是定义了Entry的接口,定义了getKey(), getValue(), setValue(), equals()等一些抽象方法。HashMap的内部类Node实现这个接口。从源码中可以看到Node是里面存储的是链表。
有了以上桶+链表+红黑树,那么大致就是HashMap的实现了,首先HaspMap内部是有一个数组(也可以说是一个桶,桶排序算法也用的是这样的桶),里面的元素都是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
38
39
40
41
42
43
44
45
46
47
48
//构建一个带指定初始容量和加载因子的空HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果容量大于指定的容量的话,就使用默认的最大的值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//构造一个带初始容量和加载因子默认的空HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
//构造一个具有初始容量(16)和默认加载因子(0.75)的空HashMap
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//构造一个映射关系与指定Map相同的新HashMap,容量于指定Map容量相同,加载因子默认为0.75
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Returns a power of two size for the given target capacity.
*/
//找出“大于Capacity”的最小的2的幂,使得HashMap表的容量保持为2的次方倍
//算法思想:通过使用逻辑运算来替代取余,这里有一个规律,就是当N为2的次方(Power of two 那么X%N==X&(N-1))。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;// >>> 无符号右移,高位补0
n |= n >>> 2;// a|=的意思是把a和b位按位或 然后赋值给a
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

主要的属性

HashMap中的主要属性是一定要认识一下的,因为HasMap的一些特点很多是与属性有关的。

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
private static final long serialVersionUID = 362498820763181265L;
//初始容量的大小, 必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//顾名思义:集合的最大容量,必须是2的幂且小于2的30次方,传入的值如果过大的话,将会被这个值替换
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充比
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
//当数组中的一个位置上的链表的长度达到8的时候,将会将链表转化为红黑树
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* The number of key-value mappings contained in this map.
*/
//集合中的元素个数
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
//map结构被修改的次数
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
//临界值,当实际大小(容量*填充比)超过临界值时,会进行扩容。
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
//填充比
final float loadFactor;

HashMap中的成员属性不得不说的得是填充比了, 它的默认值是0.75 ,如果实际元素所占容量占分配容量的75%时,就要扩容了,如果填充比很大,说明空间的利用率非常的大,但是此时的查找效率是会很低的,因为链表的长度很大,但是JDK1.8之后的使用了红黑树会效率会更高一些,HashMap本来是以空间换时间,所以填充比没有必要太大,但是填充比太小会导致空间的浪费,如果关注内存,那么填充比可以稍大,如果关注的是查找性能,填充比可以稍小。

元素的存放位置put/get方法

我们向HashMap中添加元素的时候是通过put(K,V)方法,取得元素的方法一般是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
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//此处分两种情况:1.当tabel为null时,用默认容量16初始化tabel数组,2.当table非空的时候
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//初始化hashMap的长度为16
//此处又分为两种情况,1.key的hashMap值对应的那个节点为空时,2.key的hash值对应的那个节点不为空。
if ((p = tab[i = (n - 1) & hash]) == null)//此种情况是 该key的hash值对应的那个节点为空,即表示还没有元素被散列到这个位置
//那么就创建一个新的Node元素
tab[i] = newNode(hash, key, value, null);
else {
//该key的hash值对应的那个节点不为空,与链表上的第一个节点p比较
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
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) {
p.next = newNode(hash, key, value, null);
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对应的value已经存在了,则用新的value取代旧的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//如果加入该键值对后超过最大阙值,则进行resize操作。
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// put()方法中,使用的hash方法进行对key计算哈希值,从这里可以知道,如果传入的key值为null的时候,哈希值是0, 否则的话是通过key值的hashCode()方法取得值,然后做一次16位位移异或混合进行位运算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key.hashCode()函数调用的是key键值类型自带的哈希函数,返回int型散列值。理论上散列值是一个int型,如果直接拿散列值作为下标访问HashMap主数组的话,考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散,一般是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。你想,HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来访问数组下标。源码中模运算是在这个indexFor( )函数里完成的。

1
bucketIndex = indexFor(hash, table.length);

indexFor的代码也很简单,就是把散列值和数组长度做一个”与”操作.

1
2
static int indexFor(int h, int length){
return h & (length-1);

顺便说一下,这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样(数组长度-1)正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零,只保留低位值,用来做数组下标访问。以初始长度16为例,16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下,结果就是截取了最低的四位值

1
2
3
4
10100101 11000100 00100101
& 00000000 00000000 00001111
---------------------------------
00000000 00000000 00000101 //高位全部归0,只保留末四位

但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重。更要命的是如果散列本身做得不好,分布上成等差数列的漏洞,恰好使最后几个低位呈现规律性重复,就无比蛋疼。这时候“扰动函数”的价值就体现出来了,说到这里大家应该猜出来了。看下面这个图,

位移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性.而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。
最后我们来看一下Peter Lawley的一篇专栏文章《An introduction to optimising a hashing strategy》里的一个实验:他随机选取了352个字符串,在他们散列值完全没有冲突的前提下,对它们做低位掩码,取数组下标。

结果显示,当HashMap数组长度为512的时候,也就是用掩码取低9位的时候,在没有扰动函数的情况下,发生103次碰撞,接近30%,而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%,看来扰动函数确实是有功效的。

HashMap中查找元素方法的办法有多种,有get(Object key), containsKey(Object key), containsValue(Object 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
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
//返回指定key所映射的value;如果对于该键来说,次映射不包含任何的映射,则返回null
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// key的哈希值作为数组的下表
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//检查第一个节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果第一个节点不对,则向后检查
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
//如果此映射包含对于指定将的映射关系,则返回true
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
//如果此映射将一个或多个键映射到指定值,则返回true
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
//外层循环搜索数组
for (int i = 0; i < tab.length; ++i) {
//内层循环搜索链表
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}

HashMap的扩容机制

在HsahMap的四种构造函数中并没有对其中的成员变量Node< K,V > [] table 进行任何初始化的工作,从上面对hashMap中的主要的属性的分析知道,构造HashMap表的时候,如果不指定表的数组大小的情况下,默认大小是16,那么HashMap是如何构造一个默认的初始容量为16的空表的呢?如果Node数组中的元素达到 填充比*Node.length 的时候,HsahMap将会扩容。那么它是怎么扩容的呢?

我们直接上源码吧!

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
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
// 功能1. 初始化hashMap里的容量大小。功能2.对hashMap中的容量进行扩容,翻倍
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//旧的hashMap
// 先根据数组对象是否进行了初始化,得到旧HashMap的初始的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//旧的HashMap的阙值
int newCap, newThr = 0;//新的HashMap容量,与扩容临界值
if (oldCap > 0) {
//如果容量大小超过最大容量大小,则不在进行调整,只能改变阙值了。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新的容量大小为旧的2倍,最小的为16
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 { // zero initial threshold signifies using defaults
// oldCap = 0, oldThr = 0 相当于使用默认填充比和初始容量来进行初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
//创建一个新的数组长度为newCap大小,然后将原来的数组中的元素拷贝到新的数组中。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果旧的HashMap表非空,则按序将旧HashMap中的元素重定向到新HashMap表中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;//e按序指向oldTab数组中的元素,及每个链表中的头结点
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 { // preserve order
//对链表进行秩序的维护,因为对HashMap表是进行过两倍的扩容,所以每个桶里面的元素必须要么是待在原来的索引所对应该位置,要么是在新的桶中位置偏移两倍。
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;
}

通过阅读和解释上面的源码可以知道:
该初始化的诱发条件是在向HashMap中添加第一个元素时,通过put< K key, V value >——>putVal(hash(key), key, value, false, true)——> resize()方法,一步一步的将元素添加到hashMap中。HashMap中尤其重要的resize()方法主要实现的了两个功能:
1、在table为数组为null的时候,对其进行初始化,默认容量是16;
2、当table数组为非空,但是需要调整HashMap容量的时候,将HsahMap容量翻倍。
该方法的解释是: 这个方法可以用来初始化HashMap的大小,或者重新调整HashMap的大小,变为原来的2倍。 在从旧的数组中拷贝元素到新的数组中的时候,是一个一个的遍历数组,元素的同时遍历链表(或者红黑树),所以这个过程是相当的耗时间的。

清空有删除

HashMap中提供了remove(Object key)方法来删除键值对,使用clear()清除所有的键值对的方法,这方法使用的时候需要比较小心。

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
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
//该方法是remove()方法的内部实现方法。
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//table数非空,键的hash值所指向的数组中的元素非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;//node指向最终的结果节点,e为链表中的遍历指针
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//检查第一个节点,如果匹配成功
node = p;
//如果第一个节点匹配不成功,则向后遍历链表查找
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//删除node节点
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
//从映射中移出所有映射关系
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;//直接将数组中的值赋值为null
}
}

其他方法:size(),isEmpty(),clone()

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
//返回HasMap中的大小
public int size() {
return size;
}
//判断hashMap是否为空
public boolean isEmpty() {
return size == 0;
}
/**
* Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
* values themselves are not cloned.
*
* @return a shallow copy of this map
*/
//HashMap复制。
@SuppressWarnings("unchecked")
@Override
public Object clone() {
HashMap<K,V> result;
try {
result = (HashMap<K,V>)super.clone();//调用父类的clone方法
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
result.reinitialize();
//将HashMap 元素放入到result中。
result.putMapEntries(this, false);
return result;
}

HashMap序列化

保存Node的table数组为transient的,也就是说在进行序列化时,并不会包含该成员,这是为什么呢?

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

为了解答这个问题,我们需要明确下面事实:

  • Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值

我们可以试着想下一下下面的场景

1
2
我们在机器A上算出对象A的哈希值与索引,然后把它插入到HashMap中,然后把该HashMap序列化后,在机器B上重新算对象的哈希值与索引,这与机器A上算出的是不一样的,所以我们在机器B上get对象A时,会得到错误的结果。
所以说,当序列化一个HashMap对象时,保存Entry的table是不需要序列化进来的,因为它在另一台机器上是错误的。

因为这个原因,HashMap重现了writeObject与readObject 方法

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
/**
* Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
* serialize it).
*
* @serialData The <i>capacity</i> of the HashMap (the length of the
* bucket array) is emitted (int), followed by the
* <i>size</i> (an int, the number of key-value
* mappings), followed by the key (Object) and value (Object)
* for each key-value mapping. The key-value mappings are
* emitted in no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);
internalWriteEntries(s);
}
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
reinitialize();
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
s.readInt(); // Read and ignore number of buckets
int mappings = s.readInt(); // Read number of mappings (size)
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
else if (mappings > 0) { // (if zero, use defaults)
// Size the table using given load factor only if within
// range of 0.25...4.0
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
float fc = (float)mappings / lf + 1.0f;
int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
DEFAULT_INITIAL_CAPACITY :
(fc >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
table = tab;
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}

简单来说,在序列化时,针对Entry的key与value分别单独序列化,当反序列化时,再单独处理即可。

小结

HashMap的一些特点

  • 线程非安全,并且允许key与value都为null值,HashTable与之相反,为线程安全,key与value都不允许null值。

  • 不保证其内部元素的顺序,而且随着时间的推移,同一元素的位置也可能改变(resize的情况)

  • put、get操作的时间复杂度为O(1)。

  • 遍历其集合视角的时间复杂度与其容量(capacity,槽的个数)和现有元素的大小(entry的个数)成正比,所以如果遍历的性能要求很高,不要把capactiy设置的过高或把平衡因子(load factor,当entry数大于capacity*loadFactor时,会进行resize,reside会导致key进行rehash)设置的过低。

  • 负载因子是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况非常特殊。

  • 由于HashMap是线程非安全的,这也就是意味着如果多个线程同时对一hashmap的集合试图做迭代时有结构的上改变(添加、删除entry,只改变entry的value的值不算结构改变),那么会报ConcurrentModificationException,专业术语叫fail-fast,尽早报错对于多线程程序来说是很有必要的。

  • Map m = Collections.synchronizedMap(new HashMap(…)); 通过这种方式可以得到一个线程安全的map。

  • 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。

  • JDK1.8引入红黑树大程度优化了HashMap的性能。

坚持原创技术分享,您的支持将鼓励我继续创作!