hashmap浅析

这里是修真院后端小课堂，每篇分享文从

【背景介绍】【知识剖析】【常见问题】【解决方案】【编码实战】【扩展思考】【更多讨论】【参考文献】

八个方面深度解析后端知识/技能，本篇分享的是：

【hashmap浅析】

大家好，我是IT修真院北京分院第34期的学员岳晓鹏，一枚正直纯洁善良的java程序员，今天给大家分享一下，修真院官网java任务11，深度思考中的知识点——hashmap浅析

（1）背景介绍：

hashmap

Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。HashMap 是 Java Collection Framework 的重要成员，也是Map族中我们最为常用的一种。简单地说，HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，存储的对象是 Entry (同时包含了 Key 和 Value) 。在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。

（2）知识剖析：

哈希的概念

Hash 就是把任意长度的输入(又叫做预映射， pre-image)，通过哈希算法，变换成固定长度的输出(通常是整型)，该输出就是哈希值。这种转换是一种? 压缩映射 ，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能从散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度消息的摘要函数。

HashMap 的数据结构

我们知道，在Java中最常用的两种结构是 数组 和 链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap 就是这种应用的一个典型。实际上，HashMap 就是一个 链表数组，从上图中，我们可以形象地看出HashMap底层实现还是数组，只是数组的每一项都是一条链。

HashMap类中的几个概念

entry同时包含了 Key 和 Value,是hashmap中的存储对象

transient int size: 记录了Map中KV对的个数

capacity ：容量，如果不指定，默认容量是16

loadFactor:装载因子，用来衡量HashMap满的程度。loadFactor的默认值为0.75f

int threshold:临界值，当实际KV个数超过threshold时，HashMap会将容量扩容，threshold＝容量*加载因子

（3）常见问题：

hashmap读写速度怎么样？

（4）解决方案：

HashMap的底层是数组链表，所以读写数据的时候，根据key的哈希值就可以很容易找到entry的存储位置，在没有哈希冲突的情况下，时间复杂度为O(1)。

（5）编码实战：

介绍了下hashmap几个概念的实现及put操作的流程??

（6）拓展思考：

（7）参考文献：

https://blog.csdn.net/zxt0601/article/details/77413921【1】CSDN博客

https://blog.csdn.net/justloveyou_/article/details/62893086【2】CSDN博客

（8）更多讨论：

Q1：hashmap为什么要保证hashmap的容量为2的幂次方？ A1：保证hashmap的容量为2的幂次方，是为了减小哈希冲突，因为如果存在哈希冲突的时候，存储entry的时候，会出现一个位置上存在多个entry的情况，会造成读写速度的降低；使用2的幂次方的容量，存储的时候，会根据key的哈希值跟hashmap的(容量-1)进行位运算，这样的运算，当(容量-1)的二进制数全为1的时候，存储位置的计算结果是哈希冲突最小的。

Q2：既然hashmap的容量为2的幂次方，那么我们初始化时指定容量有什么用，hashmap会用哪个值？ A2：在初始化hashmap的时候，我们可以指定它的容量，但是，hashmap会在系统内部，根据指定的容量，计算出一个可以容纳指定容量的最小2的幂次方数；比方说指定25，它的容量实际是32，指定33，它的容量实际是64；这个跟hashmap后期使用的方式有关，要保证哈希冲突最小。 Q3：hashmap放入entry的时候，超过容量怎么样？ A3：hashmap超过容量的话会进行扩容，但是它的扩容条件并不是将容量存满；我们知道hashmap的size是已经存储的entry数，capacity是它的容量，loadFactor为装载因子---可以用来指示扩容条件，亦可以自己设定；当size=capacity*loadFactor的时候，就会自动进行扩容，扩容后的容量为之前的2倍；默认的因子为0.75，即size为总容量的75%时，会进行扩容，装载因子越大，那么对空间的利用更充分，但查找效率的也就越低；若装载因子越小，那么哈希表的数据将越稀疏，对空间造成的浪费也就越严重。系统默认因子为0.75，是对空间和时间的一种折衷。

（9）鸣谢：

（10）结束语：

今天的分享就到这里啦，欢迎大家点赞、转发、留言、拍砖~

PPT链接?视频链接

更多内容，可以加入IT交流群565734203与大家一起讨论交流

这里是技能树·IT修真院：，初学者转行到互联网的聚集地

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!