关于 put

源码

1、put

调用 hash ，先求 key 的哈希值，再调用 putVal 。

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 * 将指定的值与该地图中指定的键相关联.
 * 如果该 Map 已经包含此键的映射，那么旧值被新值替换.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
/**
 * 计算 key.hashCode() 并将 hash 的高位分散(XORs)到低位.
 * 由于该表使用了2次方掩码，仅在当前掩码以上的位数不同的哈希值集将总是发生碰撞。
 * (已知的例子包括在小表中持有连续整数的Float键的集合）
 * 因此，我们应用一个转换，将高位的影响向下分散。在速度、实用性和位传播的质量之间有一个权衡。
 * 因为许多常见的哈希集已经是合理分布的（所以不受益于传播），而且因为我们使用树来处理大集的碰撞，
 * 我们只是以最便宜的方式 XOR 一些移位的比特，以减少系统损失，以及纳入最高比特的影响，
 * 否则由于表的界限，永远不会被用于索引计算。
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2、putVal


/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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 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;
}

3、putVal 源码注释分析


/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {

    // 定义辅助变量，先讲一下几个变量分别存储的是什么。
    // tab：指向 table，操作 tab 的同时，table 也会跟着改变。
    // n：table 的 length
    // i：key 对应的索引值，计算方法：(n - 1) & hash
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // table 是否为空
    if ((tab = table) == null || (n = tab.length) == 0)
        // 调用 resize 对 table 进行扩容，更新 n 为 table resize 后的长度
        n = (tab = resize()).length;

    // 令 p 指向索引处（table[i]），判断 p 是否为 null
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 索引处（table[i]）为空，调用 newNode 生成一个新结点，令索引处（table[i]）指向生成的新结点，完成结点的新增。
        tab[i] = newNode(hash, key, value, null);
    else {
        // p 不等于 null 

        // 定义辅助变量
        // e：当前处理的结点，差不多类似于游标的作用
        // k：e.key ，当前游标的 key，
        Node<K,V> e; K k;

        // 判断是否产生了哈希冲突，如果是，继续判断 key 是不是重复了
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // key 已经在 hashMap 中存在，令游标 e 指向 p .
            e = p;

        // 如果 p 指向的结点是一颗红黑树
        else if (p instanceof TreeNode)
            // 按照红黑树的规则添加该结点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // p 结点指向的结点是链表头
        else {
            // 遍历链表，记录元素个数
            for (int binCount = 0; ; ++binCount) {
                // 令游标 e 依次向后滑动
                // 如果 e 指向的结点为 null ，则说明遍历到的链表尾部
                if ((e = p.next) == null) {
                    // 调用 newNode 插入到 p.next
                    p.next = newNode(hash, key, value, null);

                    // 如果链表元素个数累计总和大于 8 
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 调用 treeifyBin 则将链表转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }

                // 在链表中发现了一样的元素
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 不做处理
                    break;

                // 配合 for 循环第一句使用，令游标 e 依次向后滑动
                p = e;
            }
        }

        // 如果 e 不等于 null 
        if (e != null) { // existing mapping for key
            // 在 hashMap 中遇到了重复 key

            // 获取旧值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 用新 value 覆盖旧 value
                e.value = value;

            // 扩展点 afterNodeAccess
            afterNodeAccess(e);
            return oldValue;
        }
    }

    // 修改次数加一
    ++modCount;
    // 如果当前 table size 大于扩容阈值，则调用 resize 对 table 扩容
    if (++size > threshold)
        resize();
    // 扩展点 afterNodeInsertion
    afterNodeInsertion(evict);
    // 添加成功，返回 null
    return null;
}

问题

1、key 对应的索引，是如何被计算出来的？

hash：通过调用 HashMap 的 hash 函数，可以得到任意对象的哈希值。为了方便你阅读，我把代码贴在下面：

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

n：table 的 length
i：索引值

算法：i = (n - 1) & hash

2、什么时候会触发 resize 进行扩容

3、什么情况下，会触发树化，由链表转换为红黑树？

关键点在这几行代码

// 如果链表元素个数大等于 7
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    // 调用 treeifyBin 则将链表转换为红黑树
    treeifyBin(tab, hash);

static final int TREEIFY_THRESHOLD = 8;

TREEIFY_THRESHOLD 是 HashMap 中定义的一个常量，当链表上的元素个数大等于 7 个时，就会触发树化条件，调用 treeifyBin 函数。

但是，treeifyBin 函数会先对 table length 做检查，如果 table 为空，或 table length 小于 64 ，就会调用 resize ，所以实际上就不是树化，而是扩容了。

4、modCount 有什么用？

modCount 记录的是 HashMap 对象修改的次数，在 HashMap 的 put(), get(), remove(), Interator() 等方法中,都使用了该属性。由于 HashMap 不是线程安全的，所以在迭代的时候,会将 modCount 赋值到迭代器的 expectedModCount 属性中，然后进行迭代，如果在迭代的过程中 HashMap 被其他线程修改了，modCount 的数值就会发生变化，这个时候 expectedModCount 和 ModCount 不相等，迭代器就会抛出 ConcurrentModificationException() 异常。

5、为什么要执行一些看似无用的空函数？

afterNodeAccess 和 afterNodeInsertion 方法实际上是 HashMap 预留给子类（ LinkedHashMap ）的扩展点，实际上是空方法。

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

Java 知识点

HashMap put 方法源码分析