转载

hashmap源码-元素put，get

注意，本系列文章都是基于 jdk 1.8

这是 hashmap 源码系列文章的第二篇，前面我们主要讲解了 hashmap 中 hash 算法的实现，本文则是带大家了解元素 get, put 的相关实现，这样一来 hashmap 的大体框架就描绘完毕了。

内容主要涉及：

hashmap 初始化时机
元素 put 流程
元素 get 流程

初始化时机

还记得前面我们提到 hashmap 是类似于『懒加载』的机制进行初始化，而触发初始化的操作正是在第一次往 hashmap 中 put 元素。

简单测试一下，通过反射获取 hashmap 底层的数组对象 table。

public static void main(String[] args) throws Exception {
    HashMap<String, String> hashMap = new HashMap(10);
    Field tableField = HashMap.class.getDeclaredField("table");
    tableField.setAccessible(true);
    Object table = tableField.get(hashMap);
    System.out.println("put 操作前 table 对象：" + table);
    hashMap.put("1", "a");
    table = tableField.get(hashMap);
    System.out.println("put 操作后 table 对象：" + table);
}
复制代码

运行结果：

put 操作前 table 对象：null
put 操作前 table 对象：[Ljava.util.HashMap$Node;@610455d6

Process finished with exit code 0
复制代码

元素 put

下面我们就来了解 hashmap 中关于 put 操作的实现原理。

看到 put 方法，将键值传入之后，最终调用的是 putVal() 这个方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
复制代码

先来看到 putVal() 的参数列表：

final V putVal(int hash, 
               K key, 
               V value, 
               boolean onlyIfAbsent,
               boolean evict)
复制代码

hash：key 对应的 hash 值

key：元素 key
value：需要设置的值
onlyIfAbsent：是否覆盖 key 原有的值，如果为 true，则不进行覆盖，可以看到这个参数默认是 false
evict：为扩展类 linkedhashmap 提供的参数

开始讲解方法主体，由于方法比较复杂，我们拆分开来讲。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 判断数组是否为空，如果是则进行初始化，resize方法中包含了数组初始化操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // key 通过 hash 映射到的数组位置如果为空，则直接将当前键值加入该索引位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
      //如果 key 映射到的数组位置上已经存在元素
    }
    // 后续代码暂时省略
}
复制代码

如果 key 映射到的数组位置上已经存在元素，接着往下：

Node<K,V> e; K k;
// 比较该位置存在的键是否与当前 key 相等
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    // 如果是则将其存储到 e 变量
    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;
        }
        // 在遍历链表的过程中，发现 key 已经存在，则停止遍历
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}
// key 已经存在
if (e != null) {
    V oldValue = e.value;
    // 如果 onlyIfAbsent 设置为 false，或者原值为 null 的情况则覆盖原值
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    // linkedhashmap 的扩展
    afterNodeAccess(e);
    // 返回覆盖前的原值，结束 put 操作
    return oldValue;
}

// 新增元素的情况，modCount++，如果是覆盖原值，hashmap 认为不是结构上的改变
++modCount;
// 判断是否达到了扩容的阈值
if (++size > threshold)
    resize();
// linkedhashmap 的扩展
afterNodeInsertion(evict);
// 由于是添加元素，则原值为 null
return null;
复制代码

到此 put 操作就结束了，流程可以概括为：

数组为空则进行初始化操作（通过 resize 方法）
映射到的索引位置不存在元素，则直接在该位置添加键值
映射到的索引位置存在元素，则判断是否与当前键相等，如果是则覆盖原值
如果不相等，则判断哈希桶是否转成了红黑树，如果是则以红黑树节点的形式加入当前键值
如果没有转成红黑树，则以链表形式遍历，在链表尾部加入元素
加入元素之后，判断是否达到红黑树的转化阈值，如果是则进行树化
如果发现链表中已存在相等的键，则进行键值的覆盖
元素添加完毕之后，判断是否需要进行扩容

流程图如下（引用大神的流程图）：

元素 get

接下来看到 get() 方法，最终调用 getNode() 获取元素。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判断哈希桶数组是否为空
    // 如果数组不为空，则判断映射到的索引位置元素是否为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 桶中第一个元素为目标查找元素，则直接返回
            return first;
        // 遍历桶元素
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                // 以红黑树的形式遍历节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 以链表的形式遍历节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
复制代码

get() 方法相对没有那么复杂，步骤如下：