HashMap面试知识点

一、HashMap实现原理

JDK1.7之前:HashMap由数组+链表组成。

JDK1.8之后:HashMap由数组+链表、红黑树组成,当链表长度超过8,且

二、HashMap中put()方法的过程

 ①首先检查数组table是否为空, 为空的话通过resize()方法进行创建。

  ②接着通过Hash函数计算key应该插入当数组的位置判断table[i]是否为空,为空的情况下直接插入,不为空的话判断table[i]的链表或树中是否有key,有key的话进行覆盖,没有的话进行插入操作,

  ③插入后如果为链表,需要判断是否长度大于8且table数组长度大于64,如果是的话转为红黑树

  ④size++,判断size大小是否大于threshold(负载因子 * table数组长度),如果大于的话,resize()方法进行扩容。

三、HashMap为什么是线程不安全的

 jdk1.7之前:HashMap链表的插入的方式是是头插法,在多线程的情况下,容易产生环形链表,查询时就会产生死循环问题。

 jdk1.8之后:HashMap的插入法改为了尾插法,但是多线程情况下依然会产生一些问题,例如前面说到的put()操作,有可能产生覆盖的情况。

  比如A、B两个线程put()插入同一个HashMap数组的位置,如果A操作判断该位置为null后时间片结束,那么B插入时该位置仍为空,会直接插入,当A线程继续执行插入操作时,该位置B插入的数据就会被覆盖掉了。

四、HashMap实现线程安全的几种形式

①HashTable

  不推荐,HashTable将几乎所有方法都使用了synchronized加锁,效率较低

②ConcurrentHashMap

  jdk1.7之前:将数据分成一段一段(Segment),每一段数据配一把锁,Segment 继承了ReentrantLock 所以Segment 是一种可重入锁。一个Segment包含一个HashEntry的数组。

  jdk1.8之后:取消了Segment分段锁,使用Node + CAS + synchronized,其中synchronized只锁红黑树或者链表的头结点,锁的粒度更细,效率更高。

五、HashMap的扩容机制

  HashMap的默认负载因子是0.75,当元素个数 > 0.75 * 数组长度时,开始扩容,数组长度变为之前的2倍。

六、HashMap为什么采用2倍扩容

    在解答这个问题之前,我们要知道二进制的取模 % 运算可以视为 & 运算。 向HashMap插入一个val值时,判断该val应该处于数组哪个位置的方法就是 val %( length - 1)。

   因此,HashMap的2倍会使得扩容后更新数据位置非常容易。比如当前HashMap的length为8,二进制为1000, length - 1 为 111,2倍扩容后,length扩大到16.只需要左移一位变为10000, length - 1是1111。对于需要更新位置的val,只需要多%1位就可以了,这一位就是length-1新增的那个位置,如果val的该位为0,那么val % length - 1的值也不会变,位置不需要变化;如果该位为1,那么val的位置只需要增加数组扩大的长度即可。

hash =         10101100                                             

length - 1 =            111

index =                   100

扩容后:

hash =         10101100

length - 1 =           1111

index =                 1100

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/17517.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

OceanBase 闪回查询

前言 在OB中,drop表可以通过 回收站 或者 以往的备份恢复来还原单表。当delete数据时,由于delete操作的对象不会进入回收站,此时需要通过闪回查询功能查看delete的数据,以便后续恢复 本次实验版本为 OceanBase 4.2.1.8&#xff0…

[A-18]ARMv8/ARMv9-Memory-内存空间的属性(Attributes Properties)

ver0.1 [看前序文章有惊喜,关注“浩瀚架构师”,可以解锁全部文章] 前言 在宏伟的ARM的内存世界中VMSA中,属性这个议题算不上最亮的星,就和屏幕前的你和我一样,平凡的活在这个茫茫然的人世间。纵使“丈夫贫践应未足,今日相逢无酒钱。”,也不要灰心面对生活,因为“山重…

【Linux】--环境变量

大家好呀,我是残念,希望在你看完之后,能对你有所帮助,有什么不足请指正!共同学习交流哦 本文由:残念ing原创CSDN首发,如需要转载请通知 个人主页:残念ing-CSDN博客,欢迎各…

vue3中使用 HTML5 Canvas 做一个案例总结笔记

这篇文章记录了在vue3中如何使用HTML5 Canvas做一个时钟的案例, 当然主要是HTML5 Canvas, 如何需要了解更多关于vue的知识前面也已经写过好几篇了,辛苦翻一下的... 开始写代码之前我们先来了解一下关于HTML5 Canvas 的基础知识 目录 一 .基础知识 1.了解canvas 1.1 基本用法…

基于微信小程序的开放实验室预约管理系统的设计与实现,LW+源码+讲解

摘 要 使用旧方法对开放实验室预约管理系统的信息进行系统化管理已经不再让人们信赖了,把现在的网络信息技术运用在开放实验室预约管理系统的管理上面可以解决许多信息管理上面的难题,比如处理数据时间很长,数据存在错误不能及时纠正等问题…

【汇编语言】更灵活的定位内存地址的方法(二)—— 从 [bx+idata] 到 [bx+si+idata]:让你灵活的访问内存

文章目录 前言1. [bxidata]1.1 更加灵活的访问内存1.2 示例1.3 问题一1.4 问题一的分析与求解 2. 用[bxidata]的方式进行数组的处理2.1 问题引入2.2 原来的解决方案2.3 新的解决方案2.3.1 改进后的程序2.3.2 还可以写成这样2.3.3 用C语言来描述看看 2.4 比较与总结 3. SI和DI3.…

[IP组播]IGMP配置实验

华为ensp拓补图 实验步骤 1.配置IP地址 AR1配置 # interface GigabitEthernet0/0/0ip address 192.168.1.1 255.255.255.0 # interface GigabitEthernet0/0/1ip address 12.1.1.1 255.255.255.0 # interface GigabitEthernet0/0/2ip address 13.1.1.1 255.255.255.0 #AR2…

Vue的局部使用

文章目录 什么是Vue?局部使用Vue快速入门 常用指令v-forv-bindv-if & v-showv-onv-model Vue生命周期 Axios案例 什么是Vue? Vue是一款构建用户界面的渐进式的JavaScript框架. 局部使用Vue 快速入门常用指令声明周期 快速入门 准备: 准备html页面,并引入Vue模块(…

DAHL:利用由跨越 29 个类别的 8,573 个问题组成的基准数据集,评估大型语言模型在生物医学领域长篇回答的事实准确性。

2024-11-14,由首尔国立大学创建的DAHL数据集,为评估大型语言模型(LLMs)在生物医学领域长文本生成中的幻觉问题提供了一个重要的工具,这对于提高模型的准确性和可靠性具有重要意义。 数据集地址:DAHL|生物医…

递归算法专题

题目&#xff1a; 方法一&#xff1a;不讲武德法&#xff0c;注意&#xff1a;面试不能用&#xff01;&#xff01; 代码&#xff1a; public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {//不讲伍德方法for(int x : A) C.add(x); …

验证双随机矩阵(doubly stochastic matrix) 满足C(P)=C(P^T)

验证双随机矩阵(doubly stochastic matrix) 满足C( P P P)C(P T ^T T) 双随机矩阵&#xff1a; 在数学中&#xff0c;一个双随机矩阵&#xff08;doubly stochastic matrix&#xff09;是一个满足以下条件的矩阵&#xff1a; 非负矩阵&#xff1a;矩阵中的每个元素都是非负的…

海外媒体发稿:中东地区阿拉伯邮报Arab Post新闻媒体宣发

​今天&#xff0c;我们要特别聚焦于中东地区的知名新闻媒体——阿拉伯邮报&#xff08;Arab Post&#xff09;&#xff0c;探讨其在海内外媒体宣发领域的重要性和影响力。 阿拉伯邮报作为一家备受关注的新闻媒体&#xff0c;涵盖了新闻、政治、娱乐和观点等多个领域&#xff…

Mysql-DQL语句

文章目录 DQL 语句简单查询查询表所有数据查询指定列 别名查询清除重复值查询结果参与运算 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Mysql专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月16日11点39分 DQL 语句 DQL 语句数据…

ERP软件市场展望:2025年的规模与趋势深度解析-亿发

随着数字化转型的深入&#xff0c;ERP软件市场正迎来新一轮的增长。预计到2025年&#xff0c;全球ERP软件市场规模将持续扩大&#xff0c;中国市场也将保持强劲的增长势头。 市场规模增长 根据市场研究报告&#xff0c;全球ERP软件市场在2019年已超过3,000亿美元&#xff0c;预…

推荐15个2024最新精选wordpress模板

以下是推荐的15个2024年最新精选WordPress模板&#xff0c;轻量级且SEO优化良好&#xff0c;适合需要高性能网站的用户。中文wordpress模板适合搭建企业官网使用。英文wordpress模板&#xff0c;适合B2C网站搭建&#xff0c;功能强大且兼容性好&#xff0c;是许多专业外贸网站的…

LLMs 损失函数篇

LLMs 损失函数篇 一、介绍一下 KL 散度 KL&#xff08;Kullback-Leibler&#xff09;散度衡量了两个概率分布之间的差异。公式为&#xff1a; D K L ( P ∥ Q ) ∑ P ( x ) log ⁡ P ( x ) Q ( x ) D_{KL}(P \| Q) \sum P(x) \log \frac{P(x)}{Q(x)} DKL​(P∥Q)∑P(x)logQ…

智慧社区管理系统提升物业服务效率与居民生活质量

内容概要 智慧社区管理系统正变得越来越重要&#xff0c;它为现代物业管理提供了全新的视角和方法。通过结合先进的技术&#xff0c;这套系统帮助物业公司优化其服务流程&#xff0c;使服务效率得到显著提升。想象一下&#xff0c;业主只需在手机上轻轻一点&#xff0c;就能完…

共享门店模式:创新零售的新篇章

​在消费升级和数字化转型的双重浪潮下&#xff0c;传统零售业正面临前所未有的挑战与机遇。其中&#xff0c;共享门店模式作为一种创新的商业模式&#xff0c;正逐渐成为实体店铺应对电商冲击、提升运营效率和市场竞争力的重要途径。本文将深入解析共享门店模式的内涵、优势、…

基于SpringBoot的旅游网站(程序+数据库+报告)

基于SpringBoot的旅游网站&#xff0c;系统包含两种角色&#xff1a;管理员、用户,系统分为前台和后台两大模块&#xff0c;主要功能如下。 【前台】&#xff1a; - 首页&#xff1a;展示旅游网站的核心内容&#xff0c;包括推荐的旅游线路、最新的旅游资讯等。 - 旅游线路&am…

shell编程--永久环境变量和字符串显位

环境变量 echo $HOME 在终端输出后会显示家目录有个root变量 我们会提出个疑问为什么平时我们在终端输入sl 或者which等等命令会输出一些内容呢&#xff0c;这是因为这些命令都有对应的环境变量。 我们查看一下环境变量 在终端输入&#xff1a; echo $PATH 我们看一下输出…