HashSet的存储原理或者工作原理,主要是从如何保证唯一性来说起。
这里面主要有3个问题,需要回答?
第一,为什么要采用Hash算法?有什么优势,解决了什么问题?
第二,所谓哈希表是一张什么表?
第三,HashSet如何保证保存对象的唯一性?会经历一个什么样的运算过程?
大家可以先思考,晚些再补充答案!
首先,我们要明确一点,HashSet底层采用的是HashMap来实现存储,其值作为HashMap的key
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
具体关于hashmap的细节再说
第一,为什么要采用Hash算法?有什么优势,解决了什么问题?
解决的问题是唯一性
存储数据,底层采用的是数组
当我们往数组放数据的时候,你如何判断是否唯一?
可以采用遍历的方式,逐个比较,但是这种效率低,尤其是数据很多的情况下
所以,为了解决这个效率低的问题,我们采用新的方式
采用hash算法,通过计算存储对象的hashcode,然后再跟数组长度-1做位运算,得到我们要存储在数组的哪个下标下,如果此时计算的位置没有其他元素,直接存储,不用比较。
此处,我们只会用到hashCode
但是随着元素的不断添加,就可能出现“哈希冲突”,不同的对象计算出来的hash值是相同的,这个时候,我们就需要比较,才需要用到equals方法
如果equals相同,则不插入,不相等,则形成链表
第二,所谓哈希表是一张什么表?
本质是一个数组,而且数组的元素是链表
JDK1.7的版本实现
JDK1.8做了优化
随着元素不断添加,链表可能会越来越长,会优化红黑树
网友评论