HashMap实现原理（JDK1.8）

1 //Node是单向链表，它实现了Map.Entry接口
2 static class Node<k,v> implements Map.Entry<k,v> {
3 final int hash;
4 final K key;
5 V value;
6 Node<k,v> next;
7 //构造函数Hash值 键 值 下一个节点
8 Node(int hash, K key, V value, Node<k,v> next) {
9 this.hash = hash;
10 this.key = key;
11 this.value = value;
12 this.next = next;
13 }
14
15 public final K getKey() { return key; }
16 public final V getValue() { return value; }
17 public final String toString() { return key + = + value; }
18
19 public final int hashCode() {
20 return Objects.hashCode(key) ^ Objects.hashCode(value);
21 }
22
23 public final V setValue(V newValue) {
24 V oldValue = value;
25 value = newValue;
26 return oldValue;
27 }
28 //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
29 public final boolean equals(Object o) {
30 if (o == this)
31 return true;
32 if (o instanceof Map.Entry) {
33 Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;
34 if (Objects.equals(key, e.getKey()) &&
35 Objects.equals(value, e.getValue()))
36 return true;
37 }
38 return false;
39 }

1 //红黑树
2 static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
3 TreeNode<k,v> parent; // 父节点
4 TreeNode<k,v> left; //左子树
5 TreeNode<k,v> right;//右子树
6 TreeNode<k,v> prev; // needed to unlink next upon deletion
7 boolean red; //颜色属性
8 TreeNode(int hash, K key, V val, Node<k,v> next) {
9 super(hash, key, val, next);
10 }
11
12 //返回当前节点的根节点
13 final TreeNode<k,v> root() {
14 for (TreeNode<k,v> r = this, p;;) {
15 if ((p = r.parent) == null)
16 return r;
17 r = p;
18 }
19 }

1 //构造函数1
2 public HashMap(int initialCapacity, float loadFactor) {
3 //指定的初始容量非负
4 if (initialCapacity < 0)
5 throw new IllegalArgumentException(Illegal initial capacity: +
6 initialCapacity);
7 //如果指定的初始容量大于最大容量,置为最大容量
8 if (initialCapacity > MAXIMUM_CAPACITY)
9 initialCapacity = MAXIMUM_CAPACITY;
10 //填充比为正
11 if (loadFactor <= 0 || Float.isNaN(loadFactor))
12 throw new IllegalArgumentException(Illegal load factor: +
13 loadFactor);
14 this.loadFactor = loadFactor;
15 this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值
16 }
17
18 //构造函数2
19 public HashMap(int initialCapacity) {
20 this(initialCapacity, DEFAULT_LOAD_FACTOR);
21 }
22
23 //构造函数3
24 public HashMap() {
25 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
26 }
27
28 //构造函数4用m的元素初始化散列映射
29 public HashMap(Map<!--? extends K, ? extends V--> m) {
30 this.loadFactor = DEFAULT_LOAD_FACTOR;
31 putMapEntries(m, false);
32 }

1 public V get(Object key) {
2 Node<K,V> e;
3 return (e = getNode(hash(key), key)) == null ? null : e.value;
4 }
5 /**
6 * Implements Map.get and related methods
7 *
8 * @param hash hash for key
9 * @param key the key
10 * @return the node, or null if none
11 */
12 final Node<K,V> getNode(int hash, Object key) {
13 Node<K,V>[] tab;//Entry对象数组
14 Node<K,V> first,e; //在tab数组中经过散列的第一个位置
15 int n;
16 K k;
17 /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/
18 //也就是说在一条链上的hash值相同的
19 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
20 /*检查第一个Node是不是要找的Node*/
21 if (first.hash == hash && // always check first node
22 ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同
23 return first;
24 /*检查first后面的node*/
25 if ((e = first.next) != null) {
26 if (first instanceof TreeNode)
27 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
28 /*遍历后面的链表，找到key值和hash值都相同的Node*/
29 do {
30 if (e.hash == hash &&
31 ((k = e.key) == key || (key != null && key.equals(k))))
32 return e;
33 } while ((e = e.next) != null);
34 }
35 }
36 return null;
37 }

1 /**
2 * Initializes or doubles table size. If null, allocates in
3 * accord with initial capacity target held in field threshold.
4 * Otherwise, because we are using power-of-two expansion, the
5 * elements from each bin must either stay at same index, or move
6 * with a power of two offset in the new table.
7 *
8 * @return the table
9 */
10 final Node<K,V>[] resize() {
11 Node<K,V>[] oldTab = table;
12 int oldCap = (oldTab == null) ? 0 : oldTab.length;
13 int oldThr = threshold;
14 int newCap, newThr = 0;
15
16 /*如果旧表的长度不是空*/
17 if (oldCap > 0) {
18 if (oldCap >= MAXIMUM_CAPACITY) {
19 threshold = Integer.MAX_VALUE;
20 return oldTab;
21 }
22 /*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/
23 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
24 oldCap >= DEFAULT_INITIAL_CAPACITY)
25 /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/
26 newThr = oldThr << 1; // double threshold
27 }
28 /*如果旧表的长度的是0，就是说第一次初始化表*/
29 else if (oldThr > 0) // initial capacity was placed in threshold
30 newCap = oldThr;
31 else { // zero initial threshold signifies using defaults
32 newCap = DEFAULT_INITIAL_CAPACITY;
33 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
34 }
35
36
37
38 if (newThr == 0) {
39 float ft = (float)newCap * loadFactor;//新表长度乘以加载因子
40 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
41 (int)ft : Integer.MAX_VALUE);
42 }
43 threshold = newThr;
44 @SuppressWarnings({"rawtypes","unchecked"})
45 /*下面开始构造新表，初始化表中的数据*/
46 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
47 table = newTab;//把新表赋值给table
48 if (oldTab != null) {//原表不是空要把原表中数据移动到新表中
49 /*遍历原来的旧表*/
50 for (int j = 0; j < oldCap; ++j) {
51 Node<K,V> e;
52 if ((e = oldTab[j]) != null) {
53 oldTab[j] = null;
54 if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
55 newTab[e.hash & (newCap - 1)] = e;
56 else if (e instanceof TreeNode)
57 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
58 /*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/
59 else { // preserve order保证顺序
60 ////新计算在新表的位置，并进行搬运
61 Node<K,V> loHead = null, loTail = null;
62 Node<K,V> hiHead = null, hiTail = null;
63 Node<K,V> next;
64
65 do {
66 next = e.next;//记录下一个结点
67 //新表是旧表的两倍容量，实例上就把单链表拆分为两队，
68 //e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对
69 if ((e.hash & oldCap) == 0) {
70 if (loTail == null)
71 loHead = e;
72 else
73 loTail.next = e;
74 loTail = e;
75 }
76 else {
77 if (hiTail == null)
78 hiHead = e;
79 else
80 hiTail.next = e;
81 hiTail = e;
82 }
83 } while ((e = next) != null);
84
85 if (loTail != null) {//lo队不为null，放在新表原位置
86 loTail.next = null;
87 newTab[j] = loHead;
88 }
89 if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置
90 hiTail.next = null;
91 newTab[j + oldCap] = hiHead;
92 }
93 }
94 }
95 }
96 }
97 return newTab;
98 }