10-Map 相关面试题(集合)_关于map集合类的面试题-程序员宅基地

技术标签: Java源码  算法  java  链表  数据结构  

注:源码系列文章主要是对某付费专栏的总结记录。如有侵权,请联系删除。

Map 在面试中,占据了很大一部分的面试题,其中以 HashMap 为主,这些面试题目有的可以说清楚,有的很难说清楚,如果是面对面面试的话,建议画一画。

1 Map 整体数据结构类问题

1.1 说一说 HashMap 底层数据结构

答:HashMap 底层是 数组 + 链表 + 红黑树 的数据结构,数组的作用主要是方便快速查找,时间复杂度是 O(1),默认大小是 16,数组的下标索引是通过 Key 的 hash 计算出来的(index = (tab.length - 1) & hash),数组元素叫做 Node,当多个 key 的 hashcode 一致,但 key 值不同时,就叫做(hash 碰撞冲突),单个 Node 就会转化成链表,链表的查询复杂度是 O(n),当链表的长度大于等于 8 并且数组大小(tab.length)超过 64 时,链表就会转化成红黑树,红黑树的查询复杂度是 O(log(n)),简单来说,最坏的查询次数相当于红黑树的最大深度。

1.2 HashMap、TreeMap、LinkedHashMap 三者有什么相同点,有什么不同点?

答:

相同点:

  1. 三者在特定的情况下,都会使用红黑树;
  2. HashMap 和 LinkedHashMap 底层使用的 hash 算法相同,TreeMap 不需要 hash 算法,因为它没有桶的概念;
  3. 在迭代的过程中,如果 Map 的数据结构被改动,都会报 ConcurrentModificationException 错误。

不同点:

  1. HashMap 数据结构以数组为主,查询非常快,TreeMap 数据结构以红黑树为主,利用了红黑树左小右大的特点,可以实现 key 的排序,LinkedHashMap 在 HashMap 的基础上增加了链表的结构,实现了插入顺序访问和最少访问删除两种策略;
  2. 由于 Map 底层数据结构的差别,也导致了三者的使用场景的不同。TreeMap 适合需要根据 key 进行排序的场景,linkedHashMap 适合按照插入顺序访问,或需要删除最少访问元素的场景,剩余场景我们使用 HashMap 即可。我们工作中大部分场景基本都在使用 HashMap;
  3. 由于三种 Map 的底层数据结构的不同,导致了上层包装的 api 略有差异。

1.3 说一说 Map 的 hash 算法

static final int hash(Object key) {
    
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// index = (tab.length - 1) & hash

以上代码是 HashMap 的 hash 算法。

这其实是个数学问题,源码中就是通过以上代码来计算 hash 的,首先计算出 key 的 hashcode,因为 key 是 Object,所以会根据 key 的不同类型进行 hashcode 的计算,接着计算 h ^ (h >>> 16),这么做的好处是使大多数场景下,算出来的 hash 值比较分散。

一般来说,hash 值算出来之后,要计算当前 key 在数组中的索引下标位置,可以采用取模的方式,就是:索引下标位置 = hash 值 % 数组大小,这样做的好处,就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上,但取模操作对于处理器的计算是比较慢的,数学上有个公式,当 b 是 2 的幂次方时a & b = a & (b - 1),所以此处索引位置的计算公式我们可以更改为:(n - 1) & hash

此问题可以延伸出三个小问题:

  1. 为什么不用 key % 数组大小,而是需要用到 key 的 hash 值 % 数组大小?

答:如果 key 是数字,直接用 key % 数组大小是没有问题的,但我们的 key 还有可能是字符串,是复杂对象,这时候用 字符串或复杂对象 % 数组大小是不行的,所以需要先计算出 key 的 hash 值。

  1. 计算 hash 时,为什么要右移 16 位?

答:hash 算法是 h ^ (h >>> 16),为了使计算出的 hash 值更分散,所以选择先将 h 无符号右移 16 位,然后再与 h 异或,就能达到 h 的高 16 位和低 16 位都能参与计算,减少了碰撞的可能性。

  1. 为什么把取模操作换成了 & 操作?

答:key.hashCode() 算出来的 hash 值还不是数组的索引下标,为了随机的计算出索引的下标位置,我们还会用 hash 值和数组大小进行取模,这样子计算出来的索引下标比较均匀分布。

取模操处理器计算比较慢,处理器对 & 操作就比较擅长,换成了 & 操作,是有数学证明的支撑,提高了处理器处理的速度。

  1. 为什么提倡数组大小是 2 的幂次方?

答:因为只有大小是 2 的幂次方时,才能使 hash 值 % n(tab.length) == (n - 1) & hash 公式成立。

1.4 为解决 hash 冲突,大概有哪些方法?

答:

  1. 好的 hash 算法,复述上述的 哈市算法;
  2. 自动扩容。当数组大小快满的时候,采取自动扩容,可以减少 hash 冲突;
  3. hash 冲突发生时,采用链表来解决;
  4. hash 冲突严重时,链表会转化为红黑树,提高遍历速度。

网上列举的一些其它方法,尽量不要说,因为这些方法资料很少,实战用过的人更少,如果你没有深入研究的话,面试官让你深入描述一下很难说清楚,反而留下了不好的印象,说说 HashMap 现有的措施就足够了。

2 HashMap 源码细节类问题

2.1 HashMap 是如何扩容的?

答:

扩容的时机:

  1. put 时,当发现数组为空时,进行初始化扩容,默认扩容大小是 16;
  2. put 成功后,发现现有数组大小大于扩容的门阀值时,进行扩容,扩容大小为老数组大小的 2 倍 resize() 中的 newCap = oldCap << 1。(ArrayList 扩容为 1.5 倍(newCapacity = oldCapacity + (oldCapacity >> 1)))

扩容的门阀值是 threshold,每次扩容时 threshold 都会被重新计算,门阀值等于 数组大小 * 影响因子(0.75)

新数组初始化之后,需要将老数组的值拷贝到新数组上,链表和红黑树都有自己的拷贝方法。

2.2 hash 冲突时怎么办?

答:hash 冲突指定是 key 值的 hashcode 计算相同,但 key 值不同的情况。

如果桶中的元素原本只有一个或已经是链表了,新增元素直接追加到链表尾部;

如果桶中元素已经是链表,并且链表个数大于等于 8 时,此时有两种情况:

  1. 如果数组大小小于 64,数组再次扩容,链表不会转化为红黑树;
  2. 如果数组大小大于 64 时,链表就会转化为红黑树。

这里不仅仅判断了链表元素个数大于等于 8,还判断了数组大小,数组容量小于 64 没有立即转化的原因,猜测主要是因为红黑树占用的空间比链表大很多,转化也比较耗时,所以数组容量小的情况下冲突严重,我们可以先尝试扩容,看看能否通过扩容来解决冲突的问题。

2.3 为什么链表元素个数大于等于 8 时,链表要转化为红黑树?

答:当链表元素个数太多时,遍历可能比较耗时,转化成红黑树,可以使遍历的时间复杂度降低。但转化成红黑树,有空间和转化耗时的成本,我们通过 泊松分布公式 计算,正常情况下,链表个数出现 8 的几率不到千万分之一,所以说正常情况下,链表都不会转化成红黑树,这样设计的目的是为了防止非正常情况下,比如 hash 算法出问题时,导致链表元素个数轻易大于等于 8 时,仍然能够快速遍历。

延伸问题:红黑树什么时候转化成链表?

答:当节点的个数小于等于 6 时,红黑树会自动转化为链表,主要还是考虑红黑树的空间成本问题,当节点个数小于等于 6 时,遍历链表也很快,所以红黑树会重新变成链表。

2.4 HashMap 在 put 时,如果数组中已经有了这个 key,我不想把 value 覆盖怎么办?取值时,如果得到 value 是空时,想返回默认值怎么办?

答:如果数组有了 key,但不想覆盖 value,可以选择 putIfAbsent 方法,这个方法有给内置变量 onlyIfAbsent,内置是 true,就不会覆盖,我们平时使用的 put 方法,内置 onlyIfAbsent 为 false,是允许覆盖的。

取值时,如果为空,想返回默认值,可以使用 getOrDefault 方法,方法第一参数为 key,第二参数为你想返回的默认值,如 map.get(“10”, “3”),当 map 中没有 key 为 10 的值时,会返回默认值 3,而不是为空。

2.5 通过以下代码进行删除,是否可行?

HashMap<String,String > map = Maps.newHashMap();
map.put("1","1");
map.put("2","2");
map.forEach((s, s2) -> map.remove("1"));

答:不行,会报 ConcurrentModificationException,如下:

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
    
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
    
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

发现 HashMap 重写了 Map 的 forEach 方法,会判断 modCount。建议使用迭代器的方式进行珊瑚,原理同 ArrayList 迭代器类似。

2.6 描述一下 HashMap get、put 的过程

答:可以详细描述下源码的实现路径,说不清楚的话,可以画一画。

3 其它面试题

3.1 DTO 最为 Map 的 key 时,有无需要注意的点?

答:DTO 就是一个数据载体,可以看做拥有很多属性的 Java 类,我们可以对这些属性进行 get、set 操作。

看是什么类型的 Map。如果是 HashMap 的话,一定要覆写 equals 和 hashCode 方法,因为在 get、put 的时候,需要通过 equals 方法进行相等的判断;如果是 TreeMap 的话,DTO 需要实现 Comparable 接口,因为 TreeMap 会使用 Comparable 接口进行判断 key 的大小;如果是 LinkedHashMap 的话,和 HashMap 一样。

3.2 LinkedHashMap 中 的 LRU 是什么意思,是如何实现的

答:LRU,英文全称:Least recently used,中文叫做最近最少访问,在 LinkedHashMap 中,也叫做最少访问删除策略,我们可以通过 removeEldestEntry 方法设定一定的删除策略,使最少被访问的元素,在适当的时机被删除,原理是在 put 方法执行的最后,LinkedHashMap 会去检查这种策略,如果满足策略,就删除头节点。LinkedHashMap 覆写了 HashMap 的 afterNodeInsertion 方法。

保证头节点就是最少访问元素的原理是:LinkedHashMap 在 get 的时候,就会把当前访问的节点,移动到链表的尾部,慢慢的,就会使头部的节点成为最少被访问的元素。

3.3 为什么推荐 TreeMap 的元素最好都实现 Comparable 接口?但 key 是 String 的时候我们却没有额外的工作呢?

答:因为 TreeMap 的底层就是通过排序来比较两个 key 的大小的,所以推荐 key 实现 Comparable 接口,是为了让 key 的排序往你希望的排序顺序上发展,而 String 本身已经实现了 Comparable 接口,所以使用 String 时,我们不需要额外的工作,不仅仅是 String,其它包装类型也都实现了 Comparable 接口,如 Long、Double、Float 等等。

总结

Map 的面试题主要是 HashMap 为主,会问很多源码方面的问题,TreeMap 和 LinkedHashMap 主要以功能和场景为主,作为加分项。
Map 的面试题很多,但只要弄懂原理,题目再多变化,回答起来都会比较简单。

------------------------------------- END -------------------------------------

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xinxisimple/article/details/104654167

智能推荐

hive使用适用场景_大数据入门:Hive应用场景-程序员宅基地

文章浏览阅读5.8k次。在大数据的发展当中,大数据技术生态的组件,也在不断地拓展开来,而其中的Hive组件,作为Hadoop的数据仓库工具,可以实现对Hadoop集群当中的大规模数据进行相应的数据处理。今天我们的大数据入门分享,就主要来讲讲,Hive应用场景。关于Hive,首先需要明确的一点就是,Hive并非数据库,Hive所提供的数据存储、查询和分析功能,本质上来说,并非传统数据库所提供的存储、查询、分析功能。Hive..._hive应用场景

zblog采集-织梦全自动采集插件-织梦免费采集插件_zblog 网页采集插件-程序员宅基地

文章浏览阅读496次。Zblog是由Zblog开发团队开发的一款小巧而强大的基于Asp和PHP平台的开源程序,但是插件市场上的Zblog采集插件,没有一款能打的,要么就是没有SEO文章内容处理,要么就是功能单一。很少有适合SEO站长的Zblog采集。人们都知道Zblog采集接口都是对Zblog采集不熟悉的人做的,很多人采取模拟登陆的方法进行发布文章,也有很多人直接操作数据库发布文章,然而这些都或多或少的产生各种问题,发布速度慢、文章内容未经严格过滤,导致安全性问题、不能发Tag、不能自动创建分类等。但是使用Zblog采._zblog 网页采集插件

Flink学习四:提交Flink运行job_flink定时运行job-程序员宅基地

文章浏览阅读2.4k次,点赞2次,收藏2次。restUI页面提交1.1 添加上传jar包1.2 提交任务job1.3 查看提交的任务2. 命令行提交./flink-1.9.3/bin/flink run -c com.qu.wc.StreamWordCount -p 2 FlinkTutorial-1.0-SNAPSHOT.jar3. 命令行查看正在运行的job./flink-1.9.3/bin/flink list4. 命令行查看所有job./flink-1.9.3/bin/flink list --all._flink定时运行job

STM32-LED闪烁项目总结_嵌入式stm32闪烁led实验总结-程序员宅基地

文章浏览阅读1k次,点赞2次,收藏6次。这个项目是基于STM32的LED闪烁项目,主要目的是让学习者熟悉STM32的基本操作和编程方法。在这个项目中,我们将使用STM32作为控制器,通过对GPIO口的控制实现LED灯的闪烁。这个STM32 LED闪烁的项目是一个非常简单的入门项目,但它可以帮助学习者熟悉STM32的编程方法和GPIO口的使用。在这个项目中,我们通过对GPIO口的控制实现了LED灯的闪烁。LED闪烁是STM32入门课程的基础操作之一,它旨在教学生如何使用STM32开发板控制LED灯的闪烁。_嵌入式stm32闪烁led实验总结

Debezium安装部署和将服务托管到systemctl-程序员宅基地

文章浏览阅读63次。本文介绍了安装和部署Debezium的详细步骤,并演示了如何将Debezium服务托管到systemctl以进行方便的管理。本文将详细介绍如何安装和部署Debezium,并将其服务托管到systemctl。解压缩后,将得到一个名为"debezium"的目录,其中包含Debezium的二进制文件和其他必要的资源。注意替换"ExecStart"中的"/path/to/debezium"为实际的Debezium目录路径。接下来,需要下载Debezium的压缩包,并将其解压到所需的目录。

Android 控制屏幕唤醒常亮或熄灭_android实现拿起手机亮屏-程序员宅基地

文章浏览阅读4.4k次。需求:在诗词曲文项目中,诗词整篇朗读的时候,文章没有读完会因为屏幕熄灭停止朗读。要求:在文章没有朗读完毕之前屏幕常亮,读完以后屏幕常亮关闭;1.权限配置:设置电源管理的权限。

随便推点

目标检测简介-程序员宅基地

文章浏览阅读2.3k次。目标检测简介、评估标准、经典算法_目标检测

记SQL server安装后无法连接127.0.0.1解决方法_sqlserver 127 0 01 无法连接-程序员宅基地

文章浏览阅读6.3k次,点赞4次,收藏9次。实训时需要安装SQL server2008 R所以我上网上找了一个.exe 的安装包链接:https://pan.baidu.com/s/1_FkhB8XJy3Js_rFADhdtmA提取码:ztki注:解压后1.04G安装时Microsoft需下载.NET,更新安装后会自动安装如下:点击第一个傻瓜式安装,唯一注意的是在修改路径的时候如下不可修改:到安装实例的时候就可以修改啦数据..._sqlserver 127 0 01 无法连接

js 获取对象的所有key值,用来遍历_js 遍历对象的key-程序员宅基地

文章浏览阅读7.4k次。1. Object.keys(item); 获取到了key之后就可以遍历的时候直接使用这个进行遍历所有的key跟valuevar infoItem={ name:'xiaowu', age:'18',}//的出来的keys就是[name,age]var keys=Object.keys(infoItem);2. 通常用于以下实力中 <div *ngFor="let item of keys"> <div>{{item}}.._js 遍历对象的key

粒子群算法(PSO)求解路径规划_粒子群算法路径规划-程序员宅基地

文章浏览阅读2.2w次,点赞51次,收藏310次。粒子群算法求解路径规划路径规划问题描述    给定环境信息,如果该环境内有障碍物,寻求起始点到目标点的最短路径, 并且路径不能与障碍物相交,如图 1.1.1 所示。1.2 粒子群算法求解1.2.1 求解思路    粒子群优化算法(PSO),粒子群中的每一个粒子都代表一个问题的可能解, 通过粒子个体的简单行为,群体内的信息交互实现问题求解的智能性。    在路径规划中,我们将每一条路径规划为一个粒子,每个粒子群群有 n 个粒 子,即有 n 条路径,同时,每个粒子又有 m 个染色体,即中间过渡点的_粒子群算法路径规划

量化评价:稳健的业绩评价指标_rar 海龟-程序员宅基地

文章浏览阅读353次。所谓稳健的评估指标,是指在评估的过程中数据的轻微变化并不会显著的影响一个统计指标。而不稳健的评估指标则相反,在对交易系统进行回测时,参数值的轻微变化会带来不稳健指标的大幅变化。对于不稳健的评估指标,任何对数据有影响的因素都会对测试结果产生过大的影响,这很容易导致数据过拟合。_rar 海龟

IAP在ARM Cortex-M3微控制器实现原理_value line devices connectivity line devices-程序员宅基地

文章浏览阅读607次,点赞2次,收藏7次。–基于STM32F103ZET6的UART通讯实现一、什么是IAP,为什么要IAPIAP即为In Application Programming(在应用中编程),一般情况下,以STM32F10x系列芯片为主控制器的设备在出厂时就已经使用J-Link仿真器将应用代码烧录了,如果在设备使用过程中需要进行应用代码的更换、升级等操作的话,则可能需要将设备返回原厂并拆解出来再使用J-Link重新烧录代码,这就增加了很多不必要的麻烦。站在用户的角度来说,就是能让用户自己来更换设备里边的代码程序而厂家这边只需要提供给_value line devices connectivity line devices