Set

<aside> 🌆

설명

• 유일한 요소들의 컬렉션
• 유일성
  • 셋에는 중복된 요소가 존재하지 않음
• 순서 미보장
  • 대부분 셋 구현에서는 요소의 순서를 보장하지 않음
  • 출력과 입력 순서 다를 수 있음
• 빠른 검색
  • 셋은 요소의 유무를 빠르게 확인하는데 최적화, 이는 중복 방지하고 바른 조회를 가능하게 해줌 </aside>

예제

<aside> 🥋

package collection.set;

import java.util.Arrays;

public class MyHashSetV0 {

    private int[] elementData = new int[10];
    private int size = 0;

    public boolean add(int value) {
        if (contains(value)) {
            return false;
        }
        elementData[size] = value;
        size++;
        return true;
    }

    public boolean contains(int value) {
        for (int data : elementData) {
            if (data == value) {
                return true;
            }
        }
        return false;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV0{" +
                "elementData=" + Arrays.toString(elementData) +
                ", size=" + size +
                '}';
    }
}
-------------------------------
package collection.set;

public class MyHashSetV0Main {

    public static void main(String[] args) {
        MyHashSetV0 set = new MyHashSetV0();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        System.out.println(set);

        boolean result = set.add(4);
        System.out.println("중복 데이터 저장 결과 : " + result);
        System.out.println(set);

        System.out.println(set.contains(3));
        System.out.println(set.contains(99));
    }
}

출력
MyHashSetV0{elementData=[1, 2, 3, 4, 0, 0, 0, 0, 0, 0], size=4}
중복 데이터 저장 결과 : false
MyHashSetV0{elementData=[1, 2, 3, 4, 0, 0, 0, 0, 0, 0], size=4}
true
false

• 해당 셋 코드는 검색 모두 O(n)으로 성능이 좋지 않음
• 이러한 코드 앞 페이지에서 개선 시작 </aside>