HashSet、HashMap、HashTable源码分析

本文基于Android6.0源码分析

HashSet

HashSet常用于存储无重复的值。

HashSet内部实现:

1
2
3
public HashSet() {
this(new HashMap<E, HashSet<E>>());
}

说明HashSet内部实际上是key为自身的value,而value为自身的hashmap来实现存储的,HashSet能够实现非重复存储的功能是通过HashMap来实现的,所以直接看HashMap。

HsahMap

HashMap是key->value字典格式的数据结构

先来看看HashMap的构造函数:

1
2
3
4
5
6
transient HashMapEntry<K, V>[] table;
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}

从HashMap的构造函数可以看到,HashMap内部实际上是通过table来存储数据的,而table是一个HashMapEntry数组。

看看HashMap最重要的函数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
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
//根据key获取hash
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
//根据hash找到数据的index
int index = hash & (tab.length - 1);
//遍历这个index下的链表
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
//没有key,存新的值
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
//可以看到hashmap存新值就是往table中插入一个新的值
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

从上面的代码也可以看出HashMap在内存中的数组-链表式的存储结构,如下:

hashmap-structure

根据key由hash函数算出hashcode值,根据hashcode值找到HashMapEntry数组对应的index,若该index下没有值,则调用addNewEntry插入新值,否则( 发生hashcode冲突)在该index下链表尾添加新节点。

hashmap的存储结构也解释了一个问题:为什么HashSet和HashMap读取数据的复杂度数O(1),因为他是数据存储的,数组在内存中是连续的,可以根据index快速定位内存位置,HashMap的键冲突情况出现较少,链表的查找复杂度也在O(1)。

HashMap源码其他细节:

1
2
3
4
5
6
7
8
9
10
11
12
//数组的大小是4
private static final int MINIMUM_CAPACITY = 4;
static final float DEFAULT_LOAD_FACTOR = .75F;
//默认大小2
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];
//threshold表示一个当前容量临界值,当当前hashmap大小超过threshold时,hashmap的capacity扩容(翻倍扩容)
//threshold = capacity * DEFAULT_LOAD_FACTOR;
private transient int threshold;

HashMap中常用的几个成员变量

1
2
3
private transient Set<K> keySet;//hashmap的key构成的set,可实现key遍历
private transient Set<Entry<K, V>> entrySet;//hashmap键值对构成的set,可实现hashmap遍历
private transient Collection<V> values;//hashmap的value构成的set,可实现value遍历

HashTable

HashTable的源码和HashMap很类似,只是几乎在所有函数前都加了synchronized关键字,HashTable和HashMap在使用上并没有什么不同,只是hashtable是线程安全的。