Collection:Java集合框架-HashSet

2020-11-01

HashSet(基于JDK1.8)

HashSet

Set 接口的实现类之一
底层实现基于HashMap

依赖关系

1
2
3

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

类注解

HashSet 实现了Set接口由一个哈希表(实际上是HashMap)支持不能保证集合的迭代顺序特别是不能保证顺序随时间保持不变这个类允许null元素
HashSet 的 add remove contains size 等方法每次操作的时间是一定的不会随着数据量增大而改变即：在不考虑哈希冲突的情况下时间复杂度为O(1)
HashSet 遍历的时间与 size 和 capacity的总和成正比如果迭代性能很重要那么不要将初始容量设置的太高（或者负载系数设置的太低）
HashSet 是线程不安全的需要在外部实现同步或者使用 Collections#synchronizedSet 例子：Set s = Collections.synchronizedSet(new HashSet(…));
since：1.2

属性

// 伪值，以便与后备映射中的对象相关联
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
    
private transient HashMap<E,Object> map;
// 属性说明 见下面的 补充说明

构造器

// 无参 直接就是new HashMap的无参构造
public HashSet() {
	map = new HashMap<>();
}

// 传入Collection
public HashSet(Collection<? extends E> c) {
       // new HashMap(int initialCapacity) 
       // 默认HashMap加载因子 0.75
       // HashMap的容量 取 Collection的size / 0.75 + 1  和 16的较大值
       map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
       addAll(c);
   }

// 传入初始容量 以及Hash加载因子
   public HashSet(int initialCapacity, float loadFactor) {
       map = new HashMap<>(initialCapacity, loadFactor);
   }

// 传入初始容量 那么Hash加载因子 为默认 即 0.75
   public HashSet(int initialCapacity) {
       map = new HashMap<>(initialCapacity);
   }

// 缺省的构造器 初始化容量 加载因子 
// boolean dummy 忽略（true和false一样）主要是为了和上面的构造器区分参数
       HashSet(int initialCapacity, float loadFactor, boolean dummy) {
       map = new LinkedHashMap<>(initialCapacity, loadFactor);
   }

方法

   // 查看大小
   public int size() {
       return map.size();
   }

// 是否存在
   public boolean contains(Object o) {
       return map.containsKey(o);
   }

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

说明：

可以看出底层全部走的都是HashMap的方法所以不在这里过多说明后面HashMap的里面细说HashMap具体的方法实现

补充说明

HashSet 底层使用的是 HashMap 但是想使用只有两种方式继承或者组合 HashSet使用的就是组合方式（通过调用基础类的方法来复用基础类的能力 ~~继承的劣势自行查找这里就不过多说明~~）

HashSet 将HashMap声明为自己的局部变量以实现组合声明一个 PRESENT 代替Map中的Value 例子：上述添加方法入参只有一个E e但是Map（HashMap）却有K 和 V两个参数

Collection的size / 0.75 + 1 为什么是这和 16 比较？

如果传入的小于16 初始容量就按16来否则就按期望大小

HashMap的阈值为容量*0.75 加 1 目的是期望值比扩容大小大1 这样就不会扩容