人们对于任何事物的认知，往往都存在这么一个现象：只有你了解的东西，你才会感兴趣。
HashMap之于Java开发者来说，也是如此。相信多数人在起初相当长的时间内，对HashMap的印象都是“Map接口的实现类，是基于哈希的，用于存放键-值对，允许null作为键和值，非线程安全的”，仅此而已。于是在程序编写过程中便“肆无忌惮”往里放键-值对。而只有你对HashMap的实现有了一定的了解之后，你才会有兴趣研究HashMap深层次的问题，比如“HashMap最多能放多少个键-值对？如何提高HashMap的使用效率？”。其实，我一直都对HashMap的“线性数组+链表”的实现机制充满好奇，刚刚有时间研究了一下源码，现把心得与大家分享。
首先，我们来看看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
82
83
84
85
|
/**
* 初始容量，大小必须是2的指数次方，默认是16.
*/
static
final
int
DEFAULT_INITIAL_CAPACITY =
16
;
/**
* 默认最大容量，值为1<<30
*/
static
final
int
MAXIMUM_CAPACITY =
1
<<
30
;
/**
* 哈希表的默认加载因子，值为0.75.
*/
static
final
float
DEFAULT_LOAD_FACTOR =
0
.75f;
/**
* 存储元素的数组，大小必须是2的指数次方，默认是16.
*/
transient
Entry[] table;
/**
* THashMap中的存储的<K,V>映射的数目.
*/
transient
int
size;
/**
* threshold=容量*加载因子。当实际数目大于threshold时，HashMap就需要扩容.
* @serial
*/
int
threshold;
/**
* 哈希表的加载因子，如果创建时不指定loadFactor，则使用DEFAULT_LOAD_FACTOR.
*
* @serial
*/
final
float
loadFactor;
//... ...
/**
*
* <p>用一个静态内部类来定义数组项链表的元素</p>
*
* @author bruce.yang
* @version 1.0 Created on 2014-10-22 上午11:39:50
*/
static
class
Entry<K,V>
implements
Map.Entry<K,V> {
final
K key;
V value;
Entry<K,V> next;
final
int
hash;
/**
* Creates new entry.
*/
Entry(
int
h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public
final
K getKey() {
return
key;
}
public
final
V getValue() {
return
value;
}
public
final
V setValue(V newValue) {
V oldValue = value;
value = newValue;
return
oldValue;
}
public
final
boolean
equals(Object o) {
if
(!(o
instanceof
Map.Entry))
return
false
;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if
(k1 == k2 || (k1 !=
null
&& k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if
(v1 == v2 || (v1 !=
null
&& v1.equals(v2)))
return
true
;
}
return
false
;
}
public
final
int
hashCode() {
return
(key==
null
?
0
: key.hashCode()) ^
(value==
null
?
0
: value.hashCode());
}
public
final
String toString() {
return
getKey() +
"="
+ getValue();
}
|
可以看出，HashMap正是采用数组(table)类存储数据的，而数组每一个元素则是一个被静态内部类Entry封装起来的对象，元素在数组中的下标则是根据key的hashcode计算出来的；当元素下标重复的时候，会在此下标处形成一个链表，而这个链表就是通过Entry结构来实现的。我们看到，这个Entry结构是一个单向链表，它只有一个next项指向下一个元素，此外，它还包含<K,V>对，同时还有一个哈希值hash。
其次，当我们往hashmap中put元素的时候，先是根据key的hash值计算得出这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。源码：
|
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
|
/**
* 建立指定key和value之间的映射：
* 如果已经存在key，则替换对应的value，并返回原来的value；如果原来没有建立映射，则建立映射，并返回null。
* 当然了，由于HashMap允许key和value为null，返回null还有可能就是原来的value为null。
*/
public
V put(K key, V value) {
//如果key==null，则调用专门的方法处理
if
(key ==
null
)
return
putForNullKey(value);
int
hash = hash(key.hashCode());
int
i = indexFor(hash, table.length);
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++;
//加入新的项
addEntry(hash, key, value, i);
//原来不存在这项
return
null
;
}
private
V putForNullKey(V value) {
for
(Entry<K,V> e = table[
0
]; e !=
null
; e = e.next) {
if
(e.key ==
null
) {
V oldValue = e.value;
e.value = value;
e.recordAccess(
this
);
return
oldValue;
}
}
modCount++;
addEntry(
0
,
null
, value,
0
);
return
null
;
}
/**
* 添加key-value项
*/
void
addEntry(
int
hash, K key, V value,
int
bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//加入该项到链表头部
table[bucketIndex] =
new
Entry<K,V>(hash, key, value, e);
if
(size++ >= threshold)
resize(
2
* table.length);
}
/**
*扩充HashMap的容量
*/
void
resize(
int
newCapacity) {
Entry[] oldTable = table;
int
oldCapacity = oldTable.length;
if
(oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return
;
}
Entry[] newTable =
new
Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (
int
)(newCapacity * loadFactor);
}
/**
* 将原来数组中元素传输到新数组中
*/
void
transfer(Entry[] newTable) {
Entry[] src = table;
int
newCapacity = newTable.length;
for
(
int
j =
0
; j < src.length; j++) {
Entry<K,V> e = src[j];
if
(e !=
null
) {
src[j] =
null
;
do
{
Entry<K,V> next = e.next;
int
i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
while
(e !=
null
);
}
}
}
|
可以看到,首先判断key是否为null:
1).若为null，则调用专门的方法putForNullKey（value）处理并返回。
1.1)如果事先已经存在key为null的映射，则替换后返回old value。
1.2)如果不存在，则添加新的项到链表中
2).若key不为null
2.1)首先计算key的哈希值，然后根据哈希值和table数组的长度定位数组项。
2.2)对数组项的链表进行遍历，如果key的哈希值与链表中的某一项的哈希值相等且key本身引用值相等或者引用值所指向的对象相等，则替换相应项的value值为新的value，并返回老的value。如果没有找到相同的key，则加入该项到链表中。
2.3)addEntry方法直接将新的项加入到链表的头部，新项的next引用指向原来的链表项。此外判断是否需要扩容，如果此时存储的项数目size大于等于threshold，则扩大HashMap容量为原来的2倍。
2.4)resize方法用来扩容HashMap。默认是扩容至原来的2倍大小。
第三，当从hashmap中get元素时，首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。源码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/**
* 根据key取得value
*/
public
V get(Object key) {
if
(key ==
null
)
return
getForNullKey();
int
hash = hash(key.hashCode());
for
(Entry<K,V> e = table[indexFor(hash, table.length)];
e !=
null
;
e = e.next) {
Object k;
if
(e.hash == hash && ((k = e.key) == key || key.equals(k)))
return
e.value;
}
return
null
;
}
private
V getForNullKey() {
for
(Entry<K,V> e = table[
0
]; e !=
null
; e = e.next) {
if
(e.key ==
null
)
return
e.value;
}
return
null
;
}
|
可以看到，如果key为null，get方法与put方法对应，对null值也有特殊处理，即直接到table[0]中去找key为null对应的value。
如果key不为null，则定位key所在数组项，然后遍历链表，如果存在key，则返回对应的value值，否则返回null。
第四，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
|
/**
*指定初始化容量和加载因子
*/
public
HashMap(
int
initialCapacity,
float
loadFactor) {
//initialCapacity不能小于0
if
(initialCapacity <
0
)
throw
new
IllegalArgumentException(
"Illegal initial capacity: "
+
initialCapacity);
//如果指定容量大于默认最大容量，则按照默认最大容量创建
if
(initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//loadFactor不能小于0
if
(loadFactor <=
0
|| Float.isNaN(loadFactor))
throw
new
IllegalArgumentException(
"Illegal load factor: "
+
loadFactor);
//找最大于指定初始化容量的2的指数幂作为表的真实容量
int
capacity =
1
;
while
(capacity < initialCapacity)
capacity <<=
1
;
this
.loadFactor = loadFactor;
threshold = (
int
)(capacity * loadFactor);
table =
new
Entry[capacity];
init();
}
/**
*只指定初始化容量，加载因子采用默认
*/
public
HashMap(
int
initialCapacity) {
this
(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 初始化容量和加载因子都采用默认
*/
public
HashMap() {
this
.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (
int
)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table =
new
Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
|
只看源码和注释就一目了然了，这里所要特别注意一下带两个参数的构造方法，其初始化时的初始大小不一定是你所指定的大小。
最后，文章开头提出的那两个问题已经不再成为问题了：
1).HashMap最大容量是1 << 30，
2).而影响HashMap性能的两个因素是：初始容量和加载因子。这里借用书中的一段话来表述：容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子 (0.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap类的操作中，包括 get 和 put操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash操作。
读到这里，相信你对HashMap已经有了一个更深刻的认识。
各位，晚安，好梦。
本文转自NightWolves 51CTO博客，原文链接：http://blog.51cto.com/yangfei520/1566942，如需转载请自行联系原作者
