视频合集

    HashMap的实现原理，源码深度剖析！

    • 课程笔记
    • 问答交流

    一线资深java工程师招聘需求里明确了需要精通集合容器，尤其是今天我谈到的HashMap以及后续我要讲到的ConcurrentHashMap。

    HashMap在Java集合的重要性不亚于Volatile在并发编程的重要性(可见性与有序性)，所以需要重点来掌握。

    为了助大家掌握好HashMap，这节课我会重点讲解以下10点：

    1.HashMap的数据结构

    2.HashMap核心成员

    3.HashMapd的Node数组

    4.HashMap的数据存储

    5.HashMap的哈希函数

    6.哈希冲突：链式哈希表

    7.HashMap的get方法：哈希函数

    8.HashMap的put方法

    9.为什么槽位数必须使用2^n？

    10.HashMap必考点总结

    HashMap的数据结构

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

    HashMap的实现原理，源码深度剖析！-mikechen

    这里需要搞明白两个问题：

    • 数据底层具体存储的是什么？
    • 这样的存储方式有什么优点呢？

    1.核心成员

    1. 默认初始容量(数组默认大小):16，2的整数次方
    2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    3.  
    4.  最大容量
    5. static final int MAXIMUM_CAPACITY = 1 << 30;
    6.  
    7. 默认负载因子
    8. static final float DEFAULT_LOAD_FACTOR = 0.75f;
    9. 装载因子用来衡量HashMap满的程度，表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容
    10.  
    11. 链表转红黑树边界
    12. static final int TREEIFY_THRESHOLD = 8;
    13.  
    14. 红黑树转离链表边界
    15. static final int UNTREEIFY_THRESHOLD = 6;
    16.  
    17. 哈希桶数组
    18. transient Node<K,V>[] table;
    19.  
    20. 实际存储的元素个数
    21. transient int size;
    22.  
    23. 当map里面的数据大于这个threshold就会进行扩容
    24. int threshold   阈值 = table.length * loadFactor

     

    2.Node数组

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

    1. static class Node<K,V> implements Map.Entry<K,V> {
    2.     final int hash;//用来定位数组索引位置
    3.     final K key;
    4.     V value;
    5.     Node<K,V> next;//链表的下一个Node节点
    6.  
    7.     Node(int hash, K key, V value, Node<K,V> next) {
    8.         this.hash = hash;
    9.         this.key = key;
    10.         this.value = value;
    11.         this.next = next;
    12.     }
    13.  
    14.  
    15.     public final K getKey()        { return key; }
    16.     public final V getValue()      { return value; }
    17.     public final String toString() { return key + "=" + value; }
    18.  
    19.  
    20.     public final int hashCode() {
    21.         return Objects.hashCode(key) ^ Objects.hashCode(value);
    22.     }
    23.  
    24.  
    25.     public final V setValue(V newValue) {
    26.         V oldValue = value;
    27.         value = newValue;
    28.         return oldValue;
    29.     }
    30.  
    31.  
    32.     public final boolean equals(Object o) {
    33.         if (o == this)
    34.             return true;
    35.         if (o instanceof Map.Entry) {
    36.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    37.             if (Objects.equals(key, e.getKey()) &&
    38.                 Objects.equals(value, e.getValue()))
    39.                 return true;
    40.         }
    41.         return false;
    42.     }
    43. }

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

    HashMap的数据存储

    1.哈希表来存储

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

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

    哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

    2.哈希函数

    哈希表中元素是由哈希函数确定的,将数据元素的关键字Key作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。
    表示为：Addr = H（key）,如下图所示：
    HashMap的实现原理，源码深度剖析！-mikechen

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

    3.核心问题

    建立一个哈希表之前需要解决两个主要问题：

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

    2)冲突的处理

    冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。

    4.哈希冲突：链式哈希表

    哈希表为解决冲突，可以采用地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。

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

    HashMap的实现原理，源码深度剖析！-mikechen
    HashMap的实现原理，源码深度剖析！-mikechen

    HashMap的哈希函数

    1. /**
    2. * 重新计算哈希值
    3. */
    4. static final int hash(Object key) {
    5.     
    6.     int h;
    7.  
    8.      // h = key.hashCode() 为第一步 取hashCode值
    9.      // h ^ (h >>> 16) 为第二步 高位参与运算
    10.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    11. }

     

    //计算数组槽位

    1. (n - 1) & hash

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

    HashMap的实现原理，源码深度剖析！-mikechen

    这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。

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

    备注：

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

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

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

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

    HashMap的实现原理，源码深度剖析！-mikechen

    假如槽位数不是16，而是17，则槽位计算公式变成：(17 – 1) & hash
    HashMap的实现原理，源码深度剖析！-mikechen
    从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难。2.等价于length取模

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

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

    最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率。

    https://www.javacodegeeks.com/2015/09/an-introduction-to-optimising-a-hashing-strategy.html

    分析HashMap的put方法：

    1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    2.                boolean evict) {
    3.     Node<K,V>[] tab; Node<K,V> p; int n, i;
    4.     
    5.     // 当前对象的数组是null 或者数组长度时0时，则需要初始化数组
    6.     if ((tab = table) == null || (n = tab.length) == 0) {
    7.         n = (tab = resize()).length;
    8.     }
    9.     
    10.     // 使用hash与数组长度减一的值进行异或得到分散的数组下标，预示着按照计算现在的
    11.     // key会存放到这个位置上，如果这个位置上没有值，那么直接新建k-v节点存放
    12.     // 其中长度n是一个2的幂次数
    13.     if ((p = tab[i = (n - 1) & hash]) == null) {
    14.         tab[i] = newNode(hash, key, value, null);
    15.     }
    16.     
    17.     // 如果走到else这一步，说明key索引到的数组位置上已经存在内容，即出现了碰撞
    18.     // 这个时候需要更为复杂处理碰撞的方式来处理，如链表和树
    19.     else {
    20.         Node<K,V> e; K k;
    21.        
    22.         //节点key存在，直接覆盖value
    23.         if (p.hash == hash &&
    24.             ((k = p.key) == key || (key != null && key.equals(k)))) {
    25.             e = p;
    26.         }
    27.         // 判断该链为红黑树
    28.         else if (p instanceof TreeNode) {
    29.             // 其中this表示当前HashMap, tab为map中的数组
    30.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    31.         }
    32.         else {  // 判断该链为链表
    33.             for (int binCount = 0; ; ++binCount) {
    34.                 // 如果当前碰撞到的节点没有后续节点，则直接新建节点并追加
    35.                 if ((e = p.next) == null) {
    36.                     p.next = newNode(hash, key, value, null);
    37.                     // TREEIFY_THRESHOLD = 8
    38.                     // 从0开始的，如果到了7则说明满8了，这个时候就需要转
    39.                     // 重新确定是否是扩容还是转用红黑树了
    40.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    41.                         treeifyBin(tab, hash);
    42.                     break;
    43.                 }
    44.                 // 找到了碰撞节点中，key完全相等的节点，则用新节点替换老节点
    45.                 if (e.hash == hash &&
    46.                     ((k = e.key) == key || (key != null && key.equals(k))))
    47.                     break;
    48.                 p = e;
    49.             }
    50.         }
    51.         // 此时的e是保存的被碰撞的那个节点，即老节点
    52.         if (e != null) { // existing mapping for key
    53.             V oldValue = e.value;
    54.             // onlyIfAbsent是方法的调用参数，表示是否替换已存在的值，
    55.             // 在默认的put方法中这个值是false，所以这里会用新值替换旧值
    56.             if (!onlyIfAbsent || oldValue == null)
    57.                 e.value = value;
    58.             // Callbacks to allow LinkedHashMap post-actions
    59.             afterNodeAccess(e);
    60.             return oldValue;
    61.         }
    62.     }
    63.     // map变更性操作计数器
    64.     // 比如map结构化的变更像内容增减或者rehash，这将直接导致外部map的并发
    65.     // 迭代引起fail-fast问题，该值就是比较的基础
    66.     ++modCount;
    67.    
    68.      // size即map中包括k-v数量的多少
    69.    // 超过最大容量 就扩容
    70.     if (++size > threshold)
    71.         resize();
    72.     // Callbacks to allow LinkedHashMap post-actions
    73.     afterNodeInsertion(evict);
    74.     return null;
    75. }

    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必考点总结

     

    评论交流
    1. 路正银

      1、HashMap是用数据+链表+红黑树（JDK1.8版本之后增加）的数据结构来实现的，
      通过哈希函数确定在桶（数组）中的位置，当发生哈希冲突的时候，往后挂链表（JDK1.8版本会有链表转红黑树的逻辑）
      2、（1）底层数据结构不一样，1.7是数组+链表，1.8是数组+链表+红黑树
      （2）计算哈希值时，jdk1.8版本相比jdk1.7版本多了对hasCode做无符号右移16位,与原hasCode做异或的操作
      （3）扩容策略不一样
      3、哈希函数的目的是尽量让计算出的哈希值分布均匀，减少哈希碰撞
      JDK1.8版本的优化是，将hascode的高16位做移位操作，可以让hascode高位的值也参与运算，掺杂的元素多了，生成的hash的值的随机性会增大，减少了hash碰撞

      • mikechen

        核心点都谈到了 ，基本都掌握了，再补充一个点：就是HashMap 1.7版本在多线程的情况下会出现死循环，形成一个链表的死循环这个点，还可以线下有时间再做了解和补充，基本就没问题了。

        基本学习快一个月了，依然还在坚持输出作业，这个必须给赞 ，线下就坚持锻炼(keep见)+坚持作业输出，我就搬个小板凳在旁边给你呐喊加油了 ，继续加油 ✗咧嘴笑✗ ✗拳头✗

    欢迎您，新朋友，感谢参与互动！
    确定

    请输入验证码

    请输入图片中的验证码
    点击发送按钮获取验证码

    取消
    ×

    公告

    前往查看详情
    ×
    ×
    ￥undefined
    请打开手机使用微信扫码支付
    「」
    ×

    ....支付确认中....

    「」
    ×
    支付金额

    ￥

    undefined
    ×
    积分支付
    您当前的积分为0

    检测到您未绑定微信账户，请先绑定微信

    立刻绑定

    打开微信扫一扫

    微信长按二维码

    关注「mikechen公众号」安全快捷登录

    ×

    下载海报：

    点击下载
    返回顶部