Java Collection - Set

Set

一種不允許重複元素的集合

特性

唯一性：

Set 集合不允許重複的元素。

無序性：

大多數 Set 實現不保證元素的順序。但 LinkedHashSet 例外，它按照元素插入的順序保存元素。

null 值：

大多數 Set 實現允許集合中有一個 null 元素（TreeSet 除外）。

主要方法

• add(E e)：將指定元素添加到集合中，如果該元素已存在則不添加。
• remove(Object o)：從集合中移除指定元素。
• contains(Object o)：檢查集合是否包含指定元素。
• size()：返回集合中的元素數量。
• isEmpty()：檢查集合是否為空。
• iterator()：返回一個用於遍歷集合的迭代器。

實現

print 出來的結果放在 https://github.com/shengshengyang/java-for-practice/blob/master/src/Collection/Set/ShowSet.java

HashSet

特性

• HashSet 是基於哈希表的 Set 接口實現。
• 它不保證集合的迭代順序；特別是它不保證該順序恆久不變。
• 允許使用 null 元素。
• 比較高效的查找和插入性能。

LinkedHashSet

特性

• LinkedHashSet 是 HashSet 的一個子類，維護著一個運行於所有條目的雙重鏈接列表。
• 保留了元素的插入順序。
• 略微低於 HashSet 的查找和插入效率，但在迭代訪問整個集合時有更好的性能。

TreeSet

特性

• TreeSet 是基於紅黑樹（Red-Black tree）的 NavigableSet 實現。
• 元素按升序排序。
• 提供了許多有關排序的操作，如 first(), last(), headSet(), tailSet(), 等等。
• 不允許 null 元素。
• 插入和查找的效率低於 HashSet。

比較

特性	HashSet	LinkedHashSet	TreeSet
底層數據結構	哈希表	鏈接哈希表	紅黑樹
排序	無序	插入順序	自然排序或自定義排序
null 元素	允許	允許	不允許
性能（查找、插入）	高	略低於 HashSet	低於 HashSet
迭代順序	不固定	插入順序	排序順序
適用情景	需快速查找，無序	保持插入順序	有序集合、範圍查詢

自行實作

https://github.com/shengshengyang/java-for-practice/blob/master/src/Collection/Set/SimpleSet.java

import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

public class SimpleSet<E> implements Set<E> {
    private Object[] elements;
    private int size = 0;

    public SimpleSet() {
        elements = new Object[10];  // 初始容量設為 10
    }

    @Override
    public boolean add(E e) {
        if (!contains(e)) {
            if (size == elements.length) {
                increaseCapacity();  // 如果陣列滿了，增加容量
            }
            elements[size++] = e;
            return true;
        }
        return false;
    }

    private void increaseCapacity() {
        Object[] newElements = new Object[elements.length * 2];
        System.arraycopy(elements, 0, newElements, 0, elements.length);
        elements = newElements;
    }

    @Override
    public boolean contains(Object o) {
        for (int i = 0; i < size; i++) {
            if (elements[i].equals(o)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int currentIndex = 0;

            @Override
            public boolean hasNext() {
                return currentIndex < size;
            }

            @Override
            public E next() {
                return (E) elements[currentIndex++];
            }
            
        };
    }
}