Java集合干货系列-(三)HashMap源码解析

前言

今天来介绍下HashMap,之前的List,讲了ArrayList、LinkedList,就前两者而言,反映的是两种思想:

  • ArrayList以数组形式实现,顺序插入、查找快,插入、删除较慢
  • LinkedList以链表形式实现,顺序插入、查找较慢,插入、删除方便

那么是否有一种数据结构能够结合上面两种的优点呢?有,答案就是HashMap。它是基于哈希表的 Map 接口的实现,以key-value的形式存在。
构造图如下:
蓝色线条:继承
绿色线条:接口实现

正文

要理解HashMap, 就必须要知道了解其底层的实现, 而底层实现里最重要的就是它的数据结构了,HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体

在分析要理解HashMap源码前有必要对hashcode进行说明。
以下是关于HashCode的官方文档定义:

hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。
hashCode 的常规协定是:
在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。

如果根据 equals(Object) 方法,两个对象是相等的,那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。

以下情况不 是必需的:如果根据 equals(java.lang.Object) 方法,两个对象不相等,那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能。

实际上,由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。(这一般是通过将该对象的内部地址转换成一个整数来实现的,但是 JavaTM 编程语言不需要这种实现技巧。)

当equals方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。

以上这段官方文档的定义,我们可以抽出成以下几个关键点:

  1. hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的;

  2. 如果两个对象相同,就是适用于equals(java.lang.Object) 方法,那么这两个对象的hashCode一定要相同;

  3. 如果对象的equals方法被重写,那么对象的hashCode也尽量重写,并且产生hashCode使用的对象,一定要和equals方法中使用的一致,否则就会违反上面提到的第2点;

  4. 两个对象的hashCode相同,并不一定表示两个对象就相同,也就是不一定适用于equals(java.lang.Object) 方法,只能够说明这两个对象在散列存储结构中,如Hashtable,他们“存放在同一个篮子里”

再归纳一下就是hashCode是用于查找使用的,而equals是用于比较两个对象的是否相等的。以下这段话是从别人帖子回复拷贝过来的:

1.hashcode是用来查找的,如果你学过数据结构就应该知道,在查找和排序这一章有
例如内存中有这样的位置
0 1 2 3 4 5 6 7
而我有个类,这个类有个字段叫ID,我要把这个类存放在以上8个位置之一,如果不用hashcode而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID%8,然后把我们的类存放在取得得余数那个位置。比如我们的ID为9,9除8的余数为1,那么我们就把该类存在1这个位置,如果ID是13,求得的余数是5,那么我们就把该类放在5这个位置。这样,以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。

2.但是如果两个类有相同的hashcode怎么办那(我们假设上面的类的ID不是唯一的),例如9除以8和17除以8的余数都是1,那么这是不是合法的,回答是:可以这样。那么如何判断呢?在这个时候就需要定义 equals了。
也就是说,我们先通过 hashcode来判断两个类是否存放某个桶里,但这个桶里可能有很多类,那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
那么。重写了equals(),为什么还要重写hashCode()呢?
想想,你要在一个桶里找东西,你必须先要找到这个桶啊,你不通过重写hashcode()来找到桶,光重写equals()有什么用啊

HashMap简介

HashMap定义

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

HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。
HashMap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。

HashMap属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 默认初始容量为16,必须为2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 16;

// 最大容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子为0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// Entry数组,长度必须为2的n次幂
transient Entry[] table;

// 已存储元素的数量
transient int size ;

// 下次扩容的临界值,size>=threshold就会扩容,threshold等于capacity*load factor
int threshold;

// 加载因子
final float loadFactor ;

HashMap是通过”拉链法”实现的哈希表。它包括几个重要的成员变量:table, size, threshold, loadFactor, modCount。

  • table是一个Entry[]数组类型,而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
  • size是HashMap的大小,它是HashMap保存的键值对的数量。
  • threshold是HashMap的阈值,用于判断是否需要调整HashMap的容量。threshold的值=”容量*加载因子”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。
  • loadFactor就是加载因子。
  • modCount是用来实现fail-fast机制的。

可以看出HashMap底层是用Entry数组存储数据,同时定义了初始容量,最大容量,加载因子等参数,至于为什么容量必须是2的幂,加载因子又是什么,下面再说,先来看一下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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
static class Entry<K,V> implements Map.Entry<K,V> {
final K key ;
V value;
Entry<K,V> next; // 指向下一个节点
final 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 (key ==null ? 0 : key.hashCode()) ^
( value==null ? 0 : value.hashCode());
}

public final String toString() {
return getKey() + "=" + getValue();
}

// 当向HashMap中添加元素的时候调用这个方法,这里没有实现是供子类回调用
void recordAccess(HashMap<K,V> m) {
}

// 当从HashMap中删除元素的时候调动这个方法 ,这里没有实现是供子类回调用
void recordRemoval(HashMap<K,V> m) {
}
}

Entry是HashMap的内部类,它继承了Map中的Entry接口,它定义了键(key),值(value),和下一个节点的引用(next),以及hash值。很明确的可以看出Entry是什么结构,它是单线链表的一个节点。也就是说HashMap的底层结构是一个数组,而数组的元素是一个单向链表。

为什么会有这样的设计?之前介绍的List中查询时需要遍历所有的数组,为了解决这个问题HashMap采用hash算法将key散列为一个int值,这个int值对应到数组的下标,再做查询操作的时候,拿到key的散列值,根据数组下标就能直接找到存储在数组的元素。但是由于hash可能会出现相同的散列值,为了解决冲突,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
/**
* 构造一个指定初始容量和加载因子的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);

// Find a power of 2 >= initialCapacity
// 确保容量为2的n次幂,是capacity为大于initialCapacity的最小的2的n次幂
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

// 赋值加载因子
this.loadFactor = loadFactor;
// 赋值扩容临界值
threshold = (int)(capacity * loadFactor);
// 初始化hash表
table = new Entry[capacity];
init();
}

/**
* 构造一个指定初始容量的HashMap
*/
public HashMap( int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
* 构造一个使用默认初始容量(16)和默认加载因子(0.75)的HashMap
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

/**
* 构造一个指定map的HashMap,所创建HashMap使用默认加载因子(0.75)和足以容纳指定map的初始容量。
*/
public HashMap(Map<? extends K, ? extends V> m) {
// 确保最小初始容量为16,并保证可以容纳指定map
this(Math.max(( int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY ), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}

HashMap提供了三个构造函数:

  • HashMap():构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
  • HashMap(int initialCapacity):构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
  • HashMap(int initialCapacity, float loadFactor):构造一个带指定初始容量和加载因子的空 HashMap。
  • public HashMap(Map<? extends K, ? extends V> m):包含“子Map”的构造函数

在这里提到了两个参数:初始容量,加载因子。这两个参数是影响HashMap性能的重要参数,其中容量表示哈希表中桶的数量,初始容量是创建哈希表时的容量,加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。系统默认负载因子为0.75,一般情况下我们是无需修改的。

API方法摘要

HashMap源码解析(基于JDK1.6.0_45)

put方法

HashMap会对null值key进行特殊处理,总是放到table[0]位置
put过程是先计算hash然后通过hash与table.length取摸计算index值,然后将key放到table[index]位置,当table[index]已存在其它元素时,会在table[index]位置形成一个链表,将新添加的元素放在table[index],原来的元素通过Entry的next进行链接,这样以链表形式解决hash冲突问题,当元素数量达到临界值(capactiyfactor)时,则进行扩容,是table数组长度变为table.length2

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
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //处理null值
int hash = hash(key.hashCode());//计算hash
int i = indexFor(hash, table.length);//计算在数组中的存储位置
//遍历table[i]位置的链表,查找相同的key,若找到则使用新的value替换掉原来的oldValue并返回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;
}
}
//若没有在table[i]位置找到相同的key,则添加key到table[i]位置,新的元素总是在table[i]位置的第一个元素,原来的元素后移
modCount++;
addEntry(hash, key, value, i);
return null;
}
private V putForNullKey(V value) {
// 取出数组第1个位置(下标等于0)的节点,如果存在则覆盖不存在则新增,和上面的put一样不多讲,
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++;
// 如果key等于null,则hash值等于0
addEntry(0, null, value, 0);
return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
//添加key到table[bucketIndex]位置,新的元素总是在table[bucketIndex]的第一个元素,原来的元素后移
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//判断元素个数是否达到了临界值,若已达到临界值则扩容,table长度翻倍
if (size++ >= threshold)
resize(2 * table.length);
}

get方法

同样当key为null时会进行特殊处理,在table[0]的链表上查找key为null的元素
get的过程是先计算hash然后通过hash与table.length取摸计算index值,然后遍历table[index]上的链表,直到找到key,然后返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public V get(Object key) {
if (key == null)
return getForNullKey();//处理null值
int hash = hash(key.hashCode());//计算hash
//在table[index]遍历查找key,若找到则返回value,找不到返回null
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;
}

remove方法

remove方法和put get类似,计算hash,计算index,然后遍历查找,将找到的元素从table[index]链表移除

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
/**
* 根据key删除元素
*/
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e. value);
}

/**
* 根据key删除链表节点
*/
final Entry<K,V> removeEntryForKey(Object key) {
// 计算key的hash值
int hash = (key == null) ? 0 : hash(key.hashCode());
// 根据hash值计算key在数组的索引位置
int i = indexFor(hash, table.length );
// 找到该索引出的第一个节点
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;

// 遍历链表(从链表第一个节点开始next),找出相同的key,
while (e != null) {
Entry<K,V> next = e. next;
Object k;
// 如果hash值和key都相等,则认为相等
if (e.hash == hash &&
((k = e. key) == key || (key != null && key.equals(k)))) {
// 修改版本+1
modCount++;
// 计数器减1
size--;
// 如果第一个就是要删除的节点(第一个节点没有上一个节点,所以要分开判断)
if (prev == e)
// 则将下一个节点放到table[i]位置(要删除的节点被覆盖)
table[i] = next;
else
// 否则将上一个节点的next指向当要删除节点下一个(要删除节点被忽略,没有指向了)
prev. next = next;
e.recordRemoval( this);
// 返回删除的节点内容
return e;
}
// 保存当前节点为下次循环的上一个节点
prev = e;
// 下次循环
e = next;
}

return e;
}

clear()方法

clear方法非常简单,就是遍历table然后把每个位置置为null,同时修改元素个数为0
需要注意的是clear方法只会清楚里面的元素,并不会重置capactiy

1
2
3
4
5
6
7
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}

resize方法

resize方法在hashmap中并没有公开,这个方法实现了非常重要的hashmap扩容,具体过程为:先创建一个容量为table.length2的新table,修改临界值,然后把table里面元素计算hash值并使用hash与table.length2重新计算index放入到新的table里面
这里需要注意下是用每个元素的hash全部重新计算index,而不是简单的把原table对应index位置元素简单的移动到新table对应位置

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
void resize( int newCapacity) {
// 当前数组
Entry[] oldTable = table;
// 当前数组容量
int oldCapacity = oldTable.length ;
// 如果当前数组已经是默认最大容量MAXIMUM_CAPACITY ,则将临界值改为Integer.MAX_VALUE 返回
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}

// 使用新的容量创建一个新的链表数组
Entry[] newTable = new Entry[newCapacity];
// 将当前数组中的元素都移动到新数组中
transfer(newTable);
// 将当前数组指向新创建的数组
table = newTable;
// 重新计算临界值
threshold = (int)(newCapacity * loadFactor);
}

/**
* Transfers all entries from current table to newTable.
*/
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);
// 将下一个节点指向newTable[i]
e. next = newTable[i];
// 将当前节点放置在newTable[i]位置
newTable[i] = e;
// 下一次循环
e = next;
} while (e != null);
}
}
}

transfer方法中,由于数组的容量已经变大,也就导致hash算法indexFor已经发生变化,原先在一个链表中的元素,在新的hash下可能会产生不同的散列值,so所有元素都要重新计算后安顿一番。注意在do while循环的过程中,每次循环都是将下个节点指向newTable[i] ,是因为如果有相同的散列值i,上个节点已经放置在newTable[i]位置,这里还是下一个节点的next指向上一个节点(不知道这里是否能理解,画个图理解下吧)。

Map中的元素越多,hash冲突的几率也就越大,数组长度是固定的,所以导致链表越来越长,那么查询的效率当然也就越低下了。还记不记得同时数组容器的ArrayList怎么做的,扩容!而HashMap的扩容resize,需要将所有的元素重新计算后,一个个重新排列到新的数组中去,这是非常低效的,和ArrayList一样,在可以预知容量大小的情况下,提前预设容量会减少HashMap的扩容,提高性能。

再来看看加载因子的作用,如果加载因子越大,数组填充的越满,这样可以有效的利用空间,但是有一个弊端就是可能会导致冲突的加大,链表过长,反过来却又会造成内存空间的浪费。所以只能需要在空间和时间中找一个平衡点,那就是设置有效的加载因子。我们知道,很多时候为了提高查询效率的做法都是牺牲空间换取时间,到底该怎么取舍,那就要具体分析了。

containsKey方法

containsKey方法是先计算hash然后使用hash和table.length取摸得到index值,遍历table[index]元素查找是否包含key相同的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean containsKey(Object key) {
return getEntry(key) != null;
}

final Entry<K,V> getEntry(Object key) {
// 获取哈希值
// HashMap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值
int hash = (key == null) ? 0 : hash(key.hashCode());
// 在“该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;
}

getEntry() 的作用就是返回“键为key”的键值对,它的实现源码中已经进行了说明。
这里需要强调的是:HashMap将“key为null”的元素都放在table的位置0处,即table[0]中;“key不为null”的放在table的其余位置!

containsValue方法

containsValue方法就比较粗暴了,就是直接遍历所有元素直到找到value,由此可见HashMap的containsValue方法本质上和普通数组和list的contains方法没什么区别,你别指望它会像containsKey那么高效

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean containsValue(Object value) {
// 若“value为null”,则调用containsNullValue()查找
if (value == null)
return containsNullValue();

// 若“value不为null”,则查找HashMap中是否有值为value的节点。
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}

containsNullValue() 的作用判断HashMap中是否包含“值为null”的元素

1
2
3
4
5
6
7
8
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}

entrySet()、values()、keySet()方法

它们3个的原理类似,这里以entrySet()为例来说明。
entrySet()的作用是返回“HashMap中所有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
// 返回“HashMap的Entry集合”
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}

// 返回“HashMap的Entry集合”,它实际是返回一个EntrySet对象
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}

// EntrySet对应的集合
// EntrySet继承于AbstractSet,说明该集合中没有重复的EntrySet。
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}

HashMap是通过拉链法实现的散列表。表现在HashMap包括许多的Entry,而每一个Entry本质上又是一个单向链表。那么HashMap遍历key-value键值对的时候,是如何逐个去遍历的呢?

下面我们就看看HashMap是如何通过entrySet()遍历的。
entrySet()实际上是通过newEntryIterator()实现的。 下面我们看看它的代码:

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
// 返回一个“entry迭代器”
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}

// Entry的迭代器
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}

// HashIterator是HashMap迭代器的抽象出来的父类,实现了公共了函数。
// 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
private abstract class HashIterator<E> implements Iterator<E> {
// 下一个元素
Entry<K,V> next;
// expectedModCount用于实现fast-fail机制。
int expectedModCount;
// 当前索引
int index;
// 当前元素
Entry<K,V> current;

HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
// 将next指向table中第一个不为null的元素。
// 这里利用了index的初始值为0,从0开始依次向后遍历,直到找到不为null的元素就退出循环。
while (index < t.length && (next = t[index++]) == null)
;
}
}

public final boolean hasNext() {
return next != null;
}

// 获取下一个元素
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();

// 注意!!!
// 一个Entry就是一个单向链表
// 若该Entry的下一个节点不为空,就将next指向下一个节点;
// 否则,将next指向下一个链表(也是下一个Entry)的不为null的节点。
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}

// 删除当前元素
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}

}

当我们通过entrySet()获取到的Iterator的next()方法去遍历HashMap时,实际上调用的是 nextEntry() 。而nextEntry()的实现方式,先遍历Entry(根据Entry在table中的序号,从小到大的遍历);然后对每个Entry(即每个单向链表),逐个遍历。

hash和indexFor

indexFor中的h & (length-1)就相当于h%length,用于计算index也就是在table数组中的下标
hash方法是对hashcode进行二次散列,以获得更好的散列值
为了更好理解这里我们可以把这两个方法简化为 int index= key.hashCode()/table.length,以put中的方法为例可以这样替换

1
2
3
4
int hash = hash(key.hashCode());//计算hash
int i = indexFor(hash, table.length);//计算在数组中的存储位置
//上面这两行可以这样简化
int i = key.key.hashCode()%table.length;

1
2
3
4
5
6
7
8
9
10
static int hash(int h) {
// 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);
}
static int indexFor(int h, int length) {
return h & (length-1);
}

总结

HashMap和Hashtable的区别

  1. 两者最主要的区别在于Hashtable是线程安全,而HashMap则非线程安全
    Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步,因此相对而言HashMap性能会高一些,我们平时使用时若无特殊需求建议使用HashMap,在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合(Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类,这个类实现了Map接口,在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例,简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步,类似的其它Collections.synchronizedXX方法也是类似原理)
  2. HashMap可以使用null作为key,而Hashtable则不允许null作为key
    虽说HashMap支持null值作为key,不过建议还是尽量避免这样使用,因为一旦不小心使用了,若因此引发一些问题,排查起来很是费事
    HashMap以null作为key时,总是存储在table数组的第一个节点上
  3. HashMap是对Map接口的实现,HashTable实现了Map接口和Dictionary抽象类
  4. HashMap的初始容量为16,Hashtable初始容量为11,两者的填充因子默认都是0.75
    HashMap扩容时是当前容量翻倍即:capacity2,Hashtable扩容时是容量翻倍+1即:capacity2+1
  5. HashMap和Hashtable的底层实现都是数组+链表结构实现
  6. 两者计算hash的方法不同
    Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模
    1
    2
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap计算hash对key的hashcode进行了二次hash,以获得更好的散列值,然后对table数组长度取摸

1
2
3
4
5
6
7
8
9
10
11
static int hash(int h) {
// 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);
}

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

参考

该文为本人学习的笔记,方便以后自己跳槽前复习。参考网上各大帖子,取其精华整合自己的理解而成。集合框架源码面试经常会问,所以解读源码十分必要,希望对你有用。
java提高篇(二三)—–HashMap
Java 集合系列10之 HashMap详细介绍(源码解析)和使用示例
深入Java集合学习系列:HashMap的实现原理
给jdk写注释系列之jdk1.6容器(4)-HashMap源码解析
深入Java集合学习系列:HashMap的实现原理

整理的集合框架思维导图

个人整理的Java集合框架思维导图,动态维护。导出的图片无法查看备注的一些信息,所以需要源文件的童鞋可以关注我个人主页上的公众号,回复Java集合框架即可获取源文件。


文章目录
  1. 1. 前言
  2. 2. 正文
    1. 2.1. HashMap简介
      1. 2.1.1. HashMap定义
      2. 2.1.2. HashMap属性
      3. 2.1.3. HashMap构造函数
      4. 2.1.4. API方法摘要
    2. 2.2. HashMap源码解析(基于JDK1.6.0_45)
      1. 2.2.1. put方法
      2. 2.2.2. get方法
      3. 2.2.3. remove方法
      4. 2.2.4. clear()方法
      5. 2.2.5. resize方法
      6. 2.2.6. containsKey方法
      7. 2.2.7. containsValue方法
      8. 2.2.8. entrySet()、values()、keySet()方法
      9. 2.2.9. hash和indexFor
  3. 3. 总结
    1. 3.1. HashMap和Hashtable的区别
  4. 4. 参考
  5. 5. 整理的集合框架思维导图