HashSet的数据结构跟作用

た入场券 2022-05-10 01:54 121阅读 0赞

转自：[https://www.cnblogs.com/runwulingsheng/p/5208762.html][https_www.cnblogs.com_runwulingsheng_p_5208762.html]

(1) 为啥要用HahSet?  
    假如我们现在想要在一大堆数据中查找X数据。LinkedList的数据结构就不说了，查找效率低的可怕。ArrayList哪，如果我们不知道X的位置序号，还是一样要全部遍历一次直到查到结果，效率一样可怕。HashSet天生就是为了提高查找效率的。

HashSet的查找效率高，我想是因为它是根据HashCode来存储对象的，所以在查找时,先计算出对象的HashCode，然后就可以根据这个来找出它的位置，查找速度应该是O(1)，不过看了下面的解释，我这个猜想是错的

HashSet的底层是基于HashMap的，就是说它的数据结构是跟HashMap一样的。

但它存储的是对象，在Entry中，对象对应的是Key，而Value是固定的一个值（所有的对象对应的Value都是那个值---Object对象PRESENT）这样做的目的是为了符合HashMap的语法而已.

4) HashSet 如何add机制

假如我们有一个数据(散列码76268)，而此时的HashSet有128个散列单元，那么这个数据将有可能插入到数组的第108个链表中(76268%128=108)。但这只是有可能，如果在第108号链表中发现有一个老数据与新数据equals()=true的话，这个新数据将被视为已经加入，而不再重复丢入链表。

HashSet的散列单元大小如何指定?

Java默认的散列单元大小全部都是2的幂，初始值为16（2的4次幂）。假如16条链表中的75%链接有数据的时候，则认为加载因子达到默认的0.75。HahSet开始重新散列，也就是将原来的散列结构全部抛弃，重新开辟一个散列单元大小为32（2的5次幂）的散列结果，并重新计算各个数据的存储位置。以此类推下去.....

(5) 为什么HashSet查找效率提高了。

知道了HashSet的add机制后，查找的道理一样。直接根据数据的散列码和散列表的数组大小计算除余后，就得到了所在数组的位置，然后再查找链表中是否有这个数据即可。

查找的代价也就是在链表中，但是真正一条链表中的数据很少，有的甚至没有。几乎没有什么迭代的代价可言了。所以散列表的查找效率建立在散列单元所指向的链表中的数据要少 。

总结：虽然HashSet实现的是Set接口，存储时只是存储对象，不用存储键值对，但底层还是基于HashMap的，所以为了符合HashMap的语法，所有的对象都共享一个Object对象PRESENT为值

[https_www.cnblogs.com_runwulingsheng_p_5208762.html]: https://www.cnblogs.com/runwulingsheng/p/5208762.html