HashMap源码解析

前言

其实之前也有看过HashMap的源码,觉得自己对其中的实现原理什么的都还算是比较了解了。其实当初看的时候就没有看的多仔细,只是应付面试的问题罢了。 这不,最近有人提出个问题自救就没法回答了。

问: 我们知道,初始化 HashMap 的时候,可以使用默认的构造函数,也可以使用一个带 initialCapacity 参数的构造函数用于构造一个已知大小的实例。这样可以减少扩容时的数据转移等操作从而提高性能,那么已知需要存1000个数据,初始的 initialCapacity 应该是多少?

听到这问题的时候,脑海中大致知道有个扩容之类的与之相关,但是具体的却是不记得了,很是尴尬。所以接下来就回去再次详细的看了看 HashMap 的源码,这里作为记录,在下面的内容中会涉及解惑该问题。

注: 此篇文章的分析是基于JDK7的


HashMap 源码解析

在解析前我们简单说下 HashMap 的大致实现原理。 HashMap 内部是由 数组+链表 的数据结构组成的,数组的大小为capacity(默认初始大小为16,可以通过构造函数传入参数 initialCapacity 来改变)。put数据时,会根据传入的key进行hash然后对capacity取模得到数组下标index,然后将 整个Entry<K,V> 存入到对应的数组下标中去。

这里两个问题:

  1. hash会有冲突的情况。hash冲突时会得到相同的index,这时候如果再直接存 Entry<K,V> 就会导致数据覆盖

    解决方案: HashMap 在存入的时候实际上是以链表的形式存入的,并且通过判断链表中 Entry 的key值是否相等来决定是否将 Entry 加入到链表中。

  2. 当容量不够时,HashMap如何处理。扩容? 如何扩容? 何时扩容?

    这个问题是这次的主题。主要和 loadFactorinitialCapacity 两个参数有关,详细的在下面说。


构造函数

首先,我们先来看 HashMap 的构造函数,了解下影响HashMap 实例表现的一些参数。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
threshold = initialCapacity;
init();//该方法提供给子类自己实现,HashMap中没有对其实现
}

该构造函数有两个参数 initialCapacityloadFactor 这两个参数能较大的影 HashMap 实例的表现。

initialCapacity: HashMap 实例初次创建时其内部数组的大小,默认为16 loadFactor: 负载因子,默认大小为0.75。表示数组中存在多少数据的时候 HashMap 需要进行扩容(capacity的增加)

比如说,使用默认构造函数创建的HashMap 实例。即 initialCapacity=16 loadFactor=0.75,此时 HashMap 的最大容量 capacity 为16.那么当put进 16*0.75=12 个数据的时候,此时达到了负载,就需要扩容了。扩容后容量大小就是 2 * capacity. 扩容时需要rehash,并且需要 copyArray 这会消耗一 定时间,所以当已知确定的容量的时候,最好在初始化的时候设置好容量。计算公式如下:

实际容量 = 最大容量 * 负载因子

通常来说, 默认的 loadFactor 值(0.75)在时间和空间的花费上提供了一个很好的权衡。更大的 loadFactor 会减小空间的使用率,但是会增加查找所花费的时间(这会影响到 HashMap 的多数行为,包括 getput)。

为什么会增加查找锁花费的时间?

这是由于 loadFactor 越大,hash的時候就越容易冲突,导致链表长度增加,查找的时候就增加了线性的key值对比,导致效率变慢。


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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
// 存放Entry的数组,大小必须是2的幂
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold; // threshold = capacity * load factor,是需要扩展容量时的容量大小

/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
// 如果数组为空,则初始化数组大小
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果key为null,单独调用putForNullKey(value)
if (key == null)
return putForNullKey(value);
// 计算key的hash并根据hash和table的长度计算出数组下标i
int hash = hash(key);
int i = indexFor(hash, table.length);

// 获取对应下标的链表,判断是否有key值相同的Entry,如果有就使用新值替换并返回oldValue
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
// 否则,加入Entry
addEntry(hash, key, value, i);
return null;
}

/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}


/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果当前size大于threshold且新下标对应位置有值,则需要扩展数组容量,进行resize
if ((size >= threshold) && (null != table[bucketIndex])) {
// resize,容量double
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
// 重新计算数组下标
bucketIndex = indexFor(hash, table.length);
}

// 创建对应的Entry存入到对应的数组下标中去
createEntry(hash, key, value, bucketIndex);
}

/**
* Rehashes the contents of this map into a new array with a
* larger capacity. This method is called automatically when the
* number of keys in this map reaches its threshold.
*
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
*
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
// 超过了最大容量则放弃扩容
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}

// 创建新table,并将所有Entry重新计算下标存入的的table中去
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

总结下 put 操作大致步骤:

  1. 判断table是否为空,为空则初始化
  2. 判断key是否为null,为null则单独处理(这就是 HashMap 支持key为null, 这里就不细讲了,不是本篇主题,感兴趣的可以自己去看对应的源码)
  3. 根据key进行hash并根据当前数组容量取模求下标,取table中对应下标的链表。遍历链表判断是否已有对应的key,有则替换,并返回旧值;没有则加入新的Entry,返回null

这其中需要注意过程中的 扩容处理 。在备注中都说的比较明白了。 至此,最开始的问题已经解决,收工。


最后说下,在新的JDK8中, 对 HashMap 做了优化,数组下标中存的不一定是链表结构,也可能是树结构。这样当冲突大的时候,查找会更快,从而提升效率。具体的还没有详细去学习,感兴趣的可以自己去学习下。

也可以参考如下博文了解下: HashMap源码注解 之 put()方法(六)