java.util.HashMap源码初探

89 阅读 0 评论 59 点赞

我是靠谱客的博主害怕奇迹，这篇文章主要介绍java.util.HashMap源码初探，现在分享给大家，希望可以做个参考。

对于一个存储类的分析，无非从两点入手：存储用的数据结构，存储的运行机制。

数据结构：

数组

复制代码

1
2
3
4
5

/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;

Entry

链表格式。

也即，HashMap中采用的是“链接法”来处理碰撞问题的。

运行机制：

put、get

put方法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

get方法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
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;
}

可以看出，重要的一句代码为：

复制代码

1
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

这句代码的作用是判断两个Key对象是否“相同”，这里的相同的意思是指两个Key完全可以不分彼此，可以作为同一个Key使用。

在put方法中，如果两个Key的hashCode相同，且equals符合，这里是把原有的的value替换成新的value。

测试代码：

复制代码

package test.junit;
import java.util.HashMap;
import junit.framework.TestCase;
/**
* HashMap中判断两个Key是否相同：先判断hashCode，在判断是否equals
* e.hash == hash && ((k = e.key) == key || key.equals(k))
* @author xuefeng
*
*/
public class HashMapTest extends TestCase {
/**
* v1和v4的hashCode相同，但是equals不符合，所以v1和v4会组成一个链表。
*/
public void testKey1() {
HashMap<Key, Value> map = new HashMap<Key, Value>();
Key k1 = new Key(1);
Key k4 = new Key(4);
Value v1 = new Value(1);
Value v4 = new Value(4);
map.put(k1, v1);
map.put(k4, v4);
assertEquals(v1, map.get(k1));
assertEquals(v4, map.get(k4));
}
/**
* v1和v4的hashCode相同，而且equals也符合，所以v1会被v4替换掉，k1和k4指向同一个v4。
*/
public void testKey2() {
HashMap<Key2, Value> map = new HashMap<Key2, Value>();
Key2 k1 = new Key2(1);
Key2 k4 = new Key2(4);
Value v1 = new Value(1);
Value v4 = new Value(4);
map.put(k1, v1);
map.put(k4, v4); // 这里会替换掉v1
//
assertEquals(v1, map.get(k1));
assertEquals(v4, map.get(k1));
assertEquals(v4, map.get(k4));
}
}
class Key {
public int m;
public Key(int m) {
this.m = m;
}
@Override
public int hashCode() {
return m%3;
}
}
class Value {
public int m;
public Value(int m) {
this.m = m;
}
}
class Key2 {
public int m;
public Key2(int m) {
this.m = m;
}
@Override
public int hashCode() {
return m%3;
}
@Override
public boolean equals(Object obj) {
if(obj == null || !(obj instanceof Key2)) return false;
Key2 other = (Key2)obj;
return this.hashCode() == other.hashCode();
}
}

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
package test.junit;
import java.util.HashMap;
import junit.framework.TestCase;
/**
* HashMap中判断两个Key是否相同：先判断hashCode，在判断是否equals
* e.hash == hash && ((k = e.key) == key || key.equals(k))
* @author xuefeng
*
*/
public class HashMapTest extends TestCase {
/**
* v1和v4的hashCode相同，但是equals不符合，所以v1和v4会组成一个链表。
*/
public void testKey1() {
HashMap<Key, Value> map = new HashMap<Key, Value>();
Key k1 = new Key(1);
Key k4 = new Key(4);
Value v1 = new Value(1);
Value v4 = new Value(4);
map.put(k1, v1);
map.put(k4, v4);
assertEquals(v1, map.get(k1));
assertEquals(v4, map.get(k4));
}
/**
* v1和v4的hashCode相同，而且equals也符合，所以v1会被v4替换掉，k1和k4指向同一个v4。
*/
public void testKey2() {
HashMap<Key2, Value> map = new HashMap<Key2, Value>();
Key2 k1 = new Key2(1);
Key2 k4 = new Key2(4);
Value v1 = new Value(1);
Value v4 = new Value(4);
map.put(k1, v1);
map.put(k4, v4); // 这里会替换掉v1
//
assertEquals(v1, map.get(k1));
assertEquals(v4, map.get(k1));
assertEquals(v4, map.get(k4));
}
}
class Key {
public int m;
public Key(int m) {
this.m = m;
}
@Override
public int hashCode() {
return m%3;
}
}
class Value {
public int m;
public Value(int m) {
this.m = m;
}
}
class Key2 {
public int m;
public Key2(int m) {
this.m = m;
}
@Override
public int hashCode() {
return m%3;
}
@Override
public boolean equals(Object obj) {
if(obj == null || !(obj instanceof Key2)) return false;
Key2 other = (Key2)obj;
return this.hashCode() == other.hashCode();
}
}