HashSet

Hory
Java Collection
Page content

简介

HashSet 是由 HashMap 作为底层数据结构实现的一种数据结构。在学习 HashSet 之前建议先了解 HashMap 的实现原理，否则直接看 HashSet 是很难看懂的。

HashSet 是一个由 HashMap 实现的集合，特点是元素无序且不能重复。

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

和前面介绍的大多数集合一样，HashSet 也实现了 Cloneable 接口和 Serializable 接口，分别用来支持克隆以及支持序列化。还实现了 Set 接口，该接口定义了 Set 集合类型的一套规范。

字段属性

1// HashSet集合中的内容是通过 HashMap 数据结构来存储的
2private transient HashMap<E,Object> map;
3
4// 向HashSet中添加数据，数据在上面的 map 结构是作为 key 存在的，而value统一都是 PRESENT
5private static final Object PRESENT = new Object();
  • 第一个定义一个 HashMap，作为实现 HashSet 的数据结构；
  • 第二个 PRESENT 对象，前面讲过 HashMap 是作为键值对 key-value 进行存储的，而 HashSet 不是键值对，那么选择 HashMap 作为实现，其原理就是将存储在 HashSet 中的数据作为 Map 的 key，而 Map 的 value 统一为 PRESENT（下面介绍具体实现时会了解）。

构造函数

  1. 无参构造函数
1public HashSet() {
2    map = new HashMap<>();
3}

采用无参的 HashMap 构造函数，默认初始容量16和装载因子0.75。

  1. 指定初始容量
1public HashSet(int initialCapacity) {
2    map = new HashMap<>(initialCapacity);
3}
  1. 指定初始容量和装载因子
1public HashSet(int initialCapacity, float loadFactor) {
2    map = new HashMap<>(initialCapacity, loadFactor);
3}
  1. 构造包含指定集合中的元素
1public HashSet(Collection<? extends E> c) {
2    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
3    addAll(c);
4}

添加元素

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

通过 map.put() 方法来添加元素，在 map 中如果新插入的 key 不存在，则返回null，如果新插入的 key 存在，则返回原 key 对应的 value 值（注意新插入的value会覆盖原value值）。

也就是说 HashSet 的 add(E e) 方法，会将 e 作为 key，PRESENT 作为 value 插入到 map 集合中，如果 e 不存在，则插入成功返回 true;如果存在，则返回false。

删除元素

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

调用 HashMap 的 remove(Object o) 方法，该方法会首先查找 map 集合中是否存在 o ，如果存在则删除，并返回该值，如果不存在则返回 null。

也就是说 HashSet 的 remove(Object o) 方法，删除成功返回 true，删除的元素不存在会返回 false。

查找元素

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

调用 HashMap 的 containsKey(Object o) 方法，找到了返回 true，找不到返回 false。

遍历元素

同样有一般for循环和迭代器遍历

 1HashSet<Integer> set = new HashSet<>();
 2set.add(1);
 3set.add(2);
 4
 5for(Integer i : set){
 6    System.out.println(i);
 7}
 8
 9Iterator<Integer> iterator = set.iterator();
10while (iterator.hasNext()){
11    System.out.println(iterator.next());
12}