高频面试八股文原理篇(二)hashSet原理相关-Toy模板网

这篇具有很好参考价值的文章主要介绍了高频面试八股文原理篇(二)hashSet原理相关。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

HashSet概述

实现原理

运行原理

HashSet中保存的对象应该如何实现

add()/remove()/contains()方法

hashset和 treeset有什么区别

HashSet概述

HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素

实现原理

基于HashMap实现的，HashSet底层使用HashMap来保存所有元素。

默认构造函数是构建一个初始容量为16，负载因子为0.75的hashmap。封装了一个hashmap 对象来存储所有的集合元素，所有放在 hashset中的集合元素实际上由 hashmap的key来保存，而 hashset中的 hashmap的 value则存储了一个PRESENT的静态object对象

相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成
因为底层是HashMap，而存储的又是key，所以没有get()方法来直接获取，只能遍历获取。

运行原理

如果算出的元素存储的位置目前没有任何元素存储，name该元素可以直接存储在该位置上；
如果算出的元素的存储位置上目前已经有了其他的元素，那么还会调用该元素的 equals方法，与该位置的元素进行比较一次，如果过equals方法返回的是true，那么该位置上的元素就会被视为重复元素，不允许被添加，如果false，则允许添加。

HashSet中保存的对象应该如何实现

对于HashSet中保存的对象，请注意正确重写其equals和hashCode方法，以保证放入的对象的唯一性

往HashSet添加元素的时候，HashSet会先调用元素的HashCode方法得到元素的哈希值，然后通过元素的哈希值经过异或移位等运算，就可以算出该元素在哈希表中的存储位置。

add()/remove()/contains()方法

可以看到这三个方法都是直接调用的HashMap的实现：

public boolean add(E e) {
     return map.put(e, PRESENT)==null;
 }

 public boolean remove(Object o) {
     return map.remove(o)==PRESENT;
 }

 public boolean contains(Object o) {
     return map.containsKey(o);
 }