HashMap源码分析

HashMap是什么

HashMap是一个基于哈希表的容器,可以提供数值之间的映射操作。允许使用null值和null键,但是不保证映射的顺序。另外,HashMap是非线程安全的,在多线程的环境下使用可能存在问题。

常见使用方法:

  • 存:

    1
    map.put(key,value);
  • 取:

    1
    map.get(key);
  • 遍历:

    1
    2
    3
    4
    for (Map.Entry<K, V> entry : map.entrySet()) {
    Object key = entry.getKey();
    Object value = entry.getValue();
    }

源码版本:JDK 1.7.0

继承关系

1
2
3
4
5
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

HashMap继承于AbstractMap,同时实现了Map,Cloneable,Serializable接口。因此,HashMap可以被克隆(Cloneable),同时也支持序列化(Serializable)。

存储结构

HashMap使用内部类Entry来存储数据,Entry实现了Map.Entry接口

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
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
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 Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap<K,V> m) {}
void recordRemoval(HashMap<K,V> m) {}
}

关键属性

1
2
3
4
5
6
7
8
9
10
11
12
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
transient int hashSeed = 0;
private transient Set<Map.Entry<K,V>> entrySet = null;
  • DEFAULT_INITIAL_CAPACITY代表HashMap桶(bucket)的默认容量,初始化为16,该值必须是2的幂。

  • MAXIMUM_CAPACITY代表HashMap桶(bucket)的最大容量,初始化为1073741824,该值必须是2的幂,同时,如果构造的容量大于这个值,那么实际的容量就会被这个值替换。

  • DEFAULT_LOAD_FACTOR是默认的加载因子,用于计算HashMap扩容的threshold,当HashMap的实际使用容量达到总容量的threshold时,对HashMap进行扩容。

  • EMPTY_TABLE空表,用于判断当前Map对象是否扩容过。

  • table是存储Entry的数组,每个Entry是一条单链表的头节点。

  • size代表HashMap实际键值对的数量。

  • threshold是HashMap是否需要扩容的阈值,threshold = capacity * load factor。

  • loadFactor是HashMap实际加载因子,通过构造方法传入,如未指定,则为DEFAULT_LOAD_FACTOR。

    该值代表HashMap发生扩容时的扩展程度。如果值越大,意味着HashMap扩容前发生hash冲突的机会越大,单链表的长度可能越长,容器查找效率可能降低。如果值越小,意味着HashMap空间利用率越低,可能在空间没有被充分利用的情况下就开始扩容操作。

  • modCount代表当前HashMap发生结构性修改的次数。结构性修改指修改HashMap键值对数量或者内部结构的操作。该值用于容器迭代器fail-fast的判断。

  • ALTERNATIVE_HASHING_THRESHOLD_DEFAULT

  • hashSeed按需生成的hash种子。

构造方法

HashMap共有四个构造方法

1
2
3
4
public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity);
public HashMap();
public HashMap(Map<? extends K, ? extends V> m)

2和3是在方法体中调用1并赋予上述的默认值。

这里重点分析1和4的逻辑过程。

构造参数为容量和加载因子

1
2
3
4
5
6
7
8
9
10
11
12
13
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();
}

在此构造方法中会对参数的边界条件做判断和处理,如容量参数若大于最大值则实际赋予最大值。

1
2
3
4
5
6
7
8
9
/**
* Initialization hook for subclasses. This method is called
* in all constructors and pseudo-constructors (clone, readObject)
* after HashMap has been initialized but before any entries have
* been inserted. (In the absence of this method, readObject would
* require explicit knowledge of subclasses.)
*/
void init() {
}

构造参数是Map对象

1
2
3
4
5
6
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}

在此构造方法中,先通过Map对象的实际大小和默认加载因子计算出新建对象的容量大小,之后调用inflateTable方法计算初始化值并创建对象空间,最后调用putAllForCreate方法拷贝参数Map对象的内容。

1
2
3
4
5
6
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize); // Find a power of 2 >= toSize
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}

inflateTable方法中先计算出在二的幂次中大于参数的最小值(roundUpToPowerOf2逻辑如下),综合容量、加载因子和默认最大容量判断是否需要扩容,最后创建对象空间并按需计算hashSeed参数。

1
2
3
4
5
private static int roundUpToPowerOf2(int number) {
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

initHashSeedAsNeeded方法用于计算hashSeed参数,其中hashSeed用于计算key的hash值,它与key的hashCode进行按位异或运算。这个hashSeed是一个与实例相关的随机值,主要用于解决hash冲突。具体逻辑如下。

1
2
3
4
5
6
7
8
9
10
11
12
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}

putAllForCreate方法枚举参数Map的键值对,并调用putForCreate方法保存。

1
2
3
4
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}

putForCreate方法中,通过hash方法计算出key的hash值,通过indexFor方法计算出应该存放的位置,如果该位置不为空(即之前已经存放其他对象),则按链表查询是否存在相等的对象,若存在则把参数value赋值给它并结束。若不存在,通过createEntry方法创建存储体并放入对应位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);
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 != null && key.equals(k)))) {
e.value = value;
return;
}
}
createEntry(hash, key, value, i);
}
1
2
3
4
5
6
7
8
9
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
1
2
3
static int indexFor(int h, int length) {
return h & (length-1);
}
1
2
3
4
5
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++;
}

存取方法

取方法

取方法的核心在getEntry方法中,主要逻辑即通过参数key计算出index找到对应位置,并通过遍历链表和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
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
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 != null && key.equals(k))))
return e;
}
return null;
}

存方法

存方法的核心在putaddEntry方法中,其中在addEntry方法中如果HashMap的容量超过了threshold时会执行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
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
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;
}
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
if (table == EMPTY_TABLE) {
inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
}
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
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, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
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;
}
}
}

线程安全

参考:疫苗:Java HashMap的死循环

HashMap和HashTable

HashTable和HashMap在底层都是相同的存储结构,类方法的逻辑也基本相同,但是有两者有两点不同:

  1. HashTable在很多方法上都加了synchronized保证线程安全
  2. 在新增键值对时,HashMap允许key或value为null,但在HashTable中不允许key或value为空