转载

【源码笔记】HASHMAP源码解读（1）

HashMap 是我们平时工作中经常会用到的一个类，网上也有很多关于此类源码的文章，想要吃透一个源码，理解其中的含义并不容易，本文主要是对 HashMap 中的方法进行一个源码解读，从我们最常用的方法入手，由浅入深逐步窥探到整个核心。

HashMap 介绍

在看源码之前首先要介绍一下 HashMap，HashMap 是一个用于存放键值对的数据结构，在 jdk1.8 时候，它的底层实现的数据结构是数组 + 链表 + 红黑树，当链表长度大于 8 时，链表会转换成红黑树。转换成红黑树的原因是当链表比较长的时候，搜索链表的时间复杂度是 O(n)，而红黑树的时间复杂度为O(log n)，至于为什么是长度为8的时候才进行转换，这是在理想情况下，哈希值随机分布，而根据泊松分布，桶的长度超过 8 的概率非常小，所以选取 8 当作默认值，而当桶内长度低于6时会转成链表，不选 7 是因为防止链表红黑树频繁转换。

HashMap 的 put 方法

当调用 HashMap 中的 put 方法时，需要传入两个参数，key 和 value

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

它会计算出 key 的 hash 值并且调用 putVal 这个方法并传一些默认值进去，hash 这个方法非常简单，就是调用 key 的 hashcode 方法然后进行扰动函数，所谓扰动函数就是防止你写的 hashcode 方法过于简单帮你进一步处理这个 hash 值。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
复制代码

putVal 方法里面一共有五个参数，其中前三个比较好理解。

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

第四个参数是一个布尔类型的参数，当它为 true 时就会判断当前 key 是否存在与数组中，如果存在则不进行覆盖，反之，但如果没有值还是会赋值进去的，调用 put 方法默认传 false。

if (!onlyIfAbsent || oldValue == null)
        e.value = value;
复制代码

第五个参数会被传入到一个 afterNodeInsertion 方法当中，这个方法在 HashMap 中是一个无用的方法，它主要是提供给 LinkedHashMap 这么回调函数用于特殊处理。

// Callbacks to allow LinkedHashMap post-actions
    void afterNodeInsertion(boolean evict) { }
复制代码

回到 putVal 方法当中，首先最外层有三个判断，第一个 if 适用于判断当前 HashMap 是否进行初始化了，如果没有那么调用 resize 方法进行初始化。第二个 if 用于判断通过 hash 取模得到的下标在当前数组中是否有值，如果没有则直接赋值。当前第二条判断没有通过则表明发生哈希冲突了，此时需要进一步处理。

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 {
            ... // A1
        }
        ... // A2
    }
复制代码

可以看到这里也进行了三个判断，第一个 if 语句是用于判断当前 key 和数组下标中对应的链表头节点是否是同一个 key ，如果是则把 e 赋值为头节点。第二个 if 语句用于判断当前节点是否是红黑树节点，是的话将会遍历红黑树来寻找 key 所对应的元素并返回，如果没找到则直接创建一个 TreeNode 并插入到红黑树当中并返回 null。如果前两个都不满足那么遍历链表找出 key 所对应的 Node 节点，和红黑树同理如果没有找到则会直接插入到链表尾部并把 e 赋值为 null，当 e 不为 null 时，也就意味着在 key 以及存在，所以就会将 value 值直接赋值给 e 的 value 属性当中。同时返回旧值。afterNodeAccess 方法和前面的 afterNodeInsertion 方法一样用于给 LinkedHashMap 回调。

// A1代码
    HashMap.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 HashMap.TreeNode)
        e = ((HashMap.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;
    }
复制代码

最后则是修改状态，将长度进行 +1 同时判断是否超出阔值，如果超出则调用 resize 方法进行扩容，然后返回 null。

// A2 代码
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
复制代码

总结

HashMap其中的方法有太多太多，这次只是大概的介绍了一下 put 方法，但还有好多方法只是大致讲了下功能，像 resize、putTreeVal 等方法，源码还没有细看，但这不妨碍我们对 put 方法有个大致的了解，下周我会继续解读这两种方法，并逐步摸头其中的原理，谢谢观看。

原文 https://juejin.im/post/5e1066f9e51d45411d0c2964

正文到此结束

所属分类： Java 编程技术

本文标签： 总结源码时间 final equals 代码 HashMap 数据参数 id map value IO key Action https 遍历文章 node App http tab CEO
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

【源码笔记】HASHMAP源码解读（1）

HashMap 介绍

HashMap 的 put 方法

总结

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流