转载

Java Collections Framework 源码分析(6.1 - HashMap 的哈希算法)

这应该是 Java Collections Framework 源码分析的最后一部分了，而分析对象也是目前为止最为复杂的数据结构：HashMap。在日常开发中 HashMap 的使用率非常高，应该和 ArrayList 不分上下，而且 HashMap 的相关问题是 Java 面试中必然出现的，因此能够从源码层面理解 HashMap 的相关知识点就变得尤为重要。希望接下来的几篇文章能够帮助你从数个核心知识点上真正掌握 HashMap 这个数据结构。

基础结构

大家可能已经知道 Java8 之后，HashMap 内部存放元素的数据结构发生了一些变化，不再单纯是以前数组+链表的方式，而是在满足某些条件后会变为红黑树的形式。所以让我们先从基础结构开始分析。

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

可以看到 HashMap 内部使用一个数组来存放数据元素，而数组元素的类型是 Node。需要留意一下的是注释中提到数组的长度一定是 2 的幂。接着看一下 Node 的定义：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    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;
    }
....

很简单的数据包装对象，封装了 key 与 value 和相应的 hash 值，并且有指向下一个节点，类似单链表的结构。

put 操作

我们可以从 HashMap 最常用的 put 函数入手，先大致看一下 HashMap 是如何新增元素的。

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) {
    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 {
        ....
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

第一个 if 用来检查 table 是否被初始化，如果没有的话会调用 resize() 函数得到一个新的数组， resize() 函数我们稍后分析，先往下走。

第二个 if 的作用也很明显，通过 hash 值在数组中寻找是否有对应的 Node 对象，如果没有则创建一个新的 Node 。 newNode() 函数很简单，只是调用 Node 的构造函数，值得看一下的是 i 的计算逻辑。在理解 i 的计算逻辑就要先看一下 hash 的算法。

Hash 算法

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

可以看到 HashMap 中用到的哈希算法非常简单，调用 key 对象的 hashCode 函数，然后与自身逻辑位移(高位补 0) 16 位之后的值进行 XOR(异或)操作。之后还会有地方会谈及这个哈希算法，现在先回到之前 i 计算的那部分。

确定 table 中的位置

tab[i = (n - 1) & hash])

n 是 table 数组的长度，还记得之前提到过 table 数组长度是 2 的幂吗？因此 n 的二进制形式就是 1 开头，后面都是 0 (2 -> 10, 4 -> 100, 8 -> 1000)，而 n - 1 之后的二进制形式就都是 1 (3 -> 11, 7 -> 111)。了解了 n - 1 的数字特征后， n - 1 与 hash 进行 & (AND 操作) 的结果就容易了：如果 hash 大于 n - 1 ，那么会对 hash 截取超过 n -1 的部分，仅保留低位，反之直接返回 hash 值。

哈希冲突

现在可以继续分析 putVal 源码中的 else 部分：

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;
    }
}

回忆一下进入 else 分支的条件，即 tab 数组对应 i 的 Node 已经存在。此时我们称之为发生了「哈希冲突」，即不同的 key 产生了相同的哈希值。

第一个 if 分支的逻辑很容易理解，如果数组对应位置上 Node 对象的 hash 值与 key 值都与传入参数一致，那么就是个简单的覆盖。

接下来的 else...if 分支则是判断当前 Node 是否为 TreeNode 的示例，在这个分支中执行的是红黑树的插入操作，这部分的分析会放在后面。

最后的 else 分支中会使用 for 与 Node 上的 next 引用循环链表，便利相同 hash 值的 Node 。其中值得注意的是：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);

当计数超过 TREEIFY_THRESHOLD - 1 时会调用 treeifyBin 函数，将原来数组 + 单链表的数据结构转化为红黑树，这个阈值的初始为 8。即当由冲突引起的单链表长度超过 8 之后会执行红黑树的转化。

小结

本篇为大家分析了 HashMap 内部的数据结构，以及 put（） 函数的答题流程，包括哈希算法，冲突的解决等。不难发现位操作往往是一些底层算法的基石，因此希望大家在平时还是花些时间掌握位操作的相关知识，最好能够活学活用。之后的文章会为大家分析数组扩容，以及红黑树的部分，希望你不要错过。

原文 https://segmentfault.com/a/1190000022495225

正文到此结束

所属分类： Java 编程技术

本文标签： map key IO cat Collections 文章哈希算法 App http https CEO final equals node 注释开发 ArrayList tab 时间参数 HashMap 源码 Bootstrap list 希望 java 数据 value Collection
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

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

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

问题交流

Java Collections Framework 源码分析(6.1 - HashMap 的哈希算法)

基础结构

put 操作

Hash 算法

确定 table 中的位置

哈希冲突

小结

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流