关于hashmap的一道面试题_hashmap面试题-程序员宅基地

技术标签： java  

面试官：

hashmap的底层数据结构是什么

小瑞：

底层是数组加链表，jdk1.8之后优化增加了红黑树

 

面试官：

什么情况下会有红黑树

小瑞：

当链表长度超过8时，会将链表转为红黑树

面试官：

hashmap的容量为什么是2的幂

小瑞：

因为要根据hash算法得到数据的下标，

为了实现高效的Hash算法，hashMap的发明者采用了位运算的方式。

如果不是2的幂，产生哈希碰撞的概率大，效率会变低。

 

（补充）公式：index = HashCode（Key） & （Length - 1）

以值为“book”的key来演示整个过程：

1.计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。

2.假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。

3.把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。

 

面试官：

hashmap扩容是怎么处理的

小瑞：

影响发生Resize的因素有两个：

1.Capacity

HashMap的当前长度。HashMap的长度是2的幂。

2.LoadFactor

HashMap负载因子，默认值为0.75f。

衡量HashMap是否进行Resize的条件如下：

HashMap.Size >= Capacity * LoadFactor

HashMap的Rezie不是简单的把长度扩大，而是经过两个步骤

1.扩容

创建一个新的Entry空数组，长度是原数组的2倍。

2.ReHash

遍历原Entry数组，把所有的Entry重新Hash到新数组。

为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。


面试官：

jdk1.7与1.8在数据插入方式有什么区别

 

小瑞：

1.7是头插法，1.8是尾插法，将元素放到链表的尾部

 

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

智能推荐

【UnityDOTS 小知识】Job的依赖项_unity job schedule-程序员宅基地

文章浏览阅读202次。因为Job多数都是多线程处理，所以处理好线程之间的依赖关系就很重要。类比于Task之间的依赖处理。_unity job schedule

python if语句判断字符串相等_python怎样判断字符串相等-程序员宅基地

文章浏览阅读4.8k次。python字符串如何判断相等1.is来判断groupName = params['groupName'] ##groupName的值是'url'reqBody['dim'] = groupNameprint("reqBody_dim-SummaryListHandler", reqBody['dim'])## ('reqBody_dim-SummaryListHandler', u'url')p..._python中if判断字符串相等

java Springboot富文本编辑器ueditor内容使用poi导出为word文件_springboot 富文本转word-程序员宅基地

文章浏览阅读8.8k次。本文讲解在springboot环境下，将ueditor保存到数据库中的html内容使用poi导出为word文件，亲测导出的文件在word和wps上打开均正常显示。首先，在pom.xml文件中引入poi包<dependency> <groupId>org.apache.poi</groupId> <artifactId>poi</..._springboot 富文本转word

golang技术栈常见网址_golang站点-程序员宅基地

文章浏览阅读8.7k次，点赞2次，收藏11次。go所有，包含goadmingolang标准库文档golang修养之路Golang Profiling: 关于 pprofgo问题go语言设计与实现go.mod解析proto3proto英文，谷歌govcl文档，桌面应用开发xorm文档xorm gitgo-zero git文档成为 Go 高手的 8 个 GitHub 开源项目docker build文档k8s官方文档k8s 胡说云原生安装 Kuboard安装k8sk8s训练营k3s中文文档drone官方文档golang的excel操作文_golang站点

java word转pdf【去水印】_spire.dov license-程序员宅基地

文章浏览阅读962次。word转pdf依赖： <!--word转pdf关键包--> <dependency> <groupId&_spire.dov license

AES-GCM加密算法-程序员宅基地

文章浏览阅读6.5k次，点赞4次，收藏11次。AES是一种对称加密算法，它的相关概念在此不赘述。GCM ( Galois/Counter Mode) 指的是该对称加密采用Counter模式，并带有GMAC消息认证码。在详细介绍AES-GCM之前，我们先了解一些相关概念。下文中出现的符号:Ek 使用秘钥k对输入做对称加密运算 XOR 异或运算 Mh 将输入与秘钥h在有限域GF(2^128)上做乘法 ECB（ Electronic Mode 电子密码本模式）当我们有一段明文，需要..._aes-gcm

随便推点

ROS中base_link, odom, fixed_frame, target_frame和虚拟大地图map的关系-程序员宅基地

文章浏览阅读166次。前面已经介绍了如何使用URDF建造机器人小车并显示在Rviz的仿真环境里面，但是小车是静止的。下面介绍如何让它在Rviz里面动起来，并理清URDF,TF 和 odom 的关系。1. ROS中base_link, odom, fixed_frame, target_frame和虚拟大地图map的关系一般在urdf文件中都要定义base_link，它代表了机器人的主干，其它所有的frame都是..._target_frame frame cartographer

使用OpenGL实现遮罩效果_opengles 透明遮罩-程序员宅基地

文章浏览阅读7.9k次。本文适合于Cocos2d-X等使用OpenGL API的渲染框架一般实现自定义遮罩效果主要介绍以下几种：使用Stencil Buffer使用GL_SCISSOR_TEST（适合矩形区域）使用Shader使用BlendFunc（推荐！）_opengles 透明遮罩

《 2020年抖音用户画像报告 》-程序员宅基地

文章浏览阅读5.5k次。via：巨量算数抖音DAU超4亿，较去年同期的2.5亿，增长了60%。抖音与头条的重合度为32.1%，重合用户占抖音的42.2%。抖音与西瓜的重合度为24.6%,重合用户占抖音的29.5..._2020年抖音用户画像分析报告

Python3 SciPy解常微分方程 用Matplotlib演示_matplotlib 微分方程-程序员宅基地

文章浏览阅读7.8k次，点赞4次，收藏33次。Python科学计算 简单记录几篇笔记 SciPy解常微分方程integrate模块提供的odeint函数Anaconda 3的jupyter notebook上matplotlib 2D 绘制求解 牛顿冷却定律matplotlib 3D 绘制求解 洛伦兹吸引子_matplotlib 微分方程

黑马程序员--------语法基础_632485820-程序员宅基地

文章浏览阅读346次。-----Java培训、Android培训、iOS培训、.Net培训、期待与您交流！ -------Java语法基础1，关键字：其实就是某种语言赋予了特殊含义的单词。保留字：其实就是还没有赋予特殊含义，但是准备日后要使用过的单 词。 2，标示符：Java中的包、类、方法、参数和变量的名字，可由任意顺序的大小写字母、数字、下划线（_）和美元符号（$）组成，但标识符不能以数_632485820

Linux下常用软件推荐列表（欢迎补充。。。）_linx软件-程序员宅基地

文章浏览阅读2.4k次。Linux下推荐的常用应用程序列表一,网页浏览1,firefoxfirefox是现在最火的一个浏览器,支持好多扩展和插件,也有很多漂亮的主题.firefox就是mozilla-firefox,他是把mozilla的网页浏览的功能分离为一个单独的浏览器.Firefox一般是linux系统自带的默认浏览器.2,opera(非开源免费软件)opera是号称最快的浏览器.能直接浏览wa_linx软件

推荐文章

热门文章

相关标签