【集合】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不同步，為線程不安全的實作，如果有多個線程同時通路，并對立面的元素進行了修改，則需要在外部同步。