HashMap的存取原理你知道多少

Originally by 小秋苦逼的码农 2019-01-22

点击上方👆👆关注我

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

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

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

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

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

对于不熟悉hashcode()和equals()这两个方法的人来说，他可能会直接说，因为hashcode相同，那么两个对象是同一个对象，进而新的value覆盖掉旧的value。如果你这样回答，后果你懂。(当然可能面试会提醒你或直接问你别的问题了)。
有些人则会回答，由于hashcode相同，那么它们对应的bucket显然也是相同的，这个时候就会产生所谓的碰撞（hashmap的底层存储结构是数组+链表）。每个bucket索引对应一个链表，这个时候系统就会找到对应的链表，然后在链表的尾部加上这个Entry对象，如下图：（图画的有点丑，哈哈）

这个时候跑出来个第三者，自豪着补充了一句：根据hashcode找到对应的bucket之后，还会在对应的链表逐一检查这个链表里有没存在相同的key对象，这个时候是通过equals()这个方法来对比的。如果有，则用新的value取代旧的value。如果没有，则像楼上说的，在链表的尾部加上这个新的Entry对象。

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

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

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

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

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

这里可能大家有一些疑问，例如为啥默认的负载因子大小是0.75呢(看有些人在讨论这个问题)。对于这个我觉得可能是通过大量的数据测出来的（还没有去百度看别人的解答，仅代表个人观点，欢迎你们的解答）
这里在给大家解释以下负载因子的作用（可能有些人还不知道负载因子的干啥用的）

负载因子越大，数组要被填满时，元素就会越多，元素越多，冲突的几率就会越大，一个链表存的元素也会越多，查询的时候就会越慢。但是，此时空间的利用率更高了——空间换时间
负载因此越小，数组要被填满时，元素就会越少，冲突也会也少，一个链表的元素也会越少，查询的时候也就越快。但是，空间的利用率低了——时间换空间。