在java中,HashMap是一种重要的数据结构,它的底层实际上是一个数组,数组的每个元素是一个链表。

在添加元素的时候,会根据hash函数计算出在数组中的下标。如果数组中该下标有元素存在,则将当前元素覆盖之前的元素;之前的元素则放到当前元素的下一个元素。如果数组中该位置没有元素,则直接放到该位置。

元素个数默认是16,加载因子是0.75,当元素的个数达到数组容量*加载因子时,会进行扩容(容量增加一倍)。

在构造HashMap时,会进行容量的计算,以及数组的初始化。

1
2
3
4
5
6
// 默认数组容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 保存数据的数组
transient Entry[] table;

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
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次方。比如指定的容量是10,则最终capacity=16
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// 数组进行扩容的阀值
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
public HashMap(int initialCapacity) {
// 使用指定的容量和默认加载因子构造HashMap
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
// 不指定参数,则使用默认的容量和加载因子构造HashMap
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

HashMap的hash函数:

1
2
3
4
5
6
7
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);
}

一个好的hash函数,应该最大限度的保证key与value一一对应,即保证数组的每个位置上都只有一个元素,不用再去遍历链表,这样查找和添加的速度都是最快的。

计算元素在数组中的索引:

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

注意:h是上面经过对key经过hash之后的值。

看下HashMap的put方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public V put(K key, V value) {
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;
}

可以看到,HashMap支持null作为key。
看下putForNullKey的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
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=null的元素放在数组的首位,替换key=null的元素的value,返回原来的value。

如果key不是null,首先通过hash函数计算key的hash值,然后通过indexFor计算在数组中的下标。
然后遍历计算的数组下标的元素的链表,如果存在key=传入的key的元素,则覆盖原来的value,并返回原来的value。

如果在计算的数组索引位置的链表结构上没有找到key为传入key的元素,则执行addEntry方法。

1
2
3
4
5
6
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}

在addEntry中,首先拿到通过hash函数计算到的数组相应index的元素,然后构造一个新的Entry对象,放到数组的index位置。
如果数组元素的个数达到阀值(即数组容量*负载因子),则将数组容量扩容2倍。

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

主要看transfer方法,遍历原数组的每个元素,如果某个位置有元素,则遍历该链表结构上的所有元素,重新计算在数组的下标,并放到新数组中。

get方法更put类似,先通过hash函数对key进行hash,然后通过indexFor得到在数组的位置。然后遍历数组中该位置的链表上的所有元素,找出key为传入的key的元素,返回。

HashMap其中有些设计很精妙,比如数组的容量为何是2的N次方?hash函数和indexFor函数。
详细可以参考:HashMap的实现原理

下来来一个简易版的HashMap实现。

1
2
3
4
public interface MyMap<K, V> {
V put(K k, V v);
V get(K k);
}
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
public class MyHashMap<K, V> implements MyMap<K, V> {
// 计算当前数组元素的个数,hash计算后index相同的元素只作为一个计算。
private int size;
// 默认负载因子
private static double defaultLoader = 0.75;
// 默认容量
private static int defaultCapacity = 16;
// 实际使用的加载因子
private double loader;
// 实际的数组容量
private int capacity = 1;
// 保存Map元素的数组
private Entry<K, V>[] table = null;
public MyHashMap(int capacity, double loader) {
this.loader = loader;
// 找出一个刚好大于给定元素个数的数作为数组的容量
// 比如指定capactiy为10,则实际容量是16.
while (this.capacity < capacity) {
this.capacity = this.capacity << 1;
}
System.out.println("capacity is :" + this.capacity);
table = new Entry[this.capacity];
}
public MyHashMap(int capacity) {
this(capacity,defaultLoader);
}
public MyHashMap() {
// 不指定容量和加载因子,则使用默认的
this(defaultCapacity, defaultLoader);
}
@Override
public V put(K k, V v) {
// 当元素的个数达到数组的容量*负载因子时,进行扩容。
if (size > this.capacity * this.loader) {
expand();
}
// 根据hash函数计算K在数组中的下标
int index = getIndex(k);
// 计算出的数组下标的元素
Entry<K, V> entry = table[index];
// entry为null,说明当前数组index位置还没有元素
if (entry == null) {
entry = new Entry(k, v, null);
table[index] = entry;
// 添加元素后,size计数器加1
size++;
} else {
// 说明,数组index位置已经有元素
// 将原来index位置的元素作为新元素的next,即新元素覆盖老元素,老元素作为新元素的下一个元素。
Entry<K,V> newEntry = new Entry(k, v, entry);
// 新元素覆盖老元素的位置。
table[index] = newEntry;
// 注意这里,size并不会增加,因为该位置原来有元素,新的元素只是增加到链表上而已。
}
// 这里返回的是新元素的value,即返回的是要put的元素
return table[index].getValue();
}
@Override
public V get(K k) {
// 根据hash函数计算K在数组中的下标
int index = getIndex(k);
// 如果下标超出当前记录的数组的index,或者数组该位置没有元素,直接返回null。
if (table[index] == null) {
return null;
}
// 计算的数组index位置的元素
Entry<K, V> entry = table[index];
// 上面已经处理了entry为null的情况,这里next为null,说明数组index位置只有一个元素,直接返回
if (entry.next == null) {
return entry.getValue();
} else {
// 链表上所有元素在数组的下标一样,但key不一样。这里需要遍历所有链表上的元素确定是哪个元素
while (entry != null) {
Entry<K, V> oldEntry = entry;
entry = entry.next;

if (oldEntry.getKey() == k || k.equals(oldEntry.getKey())) {
return oldEntry.getValue();
}
}
}
return null;
}
/**
* 计算Key在数组的下标
* @param k
* @return
*/
private int getIndex(K k) {
int index = k.hashCode() % this.capacity;
return index >= 0 ? index : -index;
}
/**
* 扩容方法。将数组容量扩大一倍。原来的数据重新计算在数组的位置。
*/
private void expand() {
this.size = 0;
this.capacity = this.capacity * 2;
Entry<K, V>[] newTable = new Entry[this.capacity];
List<Entry<K, V>> list = new ArrayList<>();
for (int i = 0; i < this.table.length; i++) {
// 数组的某个位置元素为空不处理。
if (table[i] == null) {
continue;
}
Entry<K, V> entry = table[i];
// 当前数组位置只有一个元素,链表上没有其他数据
if (entry.next == null) {
list.add(entry);
} else {
// 添加链表上所有的元素
while (entry != null) {
Entry<K, V> oldEntry = entry;
entry = entry.next;
// 这里将当前元素的下一个元素设置为null,重新计算next。
oldEntry.next = null;
list.add(oldEntry);
}
}
}
// 重新计算元素在数组的index
for (int i = 0; i < list.size(); i++) {
Entry<K, V> entry = list.get(i);
this.put(entry.getKey(), entry.getValue());
}
this.table = newTable;
}
/**
* 链表结构,存储数组的元素key,value和下一个元素
*
* @author Administrator
*
* @param <K>
* @param <V>
*/
class Entry<K, V> {
// key
K k;
// value
V v;
// 下一个元素,即通过hash函数计算出index相同的元素
Entry<K, V> next;
public Entry(K k, V v, Entry<K, V> next) {
this.k = k;
this.v = v;
this.next = next;
}
public V getValue() {
return v;
}
public K getKey() {
return k;
}
}
}

测试类:

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
public class Test {
public static void main(String[] args) {
Long t1 = System.currentTimeMillis();
MyMap<String, String> myMap = new MyHashMap<>(1000);
for (int i = 0; i < 1000; i++) {
myMap.put("key" + i, "value" + i);
}
for (int i = 0; i < 1000; i++) {
System.out.println("key" + i + " value:" + myMap.get("key" + i));
}
Long t2 = System.currentTimeMillis();
System.out.println("自己写的HashMap耗时:" + (t2-t1));
System.out.println("======================HashMap==========================");
Long t3 = System.currentTimeMillis();
Map<String, String> map = new HashMap<>(1000);
for (int i = 0; i < 1000; i++) {
map.put("key" + i, "value" + i);
}
for (int i = 0; i < 1000; i++) {
System.out.println("key" + i + " value:" + map.get("key" + i));
}
Long t4 = System.currentTimeMillis();
System.out.println("JDK的HashMap耗时:" + (t4-t3));
}
}