HashMap实现原理(JDK1.8)

HashMap实现原理(JDK1.8)


如果突然被同行问起HashMap的实现原理,你会不会和我一样词穷。

下面是看完HashMap源码的一些感受和心得。

HashMap是实现了Map接口,而HashMap底层实际为链表+数组,可以看到源码中的Node<K,V>[] table,Node则是Map中的Entry集合的实现。transient修饰则是不参与Java中的序列化。


源码

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
HashMap源码部分

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {

/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;

/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;

}

看到HashMap是继承了一个抽象的Map类,实现了Map接口,Cloneable接口和Jdk序列化接口。


Cloneable接口

Cloneable接口其实只是一个空的接口,没有任何其他信息,通过实现了这个接口,程序就可以认为HashMap具备了clone,而实际其中的clone方法是存在了Object类中,而HashMap实现的clone方法,是因为继承了
AbstractMap。


AbstractMap

1
2
3
4
5
6
7
8
9
10
11
源码部分
public abstract class AbstractMap<K,V> implements Map<K,V> {
/**
* Sole constructor. (For invocation by subclass constructors, typically
* implicit.)
*/
protected AbstractMap() {
}

public abstract Set<Entry<K,V>> entrySet();
}

首先看到AbstractMap,它也是实现了一个Map接口,但是是被声明成了抽象的类,这里就涉及到了抽象的概念,抽象类不能被实例化,但是他的子类被实例化后可以引用他的方法,继承了抽象类,一定需要实现抽象方法,普通方法可以不实现。可以看到该类中abstract只出现了一次,而且是修饰了Set接口。


Map接口

Map接口都知道是键值对,一个键对应一个值,看到Map接口注释时,做着进行了说明:

1
2
3
4
5
6
An object that maps keys to values.  A map cannot contain duplicate keys;
each key can map to at most one value.

意思大概是,
将键映射到值的对象。映射不能包含重复键;
每个键最多只能映射到一个值。

HashMap在初始化,在源码中的构造方法中,有一个默认的initialCapacity,HashMap根据初始容量来进行链表的大小初始化;

而且HashMap中没有出现synchronized来进行方法同步,所以HashMap和HashTable比起来运行速度更快。

且HashMap键可以为null,是因为HashMap在put的时候做了判断
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);