JDK7 HashMap源码分析

HashMap是Java内置实现了Map接口的一个常用类,通常我们使用这个类来保存键-值对,其中Key和Value可以是任意的Java引用类型(不能使用基本数据类型)。这篇文章基于JDK7来分析HashMap的源码,了解一下HashMap的底层结构。

1. HashMap底层结构

HashMap内部维护一个Entry类型的数组(变量命名为table)。Entry对象除了存放Key和Value,还引用了另外一个Entry对象(命名为next),table数组中的每一个元素都是一个Entry链,实际上的HashMap就是一个Entry数组链表。通过计算每一个元素的hash值(根据key来计算得到hash值),将不同元素散列到不同的数组链上。注意,key值不同的情况下可能求得的hash值是相同的(hash冲突),hash值相同key值不同的元素位于同一条Entry链。

HashMap中链表元素的添加采用头插法,即最新插入的元素位于链表头部。

下面这张图很好地描述了HashMap的底层结构:

show hashmap construct

2. HashMap方法剖析

2.1 put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

(1) 首先判断table数组是否为空数组,空的话就扩展数据容量为接近于初始容量的2的整数幂。

(2) 如果key == null,调用putForNullKey方法。

(3) 调用hash方法根据key计算hash值。

(4) 根据计算的hash值调用indexFor()来获取将要插入table数组的下标索引。

(5) 接下来使用下标索引找到对应的Entry链表进行遍历,如果发现有某个元素key的hash值和key值与所查找的key相同时,则更新value为当前value,并返回oldValue,如果没有找到,那么调用addEntry方法将key和value包装为一个Entry对象插入到链表头部。在addEntry方法里面会判断map里面的元素个数是否超过阈值(threshold),如果超过阈值,要进行扩容操作,并且重新组织map里面的元素到新的位置,然后再将当前要插入的key和value插入到合适的位置。

putForNullKey将key为null的元素放到table数组下标为0的链表中,默认当key为null的时候,hash = 0。

2.2 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
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
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;
}

(1) 判断key是否为空,如果为空就直接调用getForNullKey方法,从table数组下标为0的链表中查找key为null的Entry并返回它的value。

(2) 如果key非空,则调用getEntry方法,getEntry方法会先根据key计算hash值,然后调用indexFor方法查找对应table数组下标,然后再去对应的链表上面查找对应key值的Entry并返回其value。

(3) 如果找不到key对应的元素,返回null。

2.3 remove方法

说白了其实就是找到对应的table数组链,然后在链表上找对应的Entry节点,找到就执行删除链表节点操作。

2.4 indexFor方法

1
2
3
4
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}

indexFor是一个default静态方法,外部无法访问到,用于元素的定位操作。通过使用key的hash值以及table数组长度来计算该元素在table数组中的下标位置。使用&位操作来替代取模%操作,更为高效(方正我是没测过- -),限制是length必须是2的非零整数次幂。

2.5 hash方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

hash方法可以说是实现HashMap的关键方法,然而我并没有看懂,不知道它是怎么计算得到最优的hash值。越好的hash算法能够使得元素尽可能地散列到table数组里面,减少hash冲突。最差的hash算法可能导致HashMap分布呈现为一个单链表。

2.6 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
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;
}
}
}

resize方法主要完成table数组的扩容,并重新设置阈值threshold,扩容逻辑封装在transfer方法里面,扩容的思路如下:

  • 对于原table数组里面的每一条Entry链,遍历里面的子元素进行hash操作
  • 根据得到的新hash值重新定位元素在扩容后的table数组里面的对应的Entry链上

频繁的扩容对HashMap的性能有很大影响。

3. 影响性能的要点

3.1 阈值threshold

threshold是由容量capacity和负载因子loadFactor(默认是0.75)共同决定的:

1
threshold = capacity * loadFactor

超过阈值将对table数组进行扩容capacity * 2,然后将数组链上面的元素进行rehash操作,重新调整到合适的位置上。当HashMap中存放的元素比较大的情况下,性能会有比较大的影响。所以提前预估map里面元素个数以及增长趋势并在构建HashMap时候指定容量可以适当避免出现过度rehash的情况。

3.2 hash方法

在前面的介绍中提到,散列算法的优劣影响着元素在table数组链上面的分布,如果散列算法使用不当,那么实际上HashMap可能演变成一个单链表。理想化的HashMap获取元素的时间复杂度是O(1),如果演化为单链表的话,那么获取元素的时间复杂度为O(n)。

4. 知识延伸

4.1 HashMap 与 HashTable的不同点

根据我的理解,有以下不同点:

  • HashMap支持key或者value为空的插入操作,而HashTable不支持key或者value为空的插入操作(会抛出NullPointerException)。
  • HashMap不是线程安全的类,而HashTable是线程安全的类,所有对外方法都是synchronized方法,表示同一个时刻只有一个线程能够操作这个HashTable。虽然HashTable是线程安全,但是在多线程竞争激烈的情况下,并发性能表现会比较差。所以某位Java大神在JDK5中引入ConcurrentHashMap,采用分段锁机制来更好的支持多线程下HashMap的并发,能明显提升性能)。

4.2 如何将HashMap变成一个线程安全的类

可以使用JDK中内置的Collections工具类的synchronizedMap方法将一个HashMap包装(或者称为装饰)为一个线程安全的HashMap。

synchronizedMap方法会使用一个代理类SynchronizedMap来包装我们的Map。这个代理类也实现了Map接口,通过我们传入的map委托对象来实现每一个Map接口,然后使用synchronized代码块封装所有的map方法,达到封装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
private static class SynchronizedMap<K,V>
implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
if (m==null)
throw new NullPointerException();
this.m = m;
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
synchronized (mutex) {return m.remove(key);}
}
// 其他方法
// ...
}

4.3 HashSet 与 HashMap的关系

HashSet的实现依赖于HashMap,HashSet将数据存放到一个HashMap对象中,即HashSet底层维护了一个HashMap变量。其中,key存放实际添加的元素,而对应每一个key的value都是一个Object对象。有兴趣的同学可以去翻翻HashSet的源码,这里就不深入去涉及HashSet。只要你掌握了HashMap的源码,那么HashSet相对就简单许多了。

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