详解HashMap之put与get

本文将讲述HashMap底层是通过什么数据结构实现的，以及如何计算Key的Hash值，包括初始容量以及为什么这么设计，以及HashMap的扩容机制。

put源码解析

点击显示put源码（源码已添加详细注释）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K, V>[] tab;  // tab 表示当前 hash 散列表的引用
    Node<K, V> p; // 表示具体的散列表中的元素
    int n, i; // 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) // 如果链表长度达到树化阈值，将链表转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 如果找到相同键的节点，结束遍历
                    break;
                p = e; // 继续遍历下一个节点
            }
        }
        if (e != null) { // 如果找到相同键的节点，更新节点的值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; // 修改次数+1，多线程环境下如果modCount不同，则抛出异常（HashMap不是线程安全的）
    if (++size > threshold) // 如果哈希表中的节点数量超过阈值，进行扩容
        resize();
    afterNodeInsertion(evict);
    return null; // 返回null表示插入操作成功
}

上述代码的逻辑步骤整理如下：

1. 如果哈希表为空，进行扩容（首次添加数据）
2. 如果当前节点（桶）没有数据，则直接新建节点
3. 如果当前节点有数据，则遍历列表然后分情况处理
   1. 如果key相同则替换
   2. 如果是红黑树则调用红黑树的插入方法
   3. 使用尾插法插入数据，如果长度超过8则转换为红黑树、

为什么使用尾插法？

如果使用头插法需要更新数组中头节点信息，且因为需要判断该节点的key是否有和传入的key相同，因此遍历链表的过程是必不可少的，在遍历到链表尾确定key没有相同的后，此时直接创建新节点即可

get源码解析

点击显示get源码（源码已添加详细注释）

final HashMap.Node<K, V> getNode(int hash, Object key) {
    HashMap.Node<K, V>[] tab; //当前HashMap的散列表的引用
    HashMap.Node<K, V> first, e; //first：桶头元素 e：用于存放临时元素
    int n; // table 数组的长度
    K k; // 元素中的 k

    // 判断table数组不为空，长度大于0，且计算出的索引位置上的第一个节点不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

        // 检查第一个节点是否是要查找的节点
        if (first.hash == hash && // hash值相等
            ((k = first.key) == key || (key != null && key.equals(k)))) { // key相等
            return first; // 返回第一个节点
        }

        // 如果第一个节点不是要查找的节点，则继续遍历链表或红黑树
        if ((e = first.next) != null) {
            // 如果第一个节点是红黑树的节点，则调用红黑树的查找方法
            if (first instanceof HashMap.TreeNode) {
                return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
            }

            // 遍历链表中的节点，查找与指定key相等的节点
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    return e; // 返回找到的节点
                }
            } while ((e = e.next) != null); // 继续遍历下一个节点
        }
    }
    return null; // 没有找到匹配的节点，返回null
}

上述代码的逻辑步骤整理如下：

1. 判断table数组是否为空
2. 通过Hash值在数组找到数据，Hash值相当于数组下标
3. 先判断第一个节点是否为寻找的key（因为Hash碰撞的概率比较低，通常不需要遍历）
4. 如果第一个节点不是，则遍历链表或红黑树