[数据结构与算法]HashMap的put流程（源码分析）

//我们所调用的put方法
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

其中传入的hash函数

//key值如果为空则hash为0，如果不为空则高16位异或上低16位置，主要是为了减少hash冲突，具体的在源码中有解释
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

具体实现put的方法
扩容函数，会重新计算hashmap里面对应元素的hash并放到不同的元素上

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; 
		Node<K,V> p;
		//n 数组长度 
		int n, i;
		//如果数组是空的，或者数组的长度为0，则对数组进行初始化 或者 进行扩容 
        if ((tab = table) == null || (n = tab.length) == 0)  
            n = (tab = resize()).length;
		//如果插入的位置为空的，那么当前位置等于直接new一个新的Node 
		//(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;
			//目前这个值的hash==计算出的数组下标对应的hash 且它们的key值也相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
			//p是一个TreeNode
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
			//p为链表节点，且存在冲突
            else {
                for (int binCount = 0; ; ++binCount) {
					//如果下一个节点为空，则复制给下一个节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
						//如果链表长度>=树化的值（默认为8）
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
							//在这个函数里面会判断这个当前数组的长度是否达到了最小的树化大小（默认64），如果没有则会进行扩容
                            treeifyBin(tab, hash);
                        break;
                    }
					//在链表中找到了相同key的节点
                    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;
            }
        }
		//这个数字记录HashMap结构性的修改
		//映射关系的修改或者内部结构的修改
		/ This field is used to make iterators on Collection-views of the HashMap fail-fast. 
        ++modCount;
		//如果目前的数组的大小大于阈值 那么就进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

大概流程总结下来就是
1.如果当前数组是空就初始化或者扩容
2.如果计算出来的数组下标中没有值，那么直接插入
3.如果hash冲突，判断是否为红黑树结构，如果是的那么插入到红黑树中，如果不是则遍历链表，插入到链表中，插入之后会判断链表长度是否》=8且数组长度>=64，如果是则会转换为红黑树结构
4.如果其中存在一摸一样的key那么就修改值
5.最后判断数组容量是否大于阈值，如果是的，那么就扩容