JAVA基础集合框架【四】HashMap之源码分析putVal

文章首发于：clawhub.club

---

相关源码翻译

Node内部类

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 * 基本哈希桶节点，用于大多数条目。(参见下面的TreeNode子类和LinkedHashMap中的Entry子类。)
 */
static class Node<K, V> implements Entry<K, V> {
    // 哈希值
    final int hash;
    // 键
    final K key;
    // 值
    V value;
    // 写一个Node节点的引用
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final String toString() {
        return key + "=" + value;
    }

    public final int hashCode() {
        // 位异或运算（^）：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Entry<?, ?> e = (Entry<?, ?>) o;
            if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

创建一个常规(非树)节点

// Create a regular (non-tree) node 创建一个常规(非树)节点
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
    return new Node<>(hash, key, value, next);
}

putVal

/**
 * Implements Map.put and related methods
 * 实现了 Map.put及其他相关方法
 * @param hash         键的Hash值
 * @param key          键
 * @param value        值
 * @param onlyIfAbsent 如果为真，则不要更改现有值
 * @param evict        如果为false，则该表处于创建模式。
 * @return 老的值，如果没有，则为空
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //当前表
    Node<K, V>[] tab;
    //桶
    Node<K, V> p;
    //n:表长度
    //i:桶在表中的索引
    int n, i;
    //如果当前表为null或者表长度为0
    if ((tab = table) == null || (n = tab.length) == 0)
        //扩容操作,初始化
        n = (tab = resize()).length;
    //如果 键所在的桶 为null
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 新建桶
        tab[i] = newNode(hash, key, value, null);

    //如果 键所在的桶 不为null
    else {
        //当前key节点
        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) {
                //如果桶的下一个节点为null
                if ((e = p.next) == null) {
                    //创建节点
                    p.next = newNode(hash, key, value, null);
                    //如果大于树化阈值
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //将链表转为红黑树  后期分析
                        treeifyBin(tab, hash);
                    //跳出循环
                    break;
                }
                //在链表中找到了key
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    //跳出循环
                    break;
                p = e;
            }
        }
        //存在key节点
        if (e != null) { // existing mapping for key
            //老的值
            V oldValue = e.value;
            // onlyIfAbsent如果为真，则不要更改现有值
            if (!onlyIfAbsent || oldValue == null)
                //更改现有值
                e.value = value;
            //回调
            afterNodeAccess(e);
            //返回旧的值
            return oldValue;
        }
    }
    //修改计数器加一
    ++modCount;
    //判断是否需要扩容
    if (++size > threshold)
        //扩容操作
        resize();
    //回调
    afterNodeInsertion(evict);
    //返回null
    return null;
}

流程分析

例子一：

参考资料：https://snailclimb.gitee.io/javaguide/#/./java/HashMap

1. 如果定位到的数组位置没有元素 就直接插入。
2. 如果定位到的数组位置有元素就和要插入的key比较，如果key相同就直接覆盖，如果key不相同，就判断p是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

例子二：

参考资料：https://zhuanlan.zhihu.com/p/21673805

1. 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
5. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。