HashMap原理及面试高频问题

关于HashMap一些面试高频问题:

  1. HashMap的底层数据结构?
  2. HashMap 的工作原理?
  3. 为什么hashmap的在链表元素数量超过8时改为红黑树?
    a. 为什么在解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树?
    b. 我不用红黑树,用二叉查找树可以么?
    c. 为什么使用红黑树而不使用AVL树
    d. 那为什么阀值是8呢?
  4. HashMap是如何实现扩容的?(什么时候扩容)
  5. JDK8中对HashMap做了哪些改变?
  6. HashMap为什么是非线程安全的?
  7. HashMap 和 HashTable 的区别?
  8. HashMap 和 ConcurrentHashMap 的区别?
  9. HashMap 和 TreeMap的区别?

1. HashMap的底层数据结构

数组+链表。数组就是Entry数组,也叫table:

transient Node<K,V>[] table;

HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构(源码中叫Node),它具有next指针,可以连接下一个Entry实体/Node。 链表是用来解决hash冲突问题,当出现hash值一样的情形,就在数组上的对应位置形成一条链表。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
		// get/set/hashcode/equals/tostring..
    }

为什么用数组+链表? 数组是用来确定桶的位置,利用元素的key的hash值对数组长度取模得到。

JDK1.7中,使用的是链表,对于数组中的每一个元素,都可以有一条链表来存储元素。这就是有名的拉链式存储方法。

JDK1.8中,链表长度大于8的时候,链表会转成红黑树!

HashMap的数据结构图:
在这里插入图片描述

2. HashMap 的工作原理?

HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。
在这里插入图片描述

3. 为什么hashmap的在链表元素数量超过8时改为红黑树?

  • 红黑树是一个自平衡的二叉查找树,也就是说红黑树的查找效率是非常的高,查找效率会从链表的o(n)降低为o(logn)。
  • 首先说一说转换为红黑树的必要性:红黑树的插入、删除和遍历的最坏时间复杂度都是O(log(n)),而只使用单链表的时间复杂度是O(n)。因此,意外的情况或者恶意使用下导致hashCode()方法的返回值很差时,性能的下降将会是"优雅"的,只要Key具有可比性。
  • TreeNodes的大小是常规Nodes的两倍,所以只有桶中包含足够多的元素以供使用时,我们才会使用树。所以总体上来说还是空间换时间

a. 为什么在解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树?

  1. 构造红黑树要比构造链表复杂,在链表的节点不多的时候,从整体的性能看来, 数组+红黑树的结构可能不一定比数组+链表的结构性能高。就好比杀鸡焉用牛刀的意思。
  2. HashMap频繁的扩容,会造成底部红黑树不断的进行拆分和重组,这是非常耗时的。因此,也就是链表长度比较长的时候转变成红黑树才会显著提高效率。

b. 我不用红黑树,用二叉查找树可以么?

  1. 之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成树很深的问题),遍历查找会非常慢。
  2. 而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题。但与此同时,红黑树的插入、拆分和重组相比于二叉查找树更耗时。

c. 为什么使用红黑树而不使用AVL树

红黑树和AVL树(平衡二叉搜索树)的区别:

  • AVL树是更加严格的平衡,因此可以提供更快的查找速度,一般读取查找密集型任务,适用AVL树。
  • 红黑树更适合于插入修改密集型任务
  • 通常,AVL树的旋转比红黑树的旋转更加难以平衡和调试。

原因总结:

  1. AVL以及红黑树是高度平衡的树数据结构。它们非常相似,真正的区别在于在任何添加/删除操作时完成的旋转操作次数
  2. 两种实现都缩放为O(logN),其中N是叶子的数量,但实际上AVL树在查找密集型任务上更快:利用更好的平衡,树遍历平均更短。另一方面,插入和删除方面,AVL树速度较慢:需要更高的旋转次数才能在修改时正确地重新平衡数据结构。
  3. 在AVL树中,从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中,差异可以是2倍。
  4. 两个都O(log N)查找,但平衡AVL树可能需要O(logN)旋转,而红黑树将需要最多两次旋转使其达到平衡(尽管可能需要检查O(logN)节点以确定旋转的位置)。旋转本身是O(1)操作,因为你只是移动指针
  5. 总结用AVL树开销太大

为什么HashMap使用红黑树而不使用AVL树

d. 为什么阀值是8?

  • 关于为什么阀值是8

4. HashMap是如何实现扩容的?(什么时候扩容)

概括:hashmap中的元素个数超过数组大小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置。而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。扩容过程就是创建一个新的数组,其容量为旧数组的两倍,并重新计算旧数组中结点的存储位置。

流程图
在这里插入图片描述

5. jdk8中对HashMap做了哪些改变

  1. 之前jdk1.7的存储结构是数组+链表,到了jdk1.8变成了数组+链表+红黑树。(最显著改变)
  2. 发生hash碰撞时,由头插法改为尾插法
  3. Entry被Node替代(换了一个马甲)

6. HashMap为什么是非线程安全的?

HashMap的方法都是不安全的,主要体现在三方面:

  1. put等方法没有使用synchronized关键字
  2. resize时容易发生死循环
  3. put非null元素后get出来的却是null

第一种情况比较好理解,比如有两个线程A和B,首先A希望插入一个key-value对到HashMap中,首先计算记录所要落到的桶的索引坐标,然后获取到该桶里面的链表头结点,此时线程A的时间片用完了,而此时线程B被调度得以执行,和线程A一样执行,只不过线程B成功将记录插到了桶里面,假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的,那么当线程B成功插入之后,线程A再次被调度运行时,它依然持有过期的链表头但是它对此一无所知,以至于它认为它应该这样做,如此一来就覆盖了线程B插入的记录,这样线程B插入的记录就凭空消失了,造成了数据不一致的行为。

第二种较为复杂,容易导致CPU使用率较高,具体分析。

1.7中插入链表头部,是考虑到新插入的数据,更可能作为热点数据被使用,放在头部可以减少查找时间。

1.8改为插入链表尾部,原因就是防止环化。因为resize的赋值方式,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置,在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

这也是HashMap不能用于多线程场景的一个重要原因。

7. HashMap 和 HashTable 的区别?

  1. Hashtable的方法是同步的,HashMap未经同步,所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。查看Hashtable的源代码就可以发现,除构造函数外,Hashtable的所有 public 方法声明中都有 synchronized 关键字,而HashMap的源代码中则连 synchronized 的影子都没有
  2. Hashtable不允许 null 值(key 和 value 都不可以),HashMap允许 null 值(key和value都可以)
  3. 哈希值的使用不同:Hashtable直接使用对象的hashCode;HashMap重新计算hash值,而且用代替求模
  4. HashTable的锁是对整张Hash表进行synchronized

8. HashMap 和 ConcurrentHashMap 的区别?

ConcurrentHashMap底层采用分段的数组+链表实现,线程安全:通过把整个Map分为N个Segment,可以提供相同的线程安全;Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术;有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁

9. TreeMap

TreeMap是基于红黑树的一种提供顺序访问的Map,与HashMap不同的是它的getputremove之类操作都是O(logN)的时间复杂度,具体顺序可以由指定的Comparator来决定,或者根据键的自然顺序来判断。


参考:

  1. HashMap源码分析(jdk1.8,保证你能看懂)
  2. 这21 个刁钻的HashMap 面试题,我把阿里面试官吊打了!
  3. HashMap面试指南
  4. 面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别

热门文章

暂无图片
编程学习 ·

那些年让我们目瞪口呆的bug

程序员一生与bug奋战&#xff0c;可谓是杀敌无数&#xff0c;见怪不怪了&#xff01;在某知识社交平台中&#xff0c;一个“有哪些让程序员目瞪口呆的bug”的话题引来了6700多万的阅读&#xff0c;可见程序员们对一个话题的敏感度有多高。 1、麻省理工“只能发500英里的邮件” …
暂无图片
编程学习 ·

redis的下载与安装

下载redis wget http://download.redis.io/releases/redis-5.0.0.tar.gz解压redis tar -zxvf redis-5.0.0.tar.gz编译 make安装 make install快链方便进入redis ln -s redis-5.0.0 redis
暂无图片
编程学习 ·

《大话数据结构》第三章学习笔记--线性表(一)

线性表的定义 线性表&#xff1a;零个或多个数据元素的有限序列。 线性表元素的个数n定义为线性表的长度。n为0时&#xff0c;为空表。 在比较复杂的线性表中&#xff0c;一个数据元素可以由若干个数据项组成。 线性表的存储结构 顺序存储结构 可以用C语言中的一维数组来…
暂无图片
编程学习 ·

对象的扩展

文章目录对象的扩展属性的简洁表示法属性名表达式方法的name属性属性的可枚举性和遍历可枚举性属性的遍历super关键字对象的扩展运算符解构赋值扩展运算符AggregateError错误对象对象的扩展 属性的简洁表示法 const foo bar; const baz {foo}; baz // {foo: "bar"…
暂无图片
编程学习 ·

让程序员最头疼的5种编程语言

世界上的编程语言&#xff0c;按照其应用领域&#xff0c;可以粗略地分成三类。 有的语言是多面手&#xff0c;在很多不同的领域都能派上用场。大家学过的编程语言很多都属于这一类&#xff0c;比如说 C&#xff0c;Java&#xff0c; Python。 有的语言专注于某一特定的领域&…
暂无图片
编程学习 ·

写论文注意事项

参考链接 给研究生修改了一篇论文后&#xff0c;该985博导几近崩溃…… 重点分析 摘要与结论几乎重合 这一条是我见过研究生论文中最常出现的事情&#xff0c;很多情况下&#xff0c;他们论文中摘要部分与结论部分重复率超过70%。对于摘要而言&#xff0c;首先要用一小句话引…
暂无图片
编程学习 ·

安卓 串口开发

上图&#xff1a; 上码&#xff1a; 在APP grable添加 // 串口 需要配合在项目build.gradle中的repositories添加 maven {url "https://jitpack.io" }implementation com.github.licheedev.Android-SerialPort-API:serialport:1.0.1implementation com.jakewhart…
暂无图片
编程学习 ·

2021-2027年中国铪市场调研与发展趋势分析报告

2021-2027年中国铪市场调研与发展趋势分析报告 本报告研究中国市场铪的生产、消费及进出口情况&#xff0c;重点关注在中国市场扮演重要角色的全球及本土铪生产商&#xff0c;呈现这些厂商在中国市场的铪销量、收入、价格、毛利率、市场份额等关键指标。此外&#xff0c;针对…
暂无图片
编程学习 ·

Aggressive cows题目翻译

描述&#xff1a; Farmer John has built a new long barn, with N (2 < N < 100,000) stalls.&#xff08;John农民已经新建了一个长畜棚带有N&#xff08;2<N<100000&#xff09;个牛棚&#xff09; The stalls are located along a straight line at positions…
暂无图片
编程学习 ·

剖析组建PMO的6个大坑︱PMO深度实践

随着事业环境因素的不断纷繁演进&#xff0c;项目时代正在悄悄来临。设立项目经理转岗、要求PMP等项目管理证书已是基操&#xff0c;越来越多的组织开始组建PMO团队&#xff0c;大有曾经公司纷纷建造中台的气质&#xff08;当然两者的本质并不相同&#xff0c;只是说明这个趋势…
暂无图片
编程学习 ·

Flowable入门系列文章118 - 进程实例 07

1、获取流程实例的变量 GET运行时/进程实例/ {processInstanceId} /变量/ {变量名} 表1.获取流程实例的变量 - URL参数 参数需要值描述processInstanceId是串将流程实例的id添加到变量中。变量名是串要获取的变量的名称。 表2.获取流程实例的变量 - 响应代码 响应码描述200指…
暂无图片
编程学习 ·

微信每天自动给女[男]朋友发早安和土味情话

微信通知&#xff0c;每天给女朋友发早安、情话、诗句、天气信息等~ 前言 之前逛GitHub的时候发现了一个自动签到的小工具&#xff0c;b站、掘金等都可以&#xff0c;我看了下源码发现也是很简洁&#xff0c;也尝试用了一下&#xff0c;配置也都很简单&#xff0c;主要是他有一…
暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

项目经理,你有什么优势吗?

大侠被一个问题问住了&#xff1a;你和别人比&#xff0c;你的优势是什么呢? 大侠听到这个问题后&#xff0c;脱口而出道&#xff1a;“项目管理能力和经验啊。” 听者抬头看了一下大侠&#xff0c;显然听者对大侠的这个回答不是很满意&#xff0c;但也没有继续追问。 大侠回家…
暂无图片
编程学习 ·

nginx的负载均衡和故障转移

#注&#xff1a;proxy_temp_path和proxy_cache_path指定的路径必须在同一分区 proxy_temp_path /data0/proxy_temp_dir; #设置Web缓存区名称为cache_one&#xff0c;内存缓存空间大小为200MB&#xff0c;1天没有被访问的内容自动清除&#xff0c;硬盘缓存空间大小为30GB。 pro…
暂无图片
编程学习 ·

业务逻辑漏洞

身份认证安全 绕过身份认证的几种方法 暴力破解 测试方法∶在没有验证码限制或者一次验证码可以多次使用的地方&#xff0c;可以分为以下几种情况︰ (1)爆破用户名。当输入的用户名不存在时&#xff0c;会显示请输入正确用户名&#xff0c;或者用户名不存在 (2)已知用户名。…