Collection살펴보기 - Set

컬랙션의 구현체로는 크게 4가지가 있다. 이 중 용도가 다른 EnumSet을 논외로 하고 HashSet과 LinkedHashSet, TreeSet을 중심으로 성능을 비교해보자.

 

성능 측정을 위한 클래스

시간 단위는 밀리세컨드를 기준으로 삼고 더 정밀한 측정이 필요할 수 있으니 나노 세컨드로 반환하는 메서드도 구현했다. 구현 코드를 보자.

 

public class Timer {
    public static long checkNanoTime(CodeBlock codeBlock) {
        long startTime = System.nanoTime();
        codeBlock.doSomething();
        long endTime = System.nanoTime();
        return (endTime - startTime);
    }

    public static long checkMilliTime(CodeBlock codeBlock) {
        return checkNanoTime(codeBlock) / 1_000_000L;
    }
}

 

CodeBlock은 실제로 동작하는 메서드를 전달하는 함수형 인터페이스이다. 기본으로 제공되는 함수형 인터페이스 중엔 파라미터와 반환 타입이 없는 메서드 시그니처가 없어 직접 구현했다.(해당 메서드가 함수라고 할 순 없지만 이런 기능이 필요하니 그냥 넘어가자)

 

@FunctionalInterface
public interface CodeBlock {
    void doSomething();
}

 

이제 성능 측정을 위한 테스트 준비는 끝났다. 

 

삽입 / 조회 / 삭제의 성능 비교

HashSet / LinkedHashSet / TreeSet 별 데이터 삽입, 조회, 삭제를 할 수 있는 클래스 SetBehavior를 구현했다.

 

public class SetBehavior {
    private final static Set<Integer> hashSet = new HashSet<>();
    private final static Set<Integer> linkedHashSet = new LinkedHashSet<>();
    private final static Set<Integer> treeSet = new TreeSet<>();
    
    public static void addInHashSet(final int size) {
        IntStream.range(0, size)
                .forEach(hashSet::add);
    }
    public static void addInLinkedHashSet(final int size) {
        IntStream.range(0, size)
                .forEach(linkedHashSet::add);
    }
    public static void addInTreeSet(final int size) {
        IntStream.range(0, size)
                .forEach(treeSet::add);
    }

    public static void getAllInHashSet() {
        hashSet.forEach(hashSet::contains);
    }
    public static void getAllInLinkedHashSet() {
        linkedHashSet.forEach(linkedHashSet::contains);
    }
    public static void getAllInTreeSet() {
        treeSet.forEach(treeSet::contains);
    }

    public static void removeAllInHashSet() {
        hashSet.removeIf(value -> value > 0);
    }
    public static void removeAllInLinkedHashSet() {
        linkedHashSet.removeIf(value -> value > 0);
    }
    public static void removeAllInTreeSet() {
        treeSet.removeIf(value -> value > 0);
    }
}

 

복잡한 내용은 없으니 바로 테스트 코드를 살펴보겠다. 마지막 코드이니 조금만 참아주길 바란다.

 

@DisplayName(value = "Set 인터페이스 속도 테스트")
public class SetBehaviorTest {
    private final int SIZE = 10_000_000;

    @Test
    @DisplayName("HashSet의 속도 테스트 (삽입/조회/삭제)")
    public void checkTimeToHashSet() {
        long addDataTime = Timer.checkMilliTime(() -> SetBehavior.addInHashSet(SIZE));
        System.out.println("add data in HashSet : " + addDataTime);

        long getDataTime = Timer.checkMilliTime(SetBehavior::getAllInHashSet);
        System.out.println("get all data in HashSet : " + getDataTime);

        long removeTime = Timer.checkMilliTime(SetBehavior::removeAllInHashSet);
        System.out.println("remove all data in HashSet : " + removeTime);
    }

    @Test
    @DisplayName(value = "LinkedHashSet의 속도 테스트 (삽입/조회/삭제)")
    public void checkTimeToLinkedHashSet() {
        long addDataTime = Timer.checkMilliTime(() -> SetBehavior.addInLinkedHashSet(SIZE));
        System.out.println("add data in LinkedHashSet : " + addDataTime);

        long getDataTime = Timer.checkMilliTime(SetBehavior::getAllInLinkedHashSet);
        System.out.println("get all data in LinkedHashSet : " + getDataTime);

        long removeTime = Timer.checkMilliTime(SetBehavior::removeAllInLinkedHashSet);
        System.out.println("remove all data in LinkedHashSet : " + removeTime);
    }

    @Test
    @DisplayName(value = "TreeSet의 속도 테스트 (삽입/조회/삭제)")
    public void checkTimeToTreeSet() {
        long addDataTime = Timer.checkMilliTime(() -> SetBehavior.addInTreeSet(SIZE));
        System.out.println("add data in TreeSet : " + addDataTime);

        long getDataTime = Timer.checkMilliTime(SetBehavior::getAllInTreeSet);
        System.out.println("get all data in TreeSet : " + getDataTime);

        long removeTime = Timer.checkMilliTime(SetBehavior::removeAllInTreeSet);
        System.out.println("remove all data in TreeSet : " + removeTime);
    }
}

 

드디어 테스트를 위한 준비가 끝났다. 기준 데이터는 1000만으로 잡았고, 데이터 생성, 조회, 삭제 순으로 진행했다. 

 

(단위 : ms)

	삽입	조회	삭제
HashSet	5027	220	366
LinkedHashSet	3738	112	195
TreeSet	7435	1163	420

 

수행 결과

데이터 삽입 속도 :: LinkedHashSet < HashSet < TreeSet

데이터 조회 속도 :: LinkedHashSet < HashSet < TreeSet

데이터 삭제 속도 :: LinkedHashSet < HashSet < TreeSet

 

 

TreeSet은 저장하면서 정렬하기 때문에 어떤 동작에서도 느리다. 대신 정렬이 필요한 경우 사용하면 중복이 제거된 List처럼 사용할 수 있다. List는 데이터 조회가 느리니 조회가 자주 발생하면서 중복된 데이터가 불필요하면 TreeSet의 사용을 고민해보자.

 

추가로 Set은 내부 자료구조로 Map을 사용한다. HashSet은 HashMap, LinkedHashSet은 LinkedHashMap, TreeSet은 TreeMap이다. 그래서 데이터를 저장하는 시점에 중복된 데이터를 제거하는 로직 외 기본적인 특성은 Map 구현체를 따른다.

 

마치며

처음 테스트를 진행할 때, Set<Integer> 대신 Set<String>으로 진행했다. 그런데  TreeSet이 다른 구현체 보다 데이터 삽입이 계속 빠른 결과가 나왔다. 왜 그럴까 생각했는데 "String 인터닝" 때문이라고 문득 생각이 들었다. 그래서 Integer로 변경하였고, 예측했던 성능 측정값을 뽑아낼 수 있었다. 

알고 있지만 놓치는 부분을 발견하거나 이유를 모르다 아는 지식으로 해결하면 꽤 기분이 좋은 일인 것 같다.

 

상황에 맞는 Set의 구현체를 선택하는 사소한 습관이 큰 장애를 막는다는 것을 생각하며 포스팅을 마무리하겠다.