关于JAVA HashMap中的计算下标的值

HashMap中put根据Key的HashCode值计算出来的index下标。不同值计算不同的下标,但是我有个疑问,因为传入的值是不一样的,可能计算出的下标值非常的大,那么HashMap 会浪费很多空。那个indexFor这个计算方法,到底是怎么避免hash碰撞,而且还把计算出来值 固定在一个很小的范围类。这个怎么处理,有没有大神详解一下。

3个回答

单链表法来解决冲突较好。另外,节省空间得要靠修改默认的负载因子(load factor)。
这个比较容易理解:
Hashmap里面的bucket出现了单链表的形式,散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式,链表是单向链表。形成单链表的核心代码如下:
void addEntry(int hash, K key, V value, int bucketIndex) {

Entry e = table[bucketIndex];

table[bucketIndex] = new Entry(hash, key, value, e);

if (size++ >= threshold)

resize(2 * table.length);

上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序代码的 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。
HashMap里面没有出现hash冲突时,没有形成单链表时,hashmap查找元素很快,get()方法能够直接定位到元素,但是出现单链表后,单个bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。
当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。

还有一个hash函数做处理
http://helloworldfengyun.iteye.com/blog/2053869

这个你可以深究一下源码,HashMap解决哈希冲突的方式是维护一个链表,链表中存放哈希值相通的元素。本质上HashMap就是一个数组,而数组的元素是一个链表的。可以深入研究下HashMap的源码。推荐一个博客,写的很好的。http://blog.csdn.net/luanlouis/article/details/41576373

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
java hashmap集合如何最优的去除value为null或空的元素
java hashmap集合如何最优的去除value为null或空的元素
java中hashMap怎么转换成自定义的实体
java中hashMap怎么转换成自定义的实体 java中hashMap怎么转换成自定义的实体 java中hashMap怎么转换成自定义的实体
Java HashMap的get(),put()算法时间复杂度
Java7和Java8的HashMap的put(),get()方法的时间复杂度是啥?还请从平均,最好,最坏的角度分析。谢谢
关于java中要用hashmap存三个属性的方法
用HashMap模拟网上购物车。要求:从键盘输入(System.in)5本书的名称、单价、购买数量,将这些信息存入HashMap,然后将该HashMap作为输入参数创建方法getSum(HashMap books),该方法用于计算书的总价并返回。 书有三个属性,怎么用hashmap实现啊,求大神解答!
java中关于hashmap中的entrySet的疑问
hashmap中有个entrySet,翻遍了源码也只看到了声明了这个属性,没有任何赋值操作。 ``` private transient Set<Map.Entry<K,V>> entrySet = null; ``` 在我们调用entrySet遍历的时候却可以得到map中存放的相关键值对 ``` public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } ``` 请教一下,这个entrySet到底是在哪里赋的值。
el表达式取hashmap中的值
我在hashmap中有一个hashmap,现在我想在jsp中用el表达式取到hashmap集合中的hashmap里的值,请问怎么实现
java中获取HashMap中的table?
我的目标是想遍历table,打印真实在HashMap中table的数据结构,目前可以通过反射得到table,但是table中的元素是HashMap.Entry,是一个静态内部类,无法将其造型成HashMap.Entry类型,求助中 Field field=HashMap.class.getDeclaredField("table"); field.setAccessible(true); //设置些属性是可以访问的 Object obj=field.get(lzc2map); System.out.println(obj);
java8,如何根据条件合并两个List<HashMap>
假设两个List<HashMap> map1和List<HashMap> map2, map1的key有key1,key2,key3,key4,key5, map2有key1,key2,key6,key7,key8, 现需要以key1和key2为依据,若两者相等则将map1和map2中的元素合并为新的List<HashMap> map3, java8中是如何实现的?
Java1.8中HashMap扩容的特殊情况?
Java1.8中HashMap如果put键值对时,key的hashcode一样但内容不一样,就会一直在数组同一个位置插入(链表或者红黑树),那么一直插入到扩容门限,进行扩容,Java1.8的扩容机制并没有重新计算hash值,也就是说扩容后那个很长链表或者红黑树还是没有分开,还是很长,那这种情况下的扩容有什么意义?比如说原容量是16,那需要到12个后进行扩容,那如果有13个hash值是xxx...xx110111,他们本来在table[7],扩容后都在table[23],针所有键值对还是在一起,针对这样的情况hashmap是不是无能为例呢,还是说压根不会出现这么多有重复hash值的key。
关于Java中的hashMap的实现原理问题
hashmap底层实现是数组、链表、和红黑树,但是新增时如果key相同则覆盖相应的value,链表的作用还有意义吗?
java中Map类的子类HashMap的对象hashmap的put方法没有方法体
java中Map类的子类HashMap的对象hashmap的put方法为什么没有方法体, HashMap hashmap = new HashMap( ); hashmap.put( "Item0" ," Value0"); ...... 应该如何理解呢,谢谢分析解答
java中map的hashmap的用法
创建对象并加入到hashmap中,若想查找hashmap中某个对象的某个属性是否存在如何查找
java HashMap需要设置初始化大小吗?
HashMap需要设置初始化大小吗?hashmap即使设置初始化大小也是设置值为二的幂次方,但hashmap本身也会resize,自动扩容,也是乘以二的扩容,这样看来,hashmap设置初始化大小就没有意义了啊!
Java语言map hashmap的运用,编写一个程序用到map hashmap,要求有3个方法
Java语言map hashmap的运用,编写一个程序用到map hashmap,要求有3个方法
关于hashmap的容量问题
最近在研究hashmap的源码,jdk版本1.8 hashmap的第一层是一个数组Node<K,V>[] table table数组中存放的是一个结构体为node的单向链表 下面是和我的问题相关的几个属性: size hashmap中node的个数 capacity hashmap中table数组的长度 loadfactor 负载系数,默认0.75 threshold hashmap中的阈值(threshold是等于capacity乘以loadfactor) 当++size>threshold时hashmap会扩容,并且进行rehash操作 比如就拿初始值来说,capacity=16,threshold=12,当put第13个键值对时就会触发rehash,扩容之后,capaccity会翻倍变成32,同样threshold也会重新计算变成24 那问题来了,在hashmap中,size的大小不能大于阈值,更能大于capacity? 这岂不是意味着,node元素的个数还不如数组的长度大? 还是我理解有误,请高手指教
java HashMap存储list集合的问题
我定义一个全局的list集合,然后存储不同的数据,根据不同的Key存放在Map中,但是获取的时候确发现通过不同的Key拿到的Value却是同一个list集合,请问怎么办?
java求几个hashmap中key的并集,输出value
现有几个hashmap,可能有相同的key,但是value不同,求key的并集, 并输出在不同hashmap中的不同value,若不存在则为-1 比如hashmap1{(我,1),(你,2),(他,3),(它,4)} hashmap2{(猴,1)(狗,3)(你,4)(他,5)} hashmap3{(猴,10)(牛,2)(狗,5)(猪,4),(它,8)} hashmap4{(我,5),(牛,6)} 输出为 key hashmap1 hashmap2 hashmap3 hashmap4 我 1 -1 -1 5 你 2 4 -1 -1 他 3 5 -1 -1 它 4 -1 8 -1 猴 -1 1 10 -1 狗 -1 3 5 -1 牛 -1 -1 2 6 猪 -1 -1 4 -1
hashmap 中键值对问题
hashmap里面存放的事key和value键值对 key和value是如何建立起一一对应关系的
有关Java的HashMap的实现的问题
<div class="iteye-blog-content-contain" style="font-size: 14px;"> <p>在Java中,对于HashMap的定义是这样的:</p> <pre name="code" class="java">public class HashMap&lt;K,V&gt; extends AbstractMap&lt;K,V&gt; implements Map&lt;K,V&gt;, Cloneable, Serializable</pre> <p> 我想知道的是,为什么HashMap的父类AbstractMap已经implements了Map&lt;K,V&gt;接口,而在HashMap的定义中又再一次的声明implements Map&lt;K,V&gt;接口呢,这么做有什么意义呢?</p> <p> </p> <p>我记得我学长给我的答案是为了更好的面向接口编程,但有些模糊,请大家指导一下;</p> </div>
终于明白阿里百度这样的大公司,为什么面试经常拿ThreadLocal考验求职者了
点击上面↑「爱开发」关注我们每晚10点,捕获技术思考和创业资源洞察什么是ThreadLocalThreadLocal是一个本地线程副本变量工具类,各个线程都拥有一份线程私...
《奇巧淫技》系列-python!!每天早上八点自动发送天气预报邮件到QQ邮箱
将代码部署服务器,每日早上定时获取到天气数据,并发送到邮箱。 也可以说是一个小人工智障。 思路可以运用在不同地方,主要介绍的是思路。
加快推动区块链技术和产业创新发展,2019可信区块链峰会在京召开
11月8日,由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办,科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。   区块链技术被认为是继蒸汽机、电力、互联网之后,下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力,电力解决了人类基本的生活需求,互联网彻底改变了信息传递的方式,区块链作为构造信任的技术有重要的价值。   1...
阿里面试官问我:如何设计秒杀系统?我的回答让他比起大拇指
你知道的越多,你不知道的越多 点赞再看,养成习惯 GitHub上已经开源 https://github.com/JavaFamily 有一线大厂面试点脑图和个人联系方式,欢迎Star和指教 前言 Redis在互联网技术存储方面使用如此广泛,几乎所有的后端技术面试官都要在Redis的使用和原理方面对小伙伴们进行360°的刁难。 作为一个在互联网公司面一次拿一次Offer的面霸,打败了...
C语言魔塔游戏
很早就很想写这个,今天终于写完了。 游戏截图: 编译环境: VS2017 游戏需要一些图片,如果有想要的或者对游戏有什么看法的可以加我的QQ 2985486630 讨论,如果暂时没有回应,可以在博客下方留言,到时候我会看到。 下面我来介绍一下游戏的主要功能和实现方式 首先是玩家的定义,使用结构体,这个名字是可以自己改变的 struct gamerole { char n...
面试官问我:什么是消息队列?什么场景需要他?用了会出现什么问题?
你知道的越多,你不知道的越多 点赞再看,养成习惯 GitHub上已经开源 https://github.com/JavaFamily 有一线大厂面试点脑图、个人联系方式和人才交流群,欢迎Star和完善 前言 消息队列在互联网技术存储方面使用如此广泛,几乎所有的后端技术面试官都要在消息队列的使用和原理方面对小伙伴们进行360°的刁难。 作为一个在互联网公司面一次拿一次Offer的面霸...
Android性能优化(4):UI渲染机制以及优化
文章目录1. 渲染机制分析1.1 渲染机制1.2 卡顿现象1.3 内存抖动2. 渲染优化方式2.1 过度绘制优化2.1.1 Show GPU overdraw2.1.2 Profile GPU Rendering2.2 卡顿优化2.2.1 SysTrace2.2.2 TraceView 在从Android 6.0源码的角度剖析View的绘制原理一文中,我们了解到View的绘制流程有三个步骤,即m...
微服务中的Kafka与Micronaut
今天,我们将通过Apache Kafka主题构建一些彼此异步通信的微服务。我们使用Micronaut框架,它为与Kafka集成提供专门的库。让我们简要介绍一下示例系统的体系结构。我们有四个微型服务:订单服务,行程服务,司机服务和乘客服务。这些应用程序的实现非常简单。它们都有内存存储,并连接到同一个Kafka实例。 我们系统的主要目标是为客户安排行程。订单服务应用程序还充当网关。它接收来自客户的请求...
致 Python 初学者们!
作者| 许向武 责编 | 屠敏 出品 | CSDN 博客 前言 在 Python 进阶的过程中,相信很多同学应该大致上学习了很多 Python 的基础知识,也正在努力成长。在此期间,一定遇到了很多的困惑,对未来的学习方向感到迷茫。我非常理解你们所面临的处境。我从2007年开始接触 Python 这门编程语言,从2009年开始单一使用 Python 应对所有的开发工作,直至今...
究竟你适不适合买Mac?
我清晰的记得,刚买的macbook pro回到家,开机后第一件事情,就是上了淘宝网,花了500元钱,找了一个上门维修电脑的师傅,上门给我装了一个windows系统。。。。。。 表砍我。。。 当时买mac的初衷,只是想要个固态硬盘的笔记本,用来运行一些复杂的扑克软件。而看了当时所有的SSD笔记本后,最终决定,还是买个好(xiong)看(da)的。 已经有好几个朋友问我mba怎么样了,所以今天尽量客观...
程序员一般通过什么途径接私活?
二哥,你好,我想知道一般程序猿都如何接私活,我也想接,能告诉我一些方法吗? 上面是一个读者“烦不烦”问我的一个问题。其实不止是“烦不烦”,还有很多读者问过我类似这样的问题。 我接的私活不算多,挣到的钱也没有多少,加起来不到 20W。说实话,这个数目说出来我是有点心虚的,毕竟太少了,大家轻喷。但我想,恰好配得上“一般程序员”这个称号啊。毕竟苍蝇再小也是肉,我也算是有经验的人了。 唾弃接私活、做外...
字节跳动面试官这样问消息队列:分布式事务、重复消费、顺序消费,我整理了一下
你知道的越多,你不知道的越多 点赞再看,养成习惯 GitHub上已经开源 https://github.com/JavaFamily 有一线大厂面试点脑图、个人联系方式和人才交流群,欢迎Star和完善 前言 消息队列在互联网技术存储方面使用如此广泛,几乎所有的后端技术面试官都要在消息队列的使用和原理方面对小伙伴们进行360°的刁难。 作为一个在互联网公司面一次拿一次Offer的面霸...
Python爬虫爬取淘宝,京东商品信息
小编是一个理科生,不善长说一些废话。简单介绍下原理然后直接上代码。 使用的工具(Python+pycharm2019.3+selenium+xpath+chromedriver)其中要使用pycharm也可以私聊我selenium是一个框架可以通过pip下载 pip installselenium -ihttps://pypi.tuna.tsinghua.edu.cn/simple/ ...
阿里程序员写了一个新手都写不出的低级bug,被骂惨了。
这种新手都不会范的错,居然被一个工作好几年的小伙子写出来,差点被当场开除了。
Java工作4年来应聘要16K最后没要,细节如下。。。
前奏: 今天2B哥和大家分享一位前几天面试的一位应聘者,工作4年26岁,统招本科。 以下就是他的简历和面试情况。 基本情况: 专业技能: 1、&nbsp;熟悉Sping了解SpringMVC、SpringBoot、Mybatis等框架、了解SpringCloud微服务 2、&nbsp;熟悉常用项目管理工具:SVN、GIT、MAVEN、Jenkins 3、&nbsp;熟悉Nginx、tomca...
SpringBoot2.x系列教程(三十六)SpringBoot之Tomcat配置
Spring Boot默认内嵌的Tomcat为Servlet容器,关于Tomcat的所有属性都在ServerProperties配置类中。同时,也可以实现一些接口来自定义内嵌Servlet容器和内嵌Tomcat等的配置。 关于此配置,网络上有大量的资料,但都是基于SpringBoot1.5.x版本,并不适合当前最新版本。本文将带大家了解一下最新版本的使用。 ServerProperties的部分源...
Python绘图,圣诞树,花,爱心 | Turtle篇
每周每日,分享Python实战代码,入门资料,进阶资料,基础语法,爬虫,数据分析,web网站,机器学习,深度学习等等。 公众号回复【进群】沟通交流吧,QQ扫码进群学习吧 微信群 QQ群 1.画圣诞树 import turtle screen = turtle.Screen() screen.setup(800,600) circle = turtle.Turtle()...
作为一个程序员,CPU的这些硬核知识你必须会!
CPU对每个程序员来说,是个既熟悉又陌生的东西? 如果你只知道CPU是中央处理器的话,那可能对你并没有什么用,那么作为程序员的我们,必须要搞懂的就是CPU这家伙是如何运行的,尤其要搞懂它里面的寄存器是怎么一回事,因为这将让你从底层明白程序的运行机制。 随我一起,来好好认识下CPU这货吧 把CPU掰开来看 对于CPU来说,我们首先就要搞明白它是怎么回事,也就是它的内部构造,当然,CPU那么牛的一个东...
破14亿,Python分析我国存在哪些人口危机!
一、背景 二、爬取数据 三、数据分析 1、总人口 2、男女人口比例 3、人口城镇化 4、人口增长率 5、人口老化(抚养比) 6、各省人口 7、世界人口 四、遇到的问题 遇到的问题 1、数据分页,需要获取从1949-2018年数据,观察到有近20年参数:LAST20,由此推测获取近70年的参数可设置为:LAST70 2、2019年数据没有放上去,可以手动添加上去 3、将数据进行 行列转换 4、列名...
听说想当黑客的都玩过这个Monyer游戏(1~14攻略)
第零关 进入传送门开始第0关(游戏链接) 请点击链接进入第1关: 连接在左边→ ←连接在右边 看不到啊。。。。(只能看到一堆大佬做完的留名,也能看到菜鸡的我,在后面~~) 直接fn+f12吧 &lt;span&gt;连接在左边→&lt;/span&gt; &lt;a href="first.php"&gt;&lt;/a&gt; &lt;span&gt;←连接在右边&lt;/span&gt; o...
在家远程办公效率低?那你一定要收好这个「在家办公」神器!
相信大家都已经收到国务院延长春节假期的消息,接下来,在家远程办公可能将会持续一段时间。 但是问题来了。远程办公不是人在电脑前就当坐班了,相反,对于沟通效率,文件协作,以及信息安全都有着极高的要求。有着非常多的挑战,比如: 1在异地互相不见面的会议上,如何提高沟通效率? 2文件之间的来往反馈如何做到及时性?如何保证信息安全? 3如何规划安排每天工作,以及如何进行成果验收? ...... ...
作为一个程序员,内存和磁盘的这些事情,你不得不知道啊!!!
截止目前,我已经分享了如下几篇文章: 一个程序在计算机中是如何运行的?超级干货!!! 作为一个程序员,CPU的这些硬核知识你必须会! 作为一个程序员,内存的这些硬核知识你必须懂! 这些知识可以说是我们之前都不太重视的基础知识,可能大家在上大学的时候都学习过了,但是嘞,当时由于老师讲解的没那么有趣,又加上这些知识本身就比较枯燥,所以嘞,大家当初几乎等于没学。 再说啦,学习这些,也看不出来有什么用啊!...
这个世界上人真的分三六九等,你信吗?
偶然间,在知乎上看到一个问题 一时间,勾起了我深深的回忆。 以前在厂里打过两次工,做过家教,干过辅导班,做过中介。零下几度的晚上,贴过广告,满脸、满手地长冻疮。 再回首那段岁月,虽然苦,但让我学会了坚持和忍耐。让我明白了,在这个世界上,无论环境多么的恶劣,只要心存希望,星星之火,亦可燎原。 下文是原回答,希望能对你能有所启发。 如果我说,这个世界上人真的分三六九等,...
2020年全新Java学习路线图,含配套视频,学完即为中级Java程序员!!
新的一年来临,突如其来的疫情打破了平静的生活! 在家的你是否很无聊,如果无聊就来学习吧! 世上只有一种投资只赚不赔,那就是学习!!! 传智播客于2020年升级了Java学习线路图,硬核升级,免费放送! 学完你就是中级程序员,能更快一步找到工作! 一、Java基础 JavaSE基础是Java中级程序员的起点,是帮助你从小白到懂得编程的必经之路。 在Java基础板块中有6个子模块的学...
B 站上有哪些很好的学习资源?
哇说起B站,在小九眼里就是宝藏般的存在,放年假宅在家时一天刷6、7个小时不在话下,更别提今年的跨年晚会,我简直是跪着看完的!! 最早大家聚在在B站是为了追番,再后来我在上面刷欧美新歌和漂亮小姐姐的舞蹈视频,最近两年我和周围的朋友们已经把B站当作学习教室了,而且学习成本还免费,真是个励志的好平台ヽ(.◕ฺˇд ˇ◕ฺ;)ノ 下面我们就来盘点一下B站上优质的学习资源: 综合类 Oeasy: 综合...
爬取薅羊毛网站百度云资源
这是疫情期间无聊做的爬虫, 去获取暂时用不上的教程 import threading import time import pandas as pd import requests import re from threading import Thread, Lock # import urllib.request as request # req=urllib.request.Requ...
如何优雅地打印一个Java对象?
你好呀,我是沉默王二,一个和黄家驹一样身高,和刘德华一样颜值的程序员。虽然已经写了十多年的 Java 代码,但仍然觉得自己是个菜鸟(请允许我惭愧一下)。 在一个月黑风高的夜晚,我思前想后,觉得再也不能这么蹉跎下去了。于是痛下决心,准备通过输出的方式倒逼输入,以此来修炼自己的内功,从而进阶成为一名真正意义上的大神。与此同时,希望这些文章能够帮助到更多的读者,让大家在学习的路上不再寂寞、空虚和冷。 ...
雷火神山直播超两亿,Web播放器事件监听是怎么实现的?
Web播放器解决了在手机浏览器和PC浏览器上播放音视频数据的问题,让视音频内容可以不依赖用户安装App,就能进行播放以及在社交平台进行传播。在视频业务大数据平台中,播放数据的统计分析非常重要,所以Web播放器在使用过程中,需要对其内部的数据进行收集并上报至服务端,此时,就需要对发生在其内部的一些播放行为进行事件监听。 那么Web播放器事件监听是怎么实现的呢? 01 监听事件明细表 名...
3万字总结,Mysql优化之精髓
本文知识点较多,篇幅较长,请耐心学习 MySQL已经成为时下关系型数据库产品的中坚力量,备受互联网大厂的青睐,出门面试想进BAT,想拿高工资,不会点MySQL优化知识,拿offer的成功率会大大下降。 为什么要优化 系统的吞吐量瓶颈往往出现在数据库的访问速度上 随着应用程序的运行,数据库的中的数据会越来越多,处理时间会相应变慢 数据是存放在磁盘上的,读写速度无法和内存相比 如何优化 设计...
HTML5适合的情人节礼物有纪念日期功能
前言 利用HTML5,css,js实现爱心树 以及 纪念日期的功能 网页有播放音乐功能 以及打字倾诉感情的画面,非常适合情人节送给女朋友 具体的HTML代码 具体只要修改代码里面的男某某和女某某 文字段也可自行修改,还有代码下半部分的JS代码需要修改一下起始日期 注意月份为0~11月 也就是月份需要减一。 当然只有一部分HTML和JS代码不够运行的,文章最下面还附加了完整代码的下载地址 &lt;!...
相关热词 c# 为空 判断 委托 c#记事本颜色 c# 系统默认声音 js中调用c#方法参数 c#引入dll文件报错 c#根据名称实例化 c#从邮件服务器获取邮件 c# 保存文件夹 c#代码打包引用 c# 压缩效率
立即提问