【集合】HashSet

HashSet

• HashSet ，基于 HashMap 的 Set 实现类。

数据结构

// HashSet 只有一个属性，那就是 map
private transient HashMap<E, Object> map;

// 因为 HashSet 没有 value 的需要，所以使用一个统一的 PRESENT 即可
private static final Object PRESENT = new Object();
           

构造方法

public HashSet() {
    map = new HashMap<>();
}
           

体现了HashSet 是基于 HashMap 的 Set 实现类

public HashSet(Collection<? extends E> c) {
    // 最小必须是 16 。
    // (int) (c.size()/.75f) + 1 避免扩容
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    // 批量添加
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    // 注意，这种情况下的构造方法，创建的是 LinkedHashMap 对象
    map = new LinkedHashMap<>(initialCapacity, loadFactor); 
}
           

添加元素

• 添加一个元素

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

• 添加多个元素

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    // 遍历 c 集合，逐个添加
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}
           

删除元素

• 删除单个元素

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

查找元素

• 查找单个元素

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

清空

public void clear() {
    map.clear();
}

           

迭代器

public Iterator<E> iterator() {
        return map.keySet().iterator();
}
           

小结

• HashSet 是基于 HashMap 的 Set 实现类
• HashSet不同步，为线程不安全的实现，如果有多个线程同时访问，并对立面的元素进行了修改，则需要在外部同步。