HashMap源码理解一下？

时间：2021-05-21 09:43:11 阅读：31 评论：0 收藏：0 [点我收藏+]

HashMap 是一个散列桶（本质是数组+链表），散列桶就是数据结构里面的散列表，每个数组元素是一个Node节点，该节点又链接着多个节点形成一个链表，故一个数组元素 = 一个链表，利用了数组线性查找和链表修改的便利性(横向=Node数组，横向只存放每个链表第一个节点，通过数组下标维持每个Node链表第一个节点的关系；纵向=Node链表，纵向是通过链表中的next维持某个Node链表所有节点的关系）
HashMap 可以接受 null 键和null值，而 Hashtable 则不能
每个Node节点的hash、key值都不同，故插入数据时会比对hash、key值，同则替换value，不同则插入新Node节点

技术分享图片

HashMap 的put()和get()源码理解：

put()过程源码：

 1 public V put(K key, V value) {
 2         return putVal(hash(key), key, value, false, true);
 3     }
 4     //散列算法计算key的hash值
 5     static final int hash(Object key) {
 6         int h;
 7         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 8     }
 9  
10     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
11                    boolean evict) {
12         Node<K,V>[] tab; Node<K,V> p; int n, i;
13         if ((tab = table) == null || (n = tab.length) == 0)
14             n = (tab = resize()).length;   【注释1】
15         if ((p = tab[i = (n - 1) & hash]) == null)    【注释2】
16             tab[i] = newNode(hash, key, value, null);
17         else {
18             Node<K,V> e; K k;
19             if (p.hash == hash &&
20                 ((k = p.key) == key || (key != null && key.equals(k)))) 【注释3】
21                 e = p;
22             else if (p instanceof TreeNode)   【注释4】
23                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24             else {
25                 for (int binCount = 0; ; ++binCount) {
26                     if ((e = p.next) == null) {
27                         p.next = newNode(hash, key, value, null);  【注释6】
28                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
29                             treeifyBin(tab, hash);               【注释7】
30                         break;
31                     }
32                     if (e.hash == hash &&   
33                         ((k = e.key) == key || (key != null && key.equals(k))))
34                         break;         【注释5】
35                     p = e;
36                 }
37             }
38             if (e != null) { 【注释30】
39                 V oldValue = e.value;
40                 if (!onlyIfAbsent || oldValue == null)
41                     e.value = value;
42                 afterNodeAccess(e);
43                 return oldValue;
44             }
45         }
46         ++modCount;
47         if (++size > threshold)          【注释8】
48             resize();
49         afterNodeInsertion(evict);
50         return null;
51     }

由上：hashMap插入元素时，传入hash值+key+value，先获取当前的桶=node数组，如果当前桶为null则初始化【注释1】；

然后根据key算出hash值，再根据hash值算出node数组的下标，如果对应下标位置的node节点为null则新建node节点【注释2】；

如果对应下标位置node节点不为null且该位置的hash值、key值与传入的相等，则用新节点的value覆盖该位置的value【注释3、注释30】；

如果对应下标位置node节点不为null且该位置的hash值与key值、传入的不相等：则先判断该位置是不是红黑树节点，若是则把构建并插入新的红黑树节点【注释4】；若不是红黑树节点则该位置节点是链表，则遍历该链表，遍历过程中若链表中节点得hash值、key值与传入的hash值、key值相同，则用新节点的value覆盖该位置的value【注释5、注释30】；遍历过程中若链表中节点得hash值、key值与传入的hash值、key值不相同，则在链表结尾插入新节点【注释6】，插入之后若该链表长度大于TREEIFY_THRESHOLD值=8，则把链表转为红黑树【注释7，但注释7的treeifyBin()方法并不会马上把链表转为红黑树，如果“横向=Node数组”的长度大于64时才转，小于64就扩容resize()】；

最后检查hashMap总node节点个数大于容量阀值threshold，则扩容resize()【注释8，扩容把容量和阀值都增大为2倍；疑问：在第43行的时候已经返回了value值，那么第46行以后的代码是不会执行的，那怎么扩容?】

get()过程源码：

 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  final Node<K,V> getNode(int hash, Object key) {
 7     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 8     if ((tab = table) != null && (n = tab.length) > 0 &&
 9         (first = tab[(n - 1) & hash]) != null) {
10        if (first.hash == hash && // always check first node
11             ((k = first.key) == key || (key != null && key.equals(k))))
12             return first; 【注释1】
13         if ((e = first.next) != null) {
14             if (first instanceof TreeNode)
15                 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 【注释2】
16             do { 【注释3】
17                if (e.hash == hash &&
18                    ((k = e.key) == key || (key != null && key.equals(k))))
19                     return e;
20             } while ((e = e.next) != null);
21         }
22     }
23     return null;
24  }
25 
26 final TreeNode<K,V> getTreeNode(int h, Object k) {
27    return ((parent != null) ? root() : this).find(h, k, null);
28 }

由上：首先根据key算出hash值，再根据hash值算出node数组的下标，如果对应下标位置的链表头node节点，它的hash值、key值与传入的相等，则返回该节点value【注释1】；

如果对应下标位置的链表头node节点，它的hash值、key值与传入的不相等，则先检查该头node节点是否是红黑树节点，若是则从红黑树中查找目标节点【注释2】，即调用getTreeNode中红黑树节点的find()方法，find()源码见下图；

如果该头node不是红黑树节点而是普通的链表节点，则遍历链表查找目标节点【注释3】；

(find方法源码在TreeNode节点=红黑树节点定义中：TreeNode继承LinkedHashMap.Entry，而LinkedHashMap.Entry继承HashMap.Node，所以TreeNode是HashMap.Node的子类，即红黑树TreeNode节点是普通链表Node节点的子类节点)

技术分享图片

---------------------------------------------------------------------------------------------------