Java Collection - 세트(Set) 구현해보기

Set 구현에는 간단하다. 인덱스가 없으므로 단순히 데이터를 넣고, 유무를 확인하고, 삭제 정도가 있다. 조건으로 데이터가 들어온 경우 기본 데이터가 있는지만 확인한다.

HashSet.class

import java.util.Arrays;

public class HashSet {
    private int[] elementData = new int[10];
    private int size = 0;

    public boolean add(int value) {
        // O(n) 속도
        if (contains(value)) {
            return false;
        }

        elementData[size] = value;
        size++;
        return true;
    }

    private boolean contains(int value) {
        // O(n) 속도
        for (int data : elementData) {
            if (data == value) {
                return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "HashSet{" +
                "elementData=" + Arrays.toString(Arrays.copyOf(elementData, size)) +
                ", size=" + size +
                '}';
    }
}

HashSet - add 메소드

• add 메소드는 요소에 데이터를 보관한다.
• 보관할 데이터 중 중복된 데이터가 있는 경우 무시하나. 테스트로 구성하였으므로 contains 메소드로 값이 존재하는지 확인한다.

HashSet - contains 메소드

• contains 메소드는 주로 요소를 보관하는 ElementData 에서 특정 값이 존재하는지 확인한다.

HashSet - Size 메소드

• 요소 보관함에 들어간 데이터를 반환한다.

다음으로 HashSet 사용한 main 메소드를 돌려본다.

Main.class

public class Main {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(5);
        System.out.println(set.size());
        System.out.println("1 값이 존재하는가? " + set.contains(1));
        System.out.println("10 값이 존재하는가? " + set.contains(10));
        System.out.println("3 값을 중복해서 입력되는가? " + set.add(3));
        System.out.println(set);
    }
}

5
1 값이 존재하는가? true
10 값이 존재하는가? false
3 값을 중복해서 입력되는가? false
HashSet{elementData=[1, 2, 3, 4, 5], size=5}

초기 Set 자료 구조는 단순하나 데이터 추가, 검색에 O(n) 으로 성능이 좋지 않을 것을 볼 수 있다. 데이터가 많을 수록 점점 효율이 감소하여 검색에서는 ArrayList, LinkedList O(n) 속도라도 받아 들일 수 있으나, 데이터 추가인 add 메소드에서 느려지는 것은 납득하기가 어렵다. 중복 데이터가 있는지 전체 데이터를 확인하는 작업이 있어야 데이터를 넣을 수 있기 떄문이다.