HashMap中的get,put方法源码解析(超详细)

 get

HashMap中的get方法，点进来发现 

• 借助hash(key)方法算出键的哈希值。
• 查找节点：调用getNode方法，利用前面得到的哈希值以及键本身去查找对应的节点。
• 返回结果：要是找到了节点，就返回该节点的值；若没找到，就返回null。

 先进行判断 如果tab是空 直接返回null

不是的话进行往下判断 先判断头结点的hash值以及key值是否和目标相等，相等返回头结点。

为什么要对头结点单独进行一次判断呢 因为头结点是最常被访问到的，单独对头节点进行检查，能够避免执行遍历链表或树的操作，从而显著提升查找的效率。

如果不是头结点，继续往下判断，判断是否是红黑树，是的话通过getTreeNode在树中查找，不是就在链表中遍历比对，找到了返回，

 while ((e = e.next) != null);

然后移动下一个节点。

红黑树的查找逻辑，判断是否有父节点，有的话root() 往上找根节点，没有的话这个节点就是根节点，再从根节点开始按红黑树逻辑进行查找。

这段代码是在二次哈希，目的是减少哈希冲突

如果键等于null那么直接返回0，否则将key的哈希值与无符号右移16位进行异或 

first = tab[(n - 1) & hash]) != null

 说明一下这里 n必须是2的幂次方。这样-1的二进制就是一堆1了，此时相当于取模，只不过位运算更高效

• tab[(n - 1) & hash]：通过哈希值和数组长度的位运算，计算出键对应的数组索引，并获取该位置的头节点 first。
• first != null：判断该位置是否已存在元素（链表头节点或树节点）。

 put

 put和get其实差不多

 hash(key)：调用hash方法计算键的哈希值 减少哈希冲突

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;

 判断tab是否为null或数组长度是否为0，进行resize()初始化

• 首次初始化时，默认容量为16，负载因子为0.75，阈值（扩容临界点）为16 × 0.75 = 12。

if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}

主要分析这里就可以 这是是如果旧容量已经达到了最大值，那么就不在进行扩容，不然就直接左移一位，扩大两倍的容量。 

i = (n - 1) & hash：通过哈希值和数组长度的位运算确定桶位置。

• p = tab[i]：获取桶位置的头节点。
• p == null：若为空，说明该位置没有元素，直接插入新节点。

如果有值，那么进行判断hash与key还有equals 相等然后进行赋值替换。

桶有值且键不相等的话，继续往下面执行 判断是红黑树还是链表

else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}

 如果是链表的话，若遍历到尾节点，直接创建节点插入值，如果没有遍历到尾节点就发现有相等的键 那么直接标记，然后退出循环，在进行赋值覆盖。

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);

这一步是如果创建的节点使得大于等于8 那么就会由链表转成树

注意

 我们会发现如果tab小于64那么不会转成红黑树 而是先进行resize()进行扩容 然后如果超过了64 那那么才会转成红黑树

最后

  ++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;

++size size如果超过了阈值那么也触发 resize()进行扩容