面试精选11-谈HashSet的工作原理

HashSet的存储原理或者工作原理，主要是从如何保证唯一性来说起。

这里面主要有3个问题，需要回答？

第一，为什么要采用Hash算法？有什么优势，解决了什么问题？

第二，所谓哈希表是一张什么表？

第三，HashSet如何保证保存对象的唯一性？会经历一个什么样的运算过程？

大家可以先思考，下面来看解读！

第一，为什么要采用Hash算法？有什么优势，解决了什么问题？

解决的问题是唯一性判断的效率问题，保证为O(1)的复杂度

其存储数据的底层结构采用的是数组

当我们往数组放数据的时候，你如何判断是否唯一？

可以采用遍历的方式，逐个比较，但是这种效率低，尤其是数据很多的情况下，时间复杂度为O(n)

所以，为了解决这个效率低的问题，我们采用新的方式

采用hash算法的关键，是通过调用存储对象的hashcode方法得到一个数值，然后再根据这个数值，经过一通复杂的固定运算规则，得到我们要存储在数组的下标，如果此时计算的下标位置没有其他元素，则直接存储，不用比较，所以最佳的效果可以达到O(1)

此处，我们只会用到hashCode

但是随着元素的不断添加，就可能出现“哈希冲突”，不同的对象计算出来的hash值是相同的，这个时候，我们就需要比较，才需要用到equals方法

如果equals相同，则不插入，不相等，则形成链表

第二，所谓哈希表是一张什么表？

本质是一个数组，而且数组的元素是链表

以上是JDK1.7的版本实现

在JDK1.8版本之后做了优化

优化点：随着元素不断添加，链表可能会越来越长，那么再遍历链表的效率也会下降，所以会优化为红黑树，具体这个阈值是什么？

大家可以查看下源码，印象更深刻！