HashMap（get和put）jdk8

get逻辑：

1. HashMap数据结构为数组加链表加红黑树、只有当链表数量大于8时、才将链表转换为红黑树、时间复杂度由链表的O(N)转换为红黑树的O(logN)
3. // 主要看getNode下的方法、传入key的hash值和key
4. public V get(Object key) {
5.     Node<K,V> e;
6.     return (e = getNode(hash(key), key)) == null ? null : e.value;
7. }
9. // 返回一个Node对象、包含了key和value、在get方法中在返回value值
10. final Node<K,V> getNode(int hash, Object key) {
11.     // tab：Node<K, V>对象数组
12.     Node<K,V>[] tab;
13.     // first: 指向key hash值对应的数组值 e: first对应Node对象的下一个节点
14.     Node<K,V> first, e;
15.     // n: 指向当前HashMpa的数组长度
16.     int n;
17.     // k: 临时变量、指向 key
18.     K k;
19.     // 这里检测HashMap对象的数组是否存在、长度是否大于0、((n - 1) & hash)根据此表达式算出key对应的数组位置、在检查是否存在对象。
20.     if (
21.         (tab = table) != null &&
22.         (n = tab.length) > 0 &&
23.         (first = tab[(n - 1) & hash]) != null
24.     ) {
25.         // first当前值为一个Node节点
26.         // 这个if是检测当前的first指向的Node是否是要获取的对象
27.         // 直接判断first的hash值和要获取的hash值是否一直、并且key的值是否一直、通过 ==判断地址!=null和equals判断、key赋值为first的key
28.         if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
29.             // 判断一致后直接返回要获取的Node节点给get、get在返回Node的value值
30.             return first;
31.         // 由于上面查找都查找不到、所以要查找Node的下一个节点、即查询链表或者红黑树
32.         if ((e = first.next) != null) {
33.             // 检查first对象是否是TreeNode（红黑树）
34.             if (first instanceof TreeNode)
35.                 // 当前first为红黑树对象、直接根据key调用内部的检索方法获取对应的value
36.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
37.             do {
38.                 // 链表查询、由于first上面判断过不是要查找的对象、e在上面语句已经指向first下一个节点、所以直接开始判断
39.                 // 和上面的判断一样、检查hash值和key、qeuals判断、如果有则返回对应的Node对象、没有则最终执行下面的return null;语句。
40.                 if (e.hash == hash &&
41.                     ((k = e.key) == key || (key != null && key.equals(k))))
42.                     return e;
43.             } while ((e = e.next) != null);
44.         }
45.     }
46.     // 表示当前对象并没有存储相关的key值、返回null
47.     return null;
48. }

复制代码

put逻辑

1. public V put(K key, V value) {
2.     // 内部调用putVal设置值、参数如下int hash, K key, V value, boolean onlyIfAbsent（如果为 true，则不更改现有值）,boolean evict（如果为 false，则表处于创建模式）
3.     return putVal(hash(key), key, value, false, true);
4. }
6. // 参数如下int hash, K key, V value, boolean onlyIfAbsent（如果为 true，则不更改现有值）,boolean evict（如果为 false，则表处于创建模式）
7. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
8.                boolean evict) {
9.     // tab指向当前HashMap对象数组
10.     Node<K,V>[] tab;
11.     // p指向key的hash值所在的数组Node对象
12.     Node<K,V> p;
13.     // n：HashMap数组的长度、i：key的hash值对应的索引（index）
14.     int n, i;
15.     // 判断当前HashMap的数组对象是否为空、并且长度是否为0
16.     if ((tab = table) == null || (n = tab.length) == 0)
17.         // 分配数组空间并把长度返回给n
18.         n = (tab = resize()).length;
19.     // 计算hash对应的索引是否有对象存在、没有的话则创建Node对象、并将要put的值写入Node对象、在返回给数组
20.     if ((p = tab[i = (n - 1) & hash]) == null)
21.         tab[i] = newNode(hash, key, value, null);
22.     // 要将Node对象写入到链表或者红黑树中
23.     else {
24.         // e: 代表最终你要写入的Node对象
25.         Node<K,V> e;
26.         // k: 指向hash值对象的Node节点的key
27.         K k;
28.         // 检查是否是同一个hash值、key是否相对或者进行equals判断
29.         if (p.hash == hash &&
30.             ((k = p.key) == key || (key != null && key.equals(k))))
31.             // 代表同一个对象、赋值给e、最后在写入值
32.             e = p;
33.         // 检测是否是红黑树节点
34.         else if (p instanceof TreeNode)
35.             // 检测是红黑树对象、直接调用内部的写入方法、在返回一个Node<K, V>节点对象、最后在写入值、putTreeVal里面其实已经写入value了、后面在写入一次。
36.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
37.         else {
38.             // 链表操作、binCount检测有多少个链表节点、根据TREEIFY_THRESHOLD常量设定的值8、超过8个链表节点、则将该链表转换为红黑树
39.             for (int binCount = 0; ; ++binCount) {
40.                 //
41.                 if ((e = p.next) == null) {
42.                     p.next = newNode(hash, key, value, null);
43.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
44.                         // 将数组传入
45.                         treeifyBin(tab, hash);
46.                     break;
47.                 }
48.                 // 检测当前插入的对象是否一致、一致的话直接返回e、下面在将要写入的值赋值给变量e对象
49.                 if (e.hash == hash &&
50.                     ((k = e.key) == key || (key != null && key.equals(k))))
51.                     break;
52.                 p = e;
53.             }
54.         }
55.         // 检测e对象是否不为空、不为空则下面写入对应的value值
56.         if (e != null) { // existing mapping for key
57.             V oldValue = e.value;
58.             // onlyIfAbsent为true表示不更新对象
59.             if (!onlyIfAbsent || oldValue == null)
60.                 // 将值写入
61.                 e.value = value;
62.             afterNodeAccess(e);
63.             return oldValue;
64.         }
65.     }
66.     ++modCount;
67.     // 当前数组长度自增1大于上次扩容长度后、重新扩容并且把重新扩容的大小赋值给threshold
68.     if (++size > threshold)
69.         // 重新调整数组长度
70.         resize();
71.     // LinkedHashMap中重写了、HashMap中没有具体实现
72.     afterNodeInsertion(evict);
73.     // 对应的key无法写入、返回null      
74.     return null;
75. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！