JAVA集合系列——HashSet实现原理

文章目录

1. 1. HashSet实现原理
   1. 1.1. 特点
   2. 1.2. 数据结构和初始化
   3. 1.3. HashSet存取实现
      1. 1.3.1. 存储
      2. 1.3.2. 删除
      3. 1.3.3. 其他
   4. 1.4. 相关

HashSet实现原理

特点

1. 基于HashMap实现
2. 无序
3. 允许null值
4. 元素不重复
5. 非线程安全

数据结构和初始化

HashSet底层是基于HashMap实现的，它的所有数据都存放到HashMap中，更准确的说应该的HashMap的key中，所以无法保证有序，但保证元素的唯一性(HashMap的key是唯一的，本质还是通过key对象的equals和hashCode方法实现的)，而HashMap的value值则直接赋值PRESENT常量。

//基于HashMap
private transient HashMap<E,Object> map;
//常量PRESENT，用于设值HashMap的value
private static final Object PRESENT = new Object();
//默认构造，初始化了HashMap,HashMap默认的加载因子为0.75
public HashSet() {
 map = new HashMap<E,Object>();
}
//指定初始容量
public HashSet(int initialCapacity) {
 map = new HashMap<E,Object>(initialCapacity);
}
//指定初始的容量和加载因子
public HashSet(int initialCapacity, float loadFactor) {
 map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
//指定初始集合
public HashSet(Collection<? extends E> c) {
	map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
	addAll(c);
}
//指定初始容量和加载因子，实例下一个LinkedHashMap
//这个构造方法是包访问权限，是为LinkedHashSet提供的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
	map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

HashSet存取实现

存储

//底层通过hashMap的put方法实现，如果以e对象为Key的元素在HashMap中不存在的
//时候，add方法返回True,如果存在的话，HashMap的put方法会把PRESENT覆盖原来的旧值
//并返回旧值，这样add返回False
public boolean add(E e) {
 return map.put(e, PRESENT)==null;
}

删除

//底层通过HashMap的remove方法实现，HashMap的remove返回值为PRESENT表示remove成功
public boolean remove(Object o) {
 return map.remove(o)==PRESENT;
}

其他

//使用HashMap的keySet迭代返回
public Iterator<E> iterator() {
 return map.keySet().iterator();
}
//返回元素的个数
public int size() {
 return map.size();
}
//是否包含元素
public boolean contains(Object o) {
 return map.containsKey(o);
}

相关

HashSet通过HashMap来实现数据的存取，所以很好的了解HashMap的实现原理对你了解HashSet会非常有帮助,具体可以参考HashMap实现原理