每天一道面试题-从源码探究HashSet的工作原理

HashSet,给我们最直观的感受就是两点,不可重复和无序,底层采用了hash存储结构。

其底层是采用了HashMap,今天我们通过深入源码的方式来了解其背后的原理。

我们关注的点有几个

1,所谓的hash表是一个怎么样的结构?

hash表底层结构是一个数组,且数组的元素是一个链表结构。给大家画个图

每天一道面试题-从源码探究HashSet的工作原理

2,是如何保证唯一的?存放进去的细节如何?

首先,在hashSet的底层源代码中,我们发现,它采用的HashMap来存储的,所以我们的分析重点就是转移到HashMap的分析上

每天一道面试题-从源码探究HashSet的工作原理

HashMap的put方法如何实现的?接下来,我们继续跟踪源码

每天一道面试题-从源码探究HashSet的工作原理

关键的hash(key),即根据key得到关键的hash值,我们看看方法是怎么写的?

通过观察源代码,我们得到一个信息,当这个key不为null时,则结果值为多少,关键在于hashCode()方法。

每天一道面试题-从源码探究HashSet的工作原理

继续回到putValue方法的源码跟踪

每天一道面试题-从源码探究HashSet的工作原理

每天一道面试题-从源码探究HashSet的工作原理

整体来说,就是先通过一定的算法,其中算法的关键部分是hashCode方法,得到一个hash值,再通过hash值判断数组中是否存在该元素,如果不存在,则创建节点元素存放数组;如果存在,则添加。最后,判断当前容量是否超过阈值,超过则进行扩容。

3,hashCode()方法可以返回一个固定的整数吗?

答案是不可以,如果这个值返回一个固定值,可以想象得到,hashSet的原先的性能优势将荡然无存,所有的数据会集中到一个位置上,形成一个长链表。

每天一道面试题-从源码探究HashSet的工作原理

--------------------- 本文来自 互联网十年老兵- 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/happy_coding_life/article/details/80381233?utm_source=copy 

相关推荐