耗时3天写完的HashMap万字解析,争取一篇文章讲透它,面试官看了都直点头!

简介: 耗时3天写完的HashMap万字解析,争取一篇文章讲透它,面试官看了都直点头!

写在开头

在过去的几篇博客中,我们已经将Collection下的三大接口(List,Set,Queue)学了一遍,那么今天我们即将开启Java中另一大集合类型-Map

所谓的Map:指的是使用键值对(key-value)存储,类似于数学上的函数 y=f(x),"x" 代表 key,"y" 代表 value,key 是无序的、不可重复的,value 是无序的、可重复的,每个键最多映射到一个值上的一种数据存储结构。

那么在Map的世界里,大概是这样的一个父子继承图谱(不完全),而在日常的开发过程中,使用最多且面试时被问到的频率最高的集合类型要数HashMap,那么好,接下来我们就一起以HashMap来作为开篇,来一起学习一下Map!

image.png

HashMap

HashMap是典型的Map类型集合,包含了太多面试考点,我们尽量在这一篇文章中给讲完、讲透,所以文章会有点长,希望小伙伴们能够保持耐心阅读完,有存在问题的地方,可以提出来,咱们一起讨论,有写错的地方也请指出来,build哥有错就改!
首先,我们先来通过一个小示例,看一下HashMap的增删改查如何使用哈

【代码示例1】

public class Test {
   
   
    public static void main(String[] args) {
   
   
        HashMap<String, Integer> map = new HashMap<>();
        //增
        map.put("xiaoming", 18);
        map.put("xiaohua", 19);
        //删
        map.remove("xiaohua");
        //改
        map.put("xiaoming", 20);
        //查
        Integer xiaoming = map.get("xiaoming");
        System.out.println("xiaoming的年龄:"+xiaoming);
        //遍历Map
        for (String s : map.keySet()) {
   
   
            System.out.println(s);
            System.out.println(map.get(s));
        }
    }
}

输出:

xiaoming的年龄:20
xiaoming
20

总体来说,HashMap的存储原理就是基于哈希表的数组,只不过这个数组的每个元素中存储的可能是键值对,可能是链表,可能是红黑树,我们在存储键值对的时候(put方法),通过计算键(key)的哈希值找到对应的数组下标,然后将对应的值(value)存入。

这里提到的哈希值可不是简单的重写hashcode()所算出的结果,而是经过扰动之后的结果,通过研究HashMap的底层我们可以获得答案!

HashMap的哈希值实现原理?

穿透到HashMap的底层后,我们第一个要寻到答案的就是:哈希值的计算原理
第一步:在存储键值对时,我们跟进put()方法的源码中去一探究竟。

【源码解析1】

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

从put方法的底层中我们可以看到hash()方法的身影,JDK1.8中的hash方法源码如下:

【源码解析2】

    static final int hash(Object key) {
   
   
      int h;
      // key.hashCode():返回散列值也就是hashcode
      // ^:按位异或
      // >>>:无符号右移,忽略符号位,空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

在hash()方法通过一个三目运算符也进行返回值的处理,当key为null时,直接返回一个0值,否则则对key进行hashCode()散列码的计算,并将其与无符号右移16位之后的散列码异或运算。

  • ^ 运算符: 异或运算符是Java中的一种位运算符,它用于将两个数的二进制位进行比较,如果相同则为0,不同则为1。
  • h >>> 16: 将散列码向右移动16位,int类型的h为32位,为2的32次方,而无符号右移,相当于除以2的16次方,因此是将原来的h值分成了两个16位的部分。

经过这一道算法加工,大大的提高了hash值的扰动,使得key能够尽可能分散的存储,有效的减少了哈希碰撞

如何计算找到key在数组中的位置?

虽然在上面我们已经知道了key的哈希值计算原理,但我们仍然没有看到如何将key存入HashMap底层的数组(初始容量为16的数组)中的,我们进入到源码解析1中的putVal()中一看便知!

【源码解析3】

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
   
   
    // 数组
    HashMap.Node<K,V>[] tab; 
    // 元素
    HashMap.Node<K,V> p; 

    // n 为数组的长度 i 为下标
    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);
}

源码中通过(n - 1) & hash 获取key最终在HashMap中的存储的数组下标位置,也就是数组长度减一和hash值进行与运算。
这里其实有一个很细小的知识点,在很多Java面试时被提及,就是

为什么采用位运算而不是直接进行取余操作(符号:%)。

首先,我们先来解释一下为什么需要进行这一步的操作,在上面我们提到哈希值其实是一个int类型,4字节,范围从-2147483648 到 2147483648,这里足足有40亿个映射空间,经过右移和异或操作后,理论上的哈希碰撞(哈希碰撞)概率很小,但40亿长度的数组,得多大的内存来存储?这显然是不现实的,而又因为HashMap的初始数组长度位16,所以要进行一定的操作,让最终的结果值在0~15之间。

那么好!现在又有个问题:为什么要用与运算,而不是%呢?
理由很简单:由于位运算直接对内存数据进行操作,不需要转成十进制,处理速度非常快。
什么!你不信?OK!咱们写一个测试类验证一下!

【代码示例2】

public class Test {
   
   
    public static void main(String[] args) {
   
   
        test1();
        test2();
    }
    public static void test1() {
   
   
        int number = Integer.MAX_VALUE;
        int a = 1;
        long start = System.currentTimeMillis();

        for (int i = 1; i < number; i++) {
   
   
            a %= i;
        }
        long end = System.currentTimeMillis();
        System.out.println("第1种" +(end - start) + "毫秒");
    }

    public static void test2() {
   
   
        int number = Integer.MAX_VALUE;
        int a = 1;
        long start2 = System.currentTimeMillis();
        for (int i = 1; i < number; i++) {
   
   
            a &= i;
        }
        long end2 = System.currentTimeMillis();
        System.out.println("第2种" + (end2 - start2) + "毫秒");
    }
}

输出:

19290毫秒
第2565毫秒

结果很明显,&预算的耗时要远远小于取余%!
现在我们解释了选取&的原因,那怎么样采用实现取余数的操作呢?当b为2的幂次方时,伟大的前人们发现了这个公式:a%b = a&(b-1)
验证计算:

image.png

到这里,key的值在HashMap中的位置存储就讲完啦。

JDK1.8中为什么由数组+链表改为数组+链表+红黑树?

我们在上面所看到的源码其实都是JDK1.8的,在此之前的HashMap底层采用的是数组+链表形式,我们以JDK1.7为例,当存入一个键值对,会通过扰动函数(hash())尽可能减少碰撞,找到数组对应位置后,若无元素,则直接存入键值对,若有元素,则判断和存入的key值是否相同(重写equals()方法),若相同,则进行值覆盖,若不相同,则通过 拉链法 解决冲突。

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。
image.png

相较于JDK1.7而言,1.8的升级除了优化了hash()方法外,最主要的是在解决哈希冲突的方式上进行了大改造,发生冲突时依旧采用链表向后存储,但当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。
image.png

之所以选择红黑树,是为了解决二叉查找树在某些场合下退化成一个线性结构的缺陷。
我们可以继续查看底层putVal()的部分源码片段

【源码解析4】

// 遍历链表
for (int binCount = 0; ; ++binCount) {
   
   
    // 遍历到链表最后一个节点
    if ((e = p.next) == null) {
   
   
        p.next = newNode(hash, key, value, null);
        // 如果链表元素个数大于等于TREEIFY_THRESHOLD(8)
        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;
}

可以看到,当链表的元素个数大于等于8时,调用 treeifyBin(tab, hash)向红黑树转换,那我们继续跟入这个方法查看。

【源码解析5】

final void treeifyBin(Node<K,V>[] tab, int hash) {
   
   
    int n, index; Node<K,V> e;
    // 判断当前数组的长度是否小于 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果当前数组的长度小于 64,那么会选择先进行数组扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
   
   
        // 否则才将链表转换为红黑树

        TreeNode<K,V> hd = null, tl = null;
        do {
   
   
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
   
   
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

在treeifyBin方法中,先进行数组长度的判断,当长度小于64的时候 ,会先进行数组的扩容,当长度大于等于64时,才将链表转换为红黑树。

HashMap的扩容机制?

上面提到了扩容,我们从源码中可以看到,HashMap的扩容是通过resize()方法实现,我们继续跟进源码去看。

【源码解析6】

final Node<K,V>[] resize() {
   
   
    Node<K,V>[] oldTab = table; // 获取原来的数组 table
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取数组长度 oldCap
    int oldThr = threshold; // 获取阈值 oldThr
    int newCap, newThr = 0;
    if (oldCap > 0) {
   
    // 如果原来的数组 table 不为空
        if (oldCap >= MAXIMUM_CAPACITY) {
   
    // 超过最大值就不再扩充了,就只好随你碰撞去吧
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 没超过最大值,就扩充为原来的2倍
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
   
    // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的 resize 上限
    if (newThr == 0) {
   
   
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 将新阈值赋值给成员变量 threshold
    @SuppressWarnings({
   
   "rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建新数组 newTab
    table = newTab; // 将新数组 newTab 赋值给成员变量 table
    if (oldTab != null) {
   
    // 如果旧数组 oldTab 不为空
        for (int j = 0; j < oldCap; ++j) {
   
    // 遍历旧数组的每个元素
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
   
    // 如果该元素不为空
                oldTab[j] = null; // 将旧数组中该位置的元素置为 null,以便垃圾回收
                if (e.next == null) // 如果该元素没有冲突
                    newTab[e.hash & (newCap - 1)] = e; // 直接将该元素放入新数组
                else if (e instanceof TreeNode) // 如果该元素是树节点
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 将该树节点分裂成两个链表
                else {
   
    // 如果该元素是链表
                    Node<K,V> loHead = null, loTail = null; // 低位链表的头结点和尾结点
                    Node<K,V> hiHead = null, hiTail = null; // 高位链表的头结点和尾结点
                    Node<K,V> next;
                    do {
   
    // 遍历该链表
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
   
    // 如果该元素在低位链表中
                            if (loTail == null) // 如果低位链表还没有结点
                                loHead = e; // 将该元素作为低位链表的头结点
                            else
                                loTail.next = e; // 如果低位链表已经有结点,将该元素加入低位链表的尾部
                            loTail = e; // 更新低位链表的尾结点
                        }
                        else {
   
    // 如果该元素在高位链表中
                            if (hiTail == null) // 如果高位链表还没有结点
                                hiHead = e; // 将该元素作为高位链表的头结点
                            else
                                hiTail.next = e; // 如果高位链表已经有结点,将该元素加入高位链表的尾部
                            hiTail = e; // 更新高位链表的尾结点
                        }
                    } while ((e = next) != null); //
                    if (loTail != null) {
   
    // 如果低位链表不为空
                        loTail.next = null; // 将低位链表的尾结点指向 null,以便垃圾回收
                        newTab[j] = loHead; // 将低位链表作为新数组对应位置的元素
                    }
                    if (hiTail != null) {
   
    // 如果高位链表不为空
                        hiTail.next = null; // 将高位链表的尾结点指向 null,以便垃圾回收
                        newTab[j + oldCap] = hiHead; // 将高位链表作为新数组对应位置的元素
                    }
                }
            }
        }
    }
    return newTab; // 返回新数组
}

这个方法还是比较复杂的,由此可以看出HashMap的扩容还是比较耗时的,会伴随着数组的重新分配,旧数组的拷贝,数组容量的判断等等。

这里面我们可以发现每次新数组长度 newCap,是由oldCap << 1得到,因此每次扩容都是原来数组容量的2倍,默认初始容量为16,始终保持着2的幂次方大小,只有这样才能满足(n - 1) & hash的算法。

负载因子为什么去0.75?

很多面试官会问为什么要把DEFAULT_LOAD_FACTOR设为0.75?

其实,loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。可以百度统计学中的泊松分布原理,这里就不贴内容了。

【扩展】

loadFactor 负载因子是控制数组存放数据的疏密程度,loadFactor 越趋近于 1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor 越小,也就是趋近于 0,数组中存放的数据(entry)也就越少,也就越稀疏。

为什么线程不安全?

这个其实很好解释,对于HashMap而言,它的扩容也罢,put/get方法也罢,均没有任何加锁操作,这就意味着在多线程情况下,会带来风险。

风险1: put的时候导致元素丢失;如两个线程同时put,且key值相同的情况下,后一个线程put操作覆盖了前一个线程的操作,导致前一个线程的元素丢失。
风险2: put 和 get 并发时会导致 get 到 null;若一个线程的put操作触发了数组的扩容,这时另外一个线程去get,因为扩容的操作很耗时,这时有可能会卡死或者get到null。
风险3: 多线程下扩容会死循环;多线程下触发扩容时,因为前一个线程已经破坏了原有链表结构,后一个线程再去读取节点,进行链接的时候,很可能发生顺序错乱,从而形成一个环形链表,进而导致死循环。

总结

哎呀,妈呀!陆陆续续的写了3天,中间老是有工作琐事打断,每天抽空写一点,终于总结完了HashMap,大致的覆盖了HashMap的常见面试题,很多细节可能还是不足,后面有时间了再进行补充哈,多担待。

结尾彩蛋

如果本篇博客对您有一定的帮助,大家记得留言+点赞+收藏呀。原创不易,转载请联系Build哥!

image.png

目录
相关文章
|
2天前
|
存储 NoSQL Java
【面试宝藏】Redis 常见面试题解析
Redis 是内存数据结构存储系统,用作数据库、缓存和消息中间件,支持字符串、哈希、列表等数据类型。它的优点包括高性能、原子操作、持久化和复制。相比 Memcached,Redis 提供数据持久化、丰富数据结构和发布/订阅功能。Redis 采用单线程模型,但通过 I/O 多路复用处理高并发。常见的面试问题涉及持久化机制、过期键删除、回收策略、集群和客户端等。
22 4
|
2天前
|
存储 关系型数据库 MySQL
【面试宝藏】MySQL 面试题解析
MySQL面试题解析涵盖数据库范式、权限系统、Binlog格式、存储引擎对比、索引原理及优缺点、锁类型、事务隔离级别等。重点讨论了InnoDB与MyISAM的区别,如事务支持、外键和锁机制。此外,还提到了Unix时间戳与MySQL日期时间的转换,以及创建索引的策略。
14 4
|
2天前
|
安全 Java 数据安全/隐私保护
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
12 0
|
2天前
|
JSON 安全 Java
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
8 0
|
2天前
|
存储 缓存 NoSQL
【面试宝藏】Redis 常见面试题解析其二
Redis 高级面试题涵盖了哈希槽机制、集群的主从复制、数据丢失可能性、复制机制、最大节点数、数据库选择、连通性测试、事务操作、过期时间和内存优化等。Redis 使用哈希槽实现数据分布,主从复制保障高可用,异步复制可能导致写操作丢失。集群最大支持1000个节点,仅允许单数据库。可通过 `ping` 命令测试连接,使用 `EXPIRE` 设置过期时间,`MULTI/EXEC` 等进行事务处理。内存优化包括合理数据类型、设置过期时间及淘汰策略。Redis 可用作缓存、会话存储、排行榜等场景,使用 `SCAN` 查找特定前缀键,列表实现异步队列,分布式锁则通过 `SET` 命令和 Lua 脚本实现。
18 5
|
4天前
|
SQL 算法 大数据
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
|
4天前
|
存储 算法 搜索推荐
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
|
4天前
|
SQL 大数据 数据挖掘
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
|
4天前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
4天前
|
SQL 算法 大数据
深入解析力扣177题:第N高的薪水(SQL子查询与LIMIT详解及模拟面试问答)
深入解析力扣177题:第N高的薪水(SQL子查询与LIMIT详解及模拟面试问答)

推荐镜像

更多