乐趣区

关于linux:HashMap源码实现分析

jiezi

HashMap 源码实现剖析

一、前言

HashMap 顾名思义，就是用 hash 表的原理实现的 Map 接口容器对象，那什么又是 hash 表呢。

咱们对数组都很相熟，数组是一个占用间断内存的数据结构，学过 C 的敌人对这一点影响必定更为粗浅。既然是一段间断的内存，数组的特点就不言而喻了，一旦你晓得要查第几个数据，工夫复杂度就是 O(1), 然而对于插入操作就很艰难；还有一种数据结构你也肯定很相熟，那就是链表，链表由一组指向（单向或者双向）的节点连贯的数据结构，它的特点是内存不间断，查找艰难，然而插入删除都很容易。

那有没有一种查找容易，插入删除查找都容易的数据结构呢，没错，它就是 hash 表。

本篇，咱们就来探讨：

  • HashMap 的数据结构实现形式
  • HashMap 是怎么做到为 get、put 操作提供稳固的工夫复杂度的
  • HashMap 什么时候从单节点转成链表又是什么时候从链表转成红黑树
  • HashMap 初始化时为什么要给自定义的初始容量。
  • HashMap 如何保障容量始终是 2 的幂
  • HashMap 为何要保障容量始终是 2 的幂
  • HashMap 的 hash 值如何计算
  • HashMap 为什么是线程不平安的

要理解 HashMap 最好的形式就是看源码，本篇内容基于 Jdk1.8HashMap 源码。

二、HashMap 的基本要素

磨刀不误砍柴功，想理解 HashMap 的原理，必然绕不过 HashMap 源码中的以下几个变量：

  • DEFAULT_INITIAL_CAPACITY：初始容量 1<<4 也就是 16
  • MAXIMUM_CAPACITY：最大容量 1<<30。
  • DEFAULT_LOAD_FACTOR：负载因子，默认是 0.75。什么意思呢，比如说你定义了一个初始容量为 16 的 HashMap，当你一直向外面增加元素后，最多到初始容量的 0.75，HashMap 就会触发扩容操作。
  • threshold：下一个触发扩容操作的阈值，threshold = CAPACITY * LOAD_FACTOR。
  • TREEIFY_THRESHOLD：链表转红黑树阈值，默认为 8，超过 8 就会执行链表转红黑树办法， 然而留神转红黑树办法中会判断以后 size 是否大于 64，只有大于 64 才转红黑树，否则执行 resize() 操作 。
  • UNTREEIFY_THRESHOLD：红黑树转链表阈值，默认为 6，顾名思义，红黑树节点小于 6 就会转成链表。
  • Node<K, V> implements Map.Entry<K, V> HashMap 存放数据的根本单位，外面存有 hash 值、key、value、next。
  • Node<K, V>[] table：寄存 Node 节点的数组，HashMap 最底层数组，数组元素能够为单节点 Node、多节点链表、多节点红黑树。

以上内容，有个印象就好，不用每个都记得。但这些概念对了解 HashMap 至关重要。

三、注释

3.1 HashMap 数据结构

HashMap 的数据结构很简略，它是一个 Node 类型的数组，每个元素能够为单节点、多节点链表、多节点红黑树。要害的问题是，这么简略的构造怎么实现的 put、get 都很快？什么时候从单节点转成链表又是什么时候从链表转成红黑树？

3.1.1 HashMap 如何实现 put、get 操作工夫复杂度为 O(1)~O(n)?

咱们晓得，查找一个数组的元素，当咱们不晓得 index 的时候，复杂度是很高的，然而当咱们晓得 index 的时候，这个复杂度就是 O(1) 级别的。HashMap 应用的就是这个原理。
对于 get 操作，首先依据 key 计算出 hash 值，而这个 hash 值执行操作 (n – 1) & hash 后就是它所在的 index，在最好的状况下，该 index 恰好只有一个节点且 hash 值和 key 的 hash 值雷同，那么工夫复杂度就是 O(1)，当该节点为链表或者红黑树时，工夫复杂度会回升，然而因为 HashMap 的优化（链表长度、红黑树长度绝对于 HashMap 容量不会过长，过长会触发 resize 操作），所以最坏的状况也就是 O(n), 可能还会小于这个值。

对于 put 操作，咱们晓得，数组插入元素的老本是昂扬的，HashMap 奇妙的应用链表和红黑树代替了数组插入元素须要挪动后续元素的耗费。这样在最好的状况下，插入一个元素，该 index 地位恰好没有元素的话，工夫复杂度就是 O(1), 当该地位有元素且为链表或者红黑树的状况下，工夫复杂度会回升，然而最坏的状况下也就是 O(n)。

3.1.2 HashMap 什么时候从单节点转成链表又是什么时候从链表转成红黑树？

单节点转链表很简略，当依据新退出的值计算出来的 index 处有元素时，若元素为单节点，则从节点转为链表。
链表转红黑树有两个条件：

  • 链表长度大于 TREEIFY_THRESHOLD，默认阈值是 8
  • HashMap 长度大于 64

当同时满足这两个条件，那么就会触发链表转红黑树的操作。

3.2 HashMap 初始化时为什么要给自定义的初始容量？

为啥前辈们都要求定义一个 HashMap 的时候肯定要应用构造函数 HashMap(int initialCapacity) 指定初始容量呢？

在阿里的《Java 开发手册》中是这样阐明的：

  1. 【举荐】汇合初始化时，指定汇合初始值大小。

阐明：HashMap 应用 HashMap(int initialCapacity) 初始化，

正例：initialCapacity = (须要存储的元素个数 / 负载因子) + 1。留神负载因子（即 loader

factor）默认为 0.75，如果临时无奈确定初始值大小，请设置为 16（即默认值）。

反例：HashMap 须要搁置 1024 个元素， 因为没有设置容量初始大小，随着元素一直减少，容

量 7 次被迫扩充，resize 须要重建 hash 表，重大影响性能。

这个问题在 HashMap 源码中是不言而喻的，每次 put 函数中都会查看以后 size 是否大于 threshold，如果大于就会进行扩容，新容量是原来容量的二倍。那么问题就来了，当你要存大量数据到 HashMap 中而又不指定初始容量的话，扩容会被一次接一次的触发，十分耗费性能。

而初始容量和负载因子给多少好呢，日常开发中如无必要不倡议动负载因子，而是依据要应用的 HashMap 大小确定初始容量，这也不是说为了防止扩容初始容量给的越大越好，越大申请的内存就越大，如果你没有这么多数据去存，又会造成 hash 值过于离散。

3.3 HashMap 如何保障容量始终是 2 的幂

HashMap 应用办法 tableSizeFor() 来保障无论你给值是什么，返回的肯定是 2 的幂：

  static final int tableSizeFor(int cap)
    {
        int n = cap - 1; // 作用：保障当 cap 为 2 的幂时，返回原值而不是二倍，如 8 返回 8 而不是 16
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

首先咱们来看操作：

           n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16

假如 n=01000000, n |= n >>> 1 后 n=01100000，n |= n >>> 2 后 n =01111000,n |= n >>> 4; 后 n =01111111, 咱们能够发现，上述 5 步操作能够将一个 32 位数第一位为 1 的前面所有位全变为 1。这样再执行 n + 1 操作后，该数就必为 2 的幂次方了。如 01111111+1 = 10000000。
那又为什么要保障肯定是 2 的幂次方呢？不是不行吗？

3.3.1 HashMap 为何要保障容量始终是 2 的幂

说到这个问题不得不说执行 put() 办法时，是如何依据 hash 值在 table 中定位。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
    {
        ......
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        ......

能够看到，它应用了一个 (n – 1) & hash 的操作，n 为以后 hashmap 的容量，而容量肯定为 2 的幂次方，n- 1 的二进制低位都为 1，举例：16=0000000000010000，15=0000000000001111，这样的解决益处在于，当执行 (n – 1) & hash 的操作时，元素的地位仅取决于低位而与高位无关（这种无关性随着 HashMap 容量的增大而减小），这个逻辑长处是，无论你的 hash 值有多大，我都锁定了你的取值范畴小于以后容量，这样做防止了 hash 值过于离散的状况，而当 HashMap 扩容时又能够同时增大 hash 值的取值范畴，毛病是减少了 hash 碰撞的可能性，为了解决这个问题 HashMap 批改了 hash 值的计算方法来减少低位的 hash 复杂度。

3.3.2 HashMap 计算 hash 值

不废话，间接上源码：

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

hash 办法用 key 的 hash 值异或上 key 的 hash 值的高 16 位，为什么要这样做呢？
首先，h>>>16 的值高 16 位都为 0，这样 h^(h>>>16) 时，高 16 位的值不会有任何变动，然而低 16 位的值混淆了 key 的高 16 位的值，从而减少了 hash 值的复杂度，进一步缩小了 hash 值一样的概率。

3.4 HashMap 为什么是线程不平安的

在 Jdk1.7 中，造成 HashMap 线程不平安的起因之一是 transfer 函数，该函数应用头查法在多线程的状况下很容易呈现闭环链表从而导致死循环，同时还有数据失落的问题，Jdk1.8 中没有 transfer 函数而是在 resize 函数中实现了 HashMap 扩容或者初始化操作，resize 采纳尾插法很好的解决了闭环链表的问题，然而仍旧防止不了数据笼罩的问题。
在 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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        ......

在执行完 if ((tab = table) == null || (n = tab.length) == 0) 判断且为 true 的状况下，会间接进行赋值，然而在多线程的环境下，当两个线程同时实现判断，线程 1 刚赋值完，线程 2 再进行赋值，就造成了数据笼罩的问题。
这只是最简略的景象，咱们要想线程平安，首先要有多线程平安的解决逻辑，很显著 HashMap 是没有这样的逻辑的，那么很多为单线程设计的逻辑就很大可能出问题，所以 HashMap 为什么是线程不平安的？它自身设计就不反对多线程下的操作，所以不该有此问。
如果想要线程平安的应用基于 hash 表的 map，能够应用 ConcurrentHashMap，该实现 get 操作是无锁的，put 操作也是分段锁，性能很好。
所以说术业有专攻，每个容器的实现都有它对应的优缺点。咱们须要学会的是剖析面对的每一种状况，正当的应用不同的容器去解决问题。

HashMap 根本的原理和对应实现就说到这里了，更深刻的话题如：红黑树插入节点、均衡红黑树、遍历红黑树，能够间接看红黑树对应的原理和实现。

须要源码正文的请戳这里源码解析

最初，最近很多小伙伴找我要 Linux 学习路线图 ，于是我依据本人的教训，利用业余时间熬夜肝了一个月，整顿了一份电子书。无论你是面试还是自我晋升，置信都会对你有帮忙！

收费送给大家，只求大家金指给我点个赞！

电子书 | Linux 开发学习路线图

也心愿有小伙伴能退出我，把这份电子书做得更完满！

有播种？心愿老铁们来个三连击，给更多的人看到这篇文章

举荐浏览：

  • 干货 | 程序员进阶架构师必备资源免费送
  • 神器 | 反对搜寻的资源网站
退出移动版