HashMap的存取原理你知道多少



在java的容器集合中,hashmap的使用频率可以说是相当高的。不过对于hashmap的存(put())以及取(get())的原理可能很多人还不大清楚,今天,我就给大家介绍下它是如何存如何取的

下面以回答问题的形式来讲解

假如有面试官问你,hashmap是如何存数据的,你会怎么回答?

  1. 我想每个人都知道hashmap是以键值对的方式来存数据的,有些人可能会这么回答:当我们执行put(key, value)方法的时候,以key作为键,value作为值来存,并且如果key相同的话,则新的value会覆盖掉旧的value。
  2. 而有些人可能会这么回答:hashmap在存数据的时候是基于hashing的原理,当我们调用put(key,value)方法的时候,其实我们会先对键key调用key.hashcode()方法,根据方法返回的hashcode来找到bucket的位置来存Entry对象。(Entry对象存有key和value)。如下图:(这里没有考虑碰撞)

显然前者和后者的回答,后者的回答还是相对好点的。不过,这可能仅仅只是故事的开始。


这时面试官可能会问你,如果两个key对象的hashcode相同怎么办?

  1. 对于不熟悉hashcode()和equals()这两个方法的人来说,他可能会直接说,因为hashcode相同,那么两个对象是同一个对象,进而新的value覆盖掉旧的value。如果你这样回答,后果你懂 。(当然可能面试会提醒你或直接问你别的问题了)。
  2. 有些人则会回答,由于hashcode相同,那么它们对应的bucket显然也是相同的,这个时候就会产生所谓的碰撞(hashmap的底层存储结构是 数组+链表)。每个bucket索引对应一个链表,这个时候系统就会找到对应的链表,然后在链表的尾部加上这个Entry对象,如下图:(图画的有点丑,哈哈)
  • 这个时候跑出来个第三者,自豪着补充了一句:根据hashcode找到对应的bucket之后,还会在对应的链表逐一检查这个链表里有没存在相同的key对象,这个时候是通过equals()这个方法来对比的。如果有,则用新的value取代旧的value。如果没有,则像楼上说的,在链表的尾部加上这个新的Entry对象。

这个时候,hashmap的put原理讲解就告一段落了。下面说说获取get(key)原理

其实get原理和put原理是差不多的,一个逆向的过程。

  1. 当我们调用get(key)的时候,会调用key的hashcode方法获得hashcode.
  2. 根据hashcode获取相应的bucket。
  3. 由于一个bucket对应的链表中可能存有多个Entry,这个时候会调用key的equals方法来找到对应的Entry
  4. 最后把值返回(这句好像是废话….但我还是想说下)。

继续涨知识……

和其他容器一样,当我们没有指定大小直接new一个hashmap的时候,系统会自动给我们初始化一个数值。如果我们在存数据的过程中,大小超过了负载因子定义的容量怎么办?

  • 这里先给大家解释下 负载因子:负载因子(load factor,假设大小为n)就是当一个map填满了n倍的bucket的时候,hashmap就会进行扩容。
  • 其实当一个map被填满到75%的时候(默认的负载因子大小是0.75),它就会进行扩容,创建一个大小是原理两倍的bucket数组,并且将原理的数据存放到新的数组里。

大家都知道,当Map在扩容新的数组并且移动数据的时候,都是比较消耗时间和内存的,如果我们事先能预测到我们到存的数据的大致大小的话,我们就可以在创建hashmap的时候指定大小,这样,可以大小减少扩容带来的消耗。

  • 这里可能大家有一些疑问,例如为啥默认的负载因子大小是0.75呢(看有些人在讨论这个问题)。对于这个我觉得可能是通过大量的数据测出来的(还没有去百度看别人的解答,仅代表个人观点,欢迎你们的解答)
  • 这里在给大家解释以下负载因子的作用(可能有些人还不知道负载因子的干啥用的)
  1. 负载因子越大,数组要被填满时,元素就会越多,元素越多,冲突的几率就会越大,一个链表存的元素也会越多,查询的时候就会越慢。但是,此时空间的利用率更高了——空间换时间
  2. 负载因此越小,数组要被填满时,元素就会越少,冲突也会也少,一个链表的元素也会越少,查询的时候也就越快。但是,空间的利用率低了——时间换空间。

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-05-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PingCAP的专栏

SuRF: 一个优化的 Fast Succinct Tries

在前一篇文章中,我简单介绍了 Succinct Data Structure,这里我们继续介绍 SuRF。

36450
来自专栏生信宝典

来一份Python学习题

3*2**2的输出是多少?(1分) 8 % 4的输出是多少?(1分) 32 + '32'的输出是什么?(1分) 32 > '32'的输出是什么?(1分) 'Sh...

44550
来自专栏Java架构沉思录

从节省Redis内存空间说开去

上周部门会议上讨论的一个议题是如何节省Redis内存空间,其中有个小伙伴提到可以从压缩字符串入手,我觉得这是一个可以尝试的思路。因为有时候我们存在Redis中的...

15820
来自专栏JavaEdge

亿万级数据处理的高效解决方案简介从set/map到hashtable/hashmap/hashset秘技一:分而治之/Hash映射 + HashMap统计 + 堆/快速/归并排序堆秘技二:双层桶划分秘

1.4K70
来自专栏Golang语言社区

使用 Go 语言学会 Tensorflow

Tensorflow 并不是一个专门用于机器学习的库,相反的,它是一个通用的用于图计算的库。它的核心部分是用 C++ 实现的,同时还有其它语言的接口库。Go 语...

51920
来自专栏程序猿DD

《JS正则表达式教程》汇总

正则表达式,又称规则表达式。(英语:Regular Expression,在代码中常简写为regex、regexp或RE),计算机科学的一个概念。正则表通常被用...

35860
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--广度优先搜索

广度优先搜索(BFS)是我们学的第一种图算法,它可以让你找出两样东西之间的最短距离。 这里提到了一个新的概念:图, 那什么是图呢? 图简介 图用于模拟不同的东...

33940
来自专栏Coding01

链式编程

链式编程或者链式写法,是将多个方法 (函数) 通过点号 (.) 或者 (->)等符号链接在一起成为一句代码,这样不仅可以增强代码的可读性,而且每次链接,都是对对...

11430
来自专栏挖掘大数据

处理海量数据的10种常见方法

本文将介绍10种处理海量数据问题的常见方法,也可以说是对海量数据的处理方法进行一个简单的总结,希望对你有帮助。

284100
来自专栏数据结构与算法

P3369 【模板】普通平衡树(Treap/SBT)(pb_ds版)

题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询...

28670

扫码关注云+社区

领取腾讯云代金券