关于java:HashMap的实现原理看这篇就够了

HashMap 是一线资深 java工程师必须要精通的汇合容器，它的重要性简直等同于Volatile在并发编程的重要性（可见性与有序性）。

本篇通过图文源码详解，深度分析 HashMap 的重要内核常识，易看易学易懂。倡议珍藏，多学一点总是好的，万一面试被问到了呢。

我是Mike，10余年BAT一线大厂架构技术倾囊相授。本篇重点：

HashMap的数据结构
HashMap核心成员
HashMapd的Node数组
HashMap的数据存储
HashMap的哈希函数
哈希抵触：链式哈希表
HashMap的get办法：哈希函数
HashMap的put办法
为什么槽位数必须应用2^n？

HashMap的数据结构

首先，咱们从数据结构的角度来看：HashMap是:数组+链表+红黑树（JDK1.8减少了红黑树局部）的数据结构，如下所示:

这里须要搞明确两个问题：

*数据底层具体存储的是什么？
这样的存储形式有什么长处呢？*

默认初始容量(数组默认大小):16，2的整数次方

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

 

 最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

 

默认负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

装载因子用来掂量HashMap满的水平，示意当map汇合中存储的数据达到以后数组大小的75%则须要进行扩容

 

链表转红黑树边界

static final int TREEIFY_THRESHOLD = 8;

 

红黑树转离链表边界

static final int UNTREEIFY_THRESHOLD = 6;

 

哈希桶数组

transient Node<K,V>[] table;

 

理论存储的元素个数

transient int size;

 

当map外面的数据大于这个threshold就会进行扩容

int threshold   阈值 = table.length * loadFactor

2.Node数组

从源码可知，HashMap类中有一个十分重要的字段，就是 Node[] table，即哈希桶数组，显著它是一个Node的数组。

static class Node<K,V> implements Map.Entry<K,V> {

    final int hash;//用来定位数组索引地位

    final K key;

    V value;

    Node<K,V> next;//链表的下一个Node节点

 

    Node(int hash, K key, V value, Node<K,V> next) {

        this.hash = hash;

        this.key = key;

        this.value = value;

        this.next = next;

    }

 

    public final K getKey()        { return key; }

    public final V getValue()      { return value; }

    public final String toString() { return key + "=" + value; }

 

    public final int hashCode() {

        return Objects.hashCode(key) ^ Objects.hashCode(value);

    }



    public final V setValue(V newValue) {

        V oldValue = value;

        value = newValue;

        return oldValue;

    }



    public final boolean equals(Object o) {

        if (o == this)

            return true;

        if (o instanceof Map.Entry) {

            Map.Entry<?,?> e = (Map.Entry<?,?>)o;

            if (Objects.equals(key, e.getKey()) &&

                Objects.equals(value, e.getValue()))

                return true;

        }

        return false;

    }

}

Node是HashMap的一个外部类，实现了Map.Entry接口，实质是就是一个映射(键值对)。

HashMap的数据存储

1.哈希表来存储

HashMap采纳哈希表来存储数据。

哈希表（Hash table，也叫散列表），是依据关键码值(Key value)而间接进行拜访的数据结构，只有输出待查找的值即key，即可查找到其对应的值。

哈希表其实就是数组的一种扩大，由数组演变而来。能够说，如果没有数组，就没有散列表。

2.哈希函数

哈希表中元素是由哈希函数确定的,将数据元素的关键字Key作为自变量，通过肯定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。

示意为：Addr = H（key）,如下图所示：

哈希表中哈希函数的设计是相当重要的，这也是建哈希表过程中的关键问题之一。

3.外围问题

建设一个哈希表之前，须要解决两个次要问题：

1) 结构一个适合的哈希函数,平均性 H（key）的值均匀分布在哈希表中

2) 抵触的解决

抵触：在哈希表中，不同的关键字值对应到同一个存储地位的景象。

4.哈希抵触：链式哈希表

哈希表为解决抵触，能够采纳地址法和链地址法等来解决问题，Java中HashMap采纳了链地址法。

链地址法，简略来说，就是数组加链表的联合,如下图所示：

HashMap的哈希函数

/**

* 从新计算哈希值

*/

static final int hash(Object key) {

    

    int h;

 

     // h = key.hashCode() 为第一步 取hashCode值

     // h ^ (h >>> 16) 为第二步 高位参加运算

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

//计算数组槽位

(n - 1) & hash

对key进行了 hashCode 运算，失去一个32位的 int 值 h, 而后用 h 异或 h>>>16位。在 JDK1.8 的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：
(h = k.hashCode()) ^ (h >>> 16)。

这样做的益处是：

能够将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中退出了高位的信息，这样高位的信息被变相的保留了下来。

等于说计算下标时把hash的高16位也参加进来了，掺杂的元素多了，那么生成的hash值的随机性会增大，缩小了hash碰撞。

备注：

 - ^异或：不同为1，雷同为0
 -  >>> ：无符号右移：左边补0
 - &运算：两位同时为“1”，后果才为“1，否则为0

h & (table.length -1)来失去该对象的保留位，而HashMap底层数组的长度总是2的n次方。

为什么槽位数必须应用2^n

1. 为了让哈希后的后果更加平均

如果槽位数不是16，而是17，则槽位计算公式变成：(17 – 1) & hash

从上文能够看出，计算结果将会大大趋同，hashcode加入&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种劫难。2.等价于length取模

当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，然而&比%具备更高的效率。

位运算的运算效率高于算术运算，起因是算术运算还是会被转化为位运算。

最终目标，还是为了让哈希后的后果更平均的分部，缩小哈希碰撞，晋升hashmap的运行效率。

剖析HashMap的put办法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

               boolean evict) {

    Node<K,V>[] tab; Node<K,V> p; int n, i;

    

    // 以后对象的数组是null 或者数组长度时0时，则须要初始化数组

    if ((tab = table) == null || (n = tab.length) == 0) {

        n = (tab = resize()).length;

    }

    

    // 应用hash与数组长度减一的值进行异或失去扩散的数组下标，预示着依照计算当初的

    // key会寄存到这个地位上，如果这个地位上没有值，那么间接新建k-v节点寄存

    // 其中长度n是一个2的幂次数

    if ((p = tab[i = (n - 1) & hash]) == null) {

        tab[i] = newNode(hash, key, value, null);

    }

    

    // 如果走到else这一步，阐明key索引到的数组地位上曾经存在内容，即呈现了碰撞

    // 这个时候须要更为简单解决碰撞的形式来解决，如链表和树

    else {

        Node<K,V> e; K k;

       

        //节点key存在，间接笼罩value

        if (p.hash == hash &&

            ((k = p.key) == key || (key != null && key.equals(k)))) {

            e = p;

        }

        // 判断该链为红黑树

        else if (p instanceof TreeNode) {

            // 其中this示意以后HashMap, tab为map中的数组

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

                    // TREEIFY_THRESHOLD = 8

                    // 从0开始的，如果到了7则阐明满8了，这个时候就须要转

                    // 从新确定是否是扩容还是转用红黑树了

                    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;

            }

        }

        // 此时的e是保留的被碰撞的那个节点，即老节点

        if (e != null) { // existing mapping for key

            V oldValue = e.value;

            // onlyIfAbsent是办法的调用参数，示意是否替换已存在的值，

            // 在默认的put办法中这个值是false，所以这里会用新值替换旧值

            if (!onlyIfAbsent || oldValue == null)

                e.value = value;

            // Callbacks to allow LinkedHashMap post-actions

            afterNodeAccess(e);

            return oldValue;

        }

    }

    // map变更性操作计数器

    // 比方map结构化的变更像内容增减或者rehash，这将间接导致内部map的并发

    // 迭代引起fail-fast问题，该值就是比拟的根底

    ++modCount;

   

     // size即map中包含k-v数量的多少

   // 超过最大容量 就扩容

    if (++size > threshold)

        resize();

    // Callbacks to allow LinkedHashMap post-actions

    afterNodeInsertion(evict);

    return null;

}

HashMap的put办法执行过程整体如下：

① 判断键值对数组 table[i] 是否为空或为null，否则执行 resize() 进行扩容；

② 依据键值 key计算hash值得到插入的数组索引i，如果table[i]==null，间接新建节点增加；

③ 判断table[i]的首个元素是否和key一样，如果雷同间接笼罩value；

④ 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则间接在树中插入键值对；

⑤ 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key曾经存在间接笼罩value即可；

⑥ 插入胜利后，判断理论存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

HashMap总结

HashMap底层构造？基于Map接口的实现，数组+链表的构造，JDK 1.8后退出了红黑树，链表长度>8变红黑树,<6变链表

两个对象的hashcode雷同会产生什么? Hash抵触，HashMap通过链表来解决hash抵触

HashMap 中 equals() 和 hashCode() 有什么作用？HashMap 的增加、获取时须要通过 key 的 hashCode() 进行 hash()，而后计算下标 ( n-1 & hash)，从而取得要找的同的地位。当发生冲突（碰撞）时，利用 key.equals() 办法去链表或树中去查找对应的节点

HashMap 何时扩容？put的元素达到容量乘负载因子的时候，默认16*0.75

hash 的实现吗？h = key.hashCode()) ^ (h >>> 16)， hashCode 进行无符号右移 16 位，而后进行按位异或，失去这个键的哈希值，因为哈希表的容量都是 2 的 N 次方，在以后，元素的 hashCode() 在很多时候下低位是雷同的，这将导致抵触（碰撞），因而 1.8 当前做了个移位操作：将元素的 hashCode() 和本人右移 16 位后的后果求异或

HashMap线程平安吗？HashMap读写效率较高，然而因为其是非同步的，即读写等操作都是没有锁爱护的，所以在多线程场景下是不平安的，容易呈现数据不统一的问题，在单线程场景下十分举荐应用。

以上就是HashMap的介绍，本篇的视频版详解，留言可获取。

—END–

对于作者：mikechen，十余年BAT架构教训，资深技术专家，曾任职阿里、淘宝、百度。

欢送关注集体公众号：mikechen的互联网架构，十余年BAT架构教训倾囊相授！

在公众号菜单栏对话框回复【架构】关键词，即可查看我原创的300期+BAT架构技术系列文章与1000+大厂面试题答案合集。

关于java:HashMap的实现原理看这篇就够了

HashMap的数据结构

HashMap的数据存储

HashMap的哈希函数

为什么槽位数必须应用2^n

剖析HashMap的put办法：

HashMap总结

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于java:HashMap的实现原理看这篇就够了

HashMap的数据结构

HashMap的数据存储

HashMap的哈希函数

为什么槽位数必须应用2^n

剖析HashMap的put办法：

HashMap总结

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复