疫情原因，今年的五一没出去浪，在家没事，写个博客记录下Java中HashMap的put操作。
当执行下面这段代码，put一个值的时候，流程是什么样的呢？
HashMap<String, String> map = new HashMap<String, String>();
map.put("姓名", "张三");
//JDK源码
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 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; // (n - 1) & hash 计算下标，为空时直接放入 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 1st treeifyBin(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 key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) // 扩容 resize(); afterNodeInsertion(evict); return null; }
以上是源码，下面引用一张图来理解下上面的代码中寻址的过程：
1、首先会拿着key值，计算出hashcode值，h = key.hashCode()
2、再将该值右移16位后与原值做异或操作，h ^ (h >>> 16)，这个叫扰动函数，目的是让高低16位参与运算减少hash碰撞的几率。
3、然后用 hashCode 和 n-1 做与运算，1.8之前是用 hashCode 对数组长度取模，1.8对算法进行了优化，这样做的效果和对 hashCode 取模是一样的，但是效率会比之前高很多。
这样就找到了key要存放的位置，接下来就是把值放入相应的位置
1、如果没碰撞直接放到bucket里；
2、如果节点已经存在就替换old value；
3、如果碰撞了，以链表的形式存在buckets后；
4、如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
5、当bucket满了(超过load factor*current capacity)时，就要扩容
扩容就是将原数组的长度扩大2倍，重新计算key的 index，重新放入新的buckets中。