热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HashMap的相关问题及其底层数据结构和操作流程

本文介绍了关于HashMap的相关问题,包括其底层数据结构、JDK1.7和JDK1.8的差异、红黑树的使用、扩容和树化的条件、退化为链表的情况、索引的计算方法、hashcode和hash()方法的作用、数组容量的选择、Put方法的流程以及并发问题下的操作。文章还提到了扩容死链和数据错乱的问题,并探讨了key的设计要求。对于对Java面试中的HashMap问题感兴趣的读者,本文将为您提供一些有用的技术和经验。

本文主要介绍关于java,数据结构,开发语言的知识点,对【HashMap的相关问题】和【java面试的时候你被提问过哪些问题】有兴趣的朋友可以看下由【PnJg?】投稿的技术文章,希望该技术和经验能帮到你解决你所遇的JavaSE相关技术问题。

java面试的时候你被提问过哪些问题

目录

HashMap底层数据结构

JDK1.7和1.8有何不同?

为什么要用红黑树?

扩容

树化,何时会树化?

为何一上来不树化

树化阈值为何是8

何时会退化为链表?

索引 

索引是如何计算的?

hashcode都有了,为何还要提供hash()方法?

数组容量为何是2的n次幂? 

 容量不用2的n次幂行不行?

Put方法与扩容

介绍一下put方法流程

1.7与1.8有何不同 

 扩容(加载)因子为何默认是 0.75f

 并发问题

 多线程下操作hashmap会有什么问题?

1、扩容死链(1.7)

2、数据错乱(1.7,1.8)

key 的设计 

key 的设计要求

 String 对象的 hashCode() 设计,为啥每次乘的是31


HashMap底层数据结构 JDK1.7和1.8有何不同? 1.7 数组 + 链表1.8 数组 + (链表 | 红黑树)---->元素较多时链表会转换成红黑树

hash表可以做到快速查找:查找元素时只需要计算hash值,根据计算出来的下标去对应的表中的下标与元素进行比较,无需从头到尾一个个的去对比。 

为什么要用红黑树?

当多个元素计算出的hash值相同时,根据链接法会接在同一个下标下面,这样hash表可以快速查询的优势就体现不出来了。解决链表长度的方法有两个:扩容、红黑树

扩容

当元素的个数超过当前容量的四分之三就会发生扩容,

 扩容之后桶下标要重新计算。

如果各个元素的原始hash值都一样,那么无论扩容几次都无法缩减链表长度。这时候只能树化。

树化,何时会树化?

树化要满足两个条件:链表长度超过树化阈值,固定值为8;数组容量大于64,否则不考虑树化。只有两个都满足才会树化。

红黑树:父节点左边的都比其小,父节点右边的都比其大(先根据hash码比较,一样的话根据key值比较)。搜索的时间复杂度是O(longN)

为何一上来不树化

当链表短的时候性能是比红黑树要好,hash 表的查找,更新的时间复杂度是 O(1),而红黑树的查找,更新的时间复杂度是 O(log_2⁡n ),TreeNode 占用空间也比普通 Node 的大,如非必要,尽量还是使用链表

树化阈值为何是8

红黑树不是一个正常的情况,正常情况下链表长度不可能超过8,只有当有人恶意DOS攻击(准备大量一样hash值的对象,计算出来的桶下标一样)的时候,就会造成链表特别长。hash 值如果足够随机,则在 hash 表内按泊松分布,在负载因子 0.75 的情况下,长度超过 8 的链表出现概率是 0.00000006,树化阈值选择 8 就是为了让树化几率足够小

何时会退化为链表?

情况1:在扩容时如果拆分树时,树元素个数 <= 6 则会退化链表

情况2:remove 树节点时,(是根据移除之前的状态判断)若 root、root.left、root.right、root.left.left 有一个为 null ,也会退化为链表

索引  索引是如何计算的?

首先,计算对象的 hashCode()

再进行调用 HashMap 的 hash() 方法进行二次哈希

二次 hash() 是为了综合高位数据,让哈希分布更为均匀

最后 & (capacity – 1)---->这个计算方法只能用在capacity为2的n次幂上---->用按位与运算代替了跟容量进行取模运算, 得到索引

hashcode都有了,为何还要提供hash()方法?

二次哈希:

 为了让最后计算索引的hash值分布的更加均匀,避免链表过长的情况。取高位是为了避免低位数字一样,跟数组容量相模的时候出现hash值一样

数组容量为何是2的n次幂? 

1. 计算索引时效率更高:如果是 2 的 n 次幂可以使用位与运算 & (capacity – 1)代替取模
2. 扩容时重新计算索引效率更高: hash & oldCap == 0 的元素留在原来位置 ,否则新位置 = 旧位置 + oldCap

 

 容量不用2的n次幂行不行?

容量为2的幂虽然计算索引速度快了,但是hash的分布就没那么好了,比如全都为偶数,那么只有偶数下标上有数。追求分布性更好可以选择质数作为容量大小,对于没有两次hash的值也能做到很好哈希分布性。

容量是 2 的 n 次幂这一设计计算索引效率更好,但 hash 的分散性就不好,需要二次 hash 来作为补偿,没有采用这一设计的典型例子是 Hashtable

Put方法与扩容 介绍一下put方法流程

HashMap 是懒惰创建数组的,首次使用才创建数组

计算索引(桶下标)

如果桶下标还没人占用,创建 Node 占位返回

如果桶下标已经有人占用

已经是 TreeNode 走红黑树的添加或更新逻辑

是普通 Node,走链表的添加或更新逻辑,如果链表长度超过树化阈值,走树化逻辑

返回前检查容量是否超过阈值,一旦超过进行扩容(先把这个元素放进旧数组,然后进行扩容,把旧数组的数据迁移到新数组)

1.7与1.8有何不同 

链表插入节点时,1.7 是头插法,1.8 是尾插法

1.7 是大于等于阈值且没有空位时才扩容,而 1.8 是大于阈值就扩容

1.8 在扩容计算 Node 索引时,会优化( hash & oldCap == 0 的元素留在原来位置 ,否则新位置 = 旧位置 + oldCap)

 扩容(加载)因子为何默认是 0.75f

1. 在空间占用与查询时间之间取得较好的权衡
2. 大于这个值,空间节省了,但链表就会比较长影响性能
3. 小于这个值,冲突减少了,但扩容就会更频繁,空间占用也更多

 并发问题  多线程下操作hashmap会有什么问题? 1、扩容死链(1.7)

线程1(绿色)的临时变量 e 和 next 刚引用了这俩节点,还未来得及移动节点,发生了线程切换,由线程2(蓝色)完成扩容和迁移

线程2 扩容完成,由于头插法,链表顺序颠倒。但线程1 的临时变量 e 和 next 还引用了这俩节点,还要再来一遍迁移

 

第一次循环

循环接着线程切换前运行,注意此时 e 指向的是节点 a,next 指向的是节点 be 头插 a 节点,注意图中画了两份 a 节点,但事实上只有一个(为了不让箭头特别乱画了两份)当循环结束是 e 会指向 next 也就是 b 节点

第二次循环

next 指向了节点 ae 头插节点 b当循环结束时,e 指向 next 也就是节点 a

第三次循环

next 指向了 nulle 头插节点 a,a 的 next 指向了 b(之前 a.next 一直是 null),b 的 next 指向 a,死链已成当循环结束时,e 指向 next 也就是 null,因此第四次循环时会正常退出

2、数据错乱(1.7,1.8)
public class HashMapMissData {
    public static void main(String[] args) throws InterruptedException {

        HashMap
  
    map = new HashMap<>(); Thread t1 = new Thread(() -> { map.put("a", new Object()); // 97 => 1 }, "t1"); Thread t2 = new Thread(() -> { map.put("1", new Object()); // 49 => 1 }, "t2"); t1.start(); t2.start(); t1.join(); t2.join(); System.out.println(map); } }
  

两个线程同时向hashmap添加一个相同hash值的数,会导致其中一个被覆盖,造成数据丢失

key 的设计  key 的设计要求

HashMap 的 key 可以为 null,但 Map 的其他实现则不然

作为 key 的对象,必须实现 hashCode (为了key在hashmap中能有更好的分布性,提高性能)和 equals(万一计算出来的索引一样,进一步用equals比较是不是相同的对象),并且 key 的内容不能修改(不可变)否则会出现找不到对应的key(因为hashcode值已经变了)

key 的 hashCode 应该有良好的散列性

 String 对象的 hashCode() 设计,为啥每次乘的是31

目标是达到较为均匀的散列效果,每个字符串的 hashCode 足够独特

字符串中的每个字符都可以表现为一个数字,称为 $S_i$,其中 i 的范围是 0 ~ n - 1

散列公式为: S0∗31^{(n-1)}+ S1∗31^{(n-2)}+ … Si ∗ 31^{(n-1-i)}+ …S_{(n-1)}∗31^0

31 代入公式有较好的散列特性,并且 31 * h 可以被优化为

即 32 ∗h -h 

即 2^5 ∗h -h

即 h≪5 -h

本文《HashMap的相关问题》版权归PnJg?所有,引用HashMap的相关问题需遵循CC 4.0 BY-SA版权协议。


推荐阅读
  • 模板引擎StringTemplate的使用方法和特点
    本文介绍了模板引擎StringTemplate的使用方法和特点,包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时,还介绍了StringTemplate语法中的属性和普通字符的使用方法,并提供了向模板填充属性的示例代码。 ... [详细]
  • 本文介绍了Java高并发程序设计中线程安全的概念与synchronized关键字的使用。通过一个计数器的例子,演示了多线程同时对变量进行累加操作时可能出现的问题。最终值会小于预期的原因是因为两个线程同时对变量进行写入时,其中一个线程的结果会覆盖另一个线程的结果。为了解决这个问题,可以使用synchronized关键字来保证线程安全。 ... [详细]
  • 本文整理了Java面试中常见的问题及相关概念的解析,包括HashMap中为什么重写equals还要重写hashcode、map的分类和常见情况、final关键字的用法、Synchronized和lock的区别、volatile的介绍、Syncronized锁的作用、构造函数和构造函数重载的概念、方法覆盖和方法重载的区别、反射获取和设置对象私有字段的值的方法、通过反射创建对象的方式以及内部类的详解。 ... [详细]
  • 阿,里,云,物,联网,net,core,客户端,czgl,aliiotclient, ... [详细]
  • 本文介绍了Python爬虫技术基础篇面向对象高级编程(中)中的多重继承概念。通过继承,子类可以扩展父类的功能。文章以动物类层次的设计为例,讨论了按照不同分类方式设计类层次的复杂性和多重继承的优势。最后给出了哺乳动物和鸟类的设计示例,以及能跑、能飞、宠物类和非宠物类的增加对类数量的影响。 ... [详细]
  • 预备知识可参考我整理的博客Windows编程之线程:https:www.cnblogs.comZhuSenlinp16662075.htmlWindows编程之线程同步:https ... [详细]
  • 深入理解Java虚拟机的并发编程与性能优化
    本文主要介绍了Java内存模型与线程的相关概念,探讨了并发编程在服务端应用中的重要性。同时,介绍了Java语言和虚拟机提供的工具,帮助开发人员处理并发方面的问题,提高程序的并发能力和性能优化。文章指出,充分利用计算机处理器的能力和协调线程之间的并发操作是提高服务端程序性能的关键。 ... [详细]
  • ejava,刘聪dejava
    本文目录一览:1、什么是Java?2、java ... [详细]
  • 1Lock与ReadWriteLock1.1LockpublicinterfaceLock{voidlock();voidlockInterruptibl ... [详细]
  • 如何自行分析定位SAP BSP错误
    The“BSPtag”Imentionedintheblogtitlemeansforexamplethetagchtmlb:configCelleratorbelowwhichi ... [详细]
  • 本文介绍了在rhel5.5操作系统下搭建网关+LAMP+postfix+dhcp的步骤和配置方法。通过配置dhcp自动分配ip、实现外网访问公司网站、内网收发邮件、内网上网以及SNAT转换等功能。详细介绍了安装dhcp和配置相关文件的步骤,并提供了相关的命令和配置示例。 ... [详细]
  • 个人学习使用:谨慎参考1Client类importcom.thoughtworks.gauge.Step;importcom.thoughtworks.gauge.T ... [详细]
  • 本文详细介绍了Java中vector的使用方法和相关知识,包括vector类的功能、构造方法和使用注意事项。通过使用vector类,可以方便地实现动态数组的功能,并且可以随意插入不同类型的对象,进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下,使用vector类是一个很好的选择。 ... [详细]
  • python3 nmap函数简介及使用方法
    本文介绍了python3 nmap函数的简介及使用方法,python-nmap是一个使用nmap进行端口扫描的python库,它可以生成nmap扫描报告,并帮助系统管理员进行自动化扫描任务和生成报告。同时,它也支持nmap脚本输出。文章详细介绍了python-nmap的几个py文件的功能和用途,包括__init__.py、nmap.py和test.py。__init__.py主要导入基本信息,nmap.py用于调用nmap的功能进行扫描,test.py用于测试是否可以利用nmap的扫描功能。 ... [详细]
  • C#多线程解决界面卡死问题的完美解决方案
    当界面需要在程序运行中不断更新数据时,使用多线程可以解决界面卡死的问题。一个主线程创建界面,使用一个子线程执行程序并更新主界面,可以避免卡死现象。本文分享了一个例子,供大家参考。 ... [详细]
author-avatar
殇不起2502909877
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有