[Java] HashSet과 LinkedHashSet 비교

우아한 프리코스 1주차 과제를 풀면서 HashSet과 LinkedHashSet의 차이에 대해 궁금해졌다.

    private Set<Integer> generateNumberSet(int numberLength) {
        LinkedHashSet<Integer> randomNumberSet = new LinkedHashSet<>();

        while (randomNumberSet.size() < numberLength) {
            int pickedNumber = Randoms.pickNumberInRange(1, 9);
            randomNumberSet.add(pickedNumber);
        }

        return randomNumberSet;
    }

generateNumberSet 메서드는 1~9 사이의 숫자를 numberLength 만큼 랜덤으로 골라 Set에 담는 역할을 한다.

    private String convertSetToString(Set<Integer> targetNumberSet) {
        StringBuilder builder = new StringBuilder();
        for (Integer number : targetNumberSet) {
            builder.append(number);
        }

        return builder.toString();
    }

convertSetToString 메서드는 Set에 있는 숫자들을 String으로 이어붙여서 String을 변환하는 역할을 한다.

여기서 처음에는 나는 LinkedHashSet이 아닌 HashSet에 숫자들을 담은 후, 문자열로 변환했다.
하지만 랜덤 숫자들을 HashSet에 담고 출력해보면 숫자들이 오름차순 정렬이 된 채로 조회가 되는 것을 보았다.
(예를 들어 랜덤 숫자가 2, 3, 1인데 문자열로 "123"이 만들어짐)

그래서 LinkedHashSet 클래스로 수정했더니 내가 원하던 대로(정렬X) 되어서 일단 LinkedHashSet 클래스로 두었다.

하지만 난 Set 컬렉션 자체가 순서가 보장되지 않는다고 알고 있다. 근데 이건 순서도 아니고 정렬이 된다고..? 엄청난 의문이 매우 들었다....

그래서 의문도 풀고 Set 컬렉션에 대해 제대로 알아갈 겸
Set 컬렉션 정리해두려고 한다. 내 의문은 확실히 풀어둬야지.

⚾️ Set

Set 은 데이터의 중복된 값이 없는 자료구조이다.
저장된 객체(데이터)를 인덱스로 관리하지 않아 저장 순서가 보장되지 않는다.

대표적인 클래스로 HashSet, LinkedHashSet, TreeSet이 있다.
HashSet은 순서를 보장하지 않는다. (HashSet이 구현 클래스들 중 가장 빠른 성능을 보인다.)
LinkedHashSet은 입력된 순서대로 데이터를 관리한다.
TreeSet은 오름차순으로 자동 정렬을 해준다.

이 블로그를 보고 내 의문점은 확실히 풀렸다!

    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(6);
        set.add(5);
        set.add(9);
        set.add(3);

        for (Integer number: set) {
            System.out.print(number); // 3569
        }
    }

이게 바로 내가 발견한 문제의 예시이다
이 클래스는 정렬을 지원하지 않는 것으로 알고 있는데 계속해서 정렬이 되어가고 있다.

하지만 여기서 10 이상의 숫자를 set 자료에 넣어보겠다.

    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(6);
        set.add(5);
        set.add(9);
        set.add(3);
        set.add(17);

        for (Integer number: set) {
            System.out.print(number); // 173569
        }
    }

반복을 해도 똑같은 결과가 출력된다.

데이터 출력 순서가 완전히 랜덤인 줄 알았지만 아니었다.
HashSet의 add 메서드를 따라가보겠다.

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

HashSet은 내부적으로 HashMap으로 구현되어 있다. Key Object에는 저장하고 싶은 객체(데이터)를 저장하고, Value Object에는 dummy data를 넣어 둔다.

HashMap을 기본적으로 선언하면 디폴트 버킷 사이즈가 16이다.

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

즉 16개의 Node<K, V>가 들어갈 수 있는 배열이 선언된 것이다.

key를 알맞은 버킷에 저장하기 위해 hashCode를 사용한다.
이 hashCode를 버킷 수로 나눈 나머지를 배열의 index로 사용한다.

HashMap의 put 메서드로 들어가보겠당!

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

HashMap의 hashCode 메서드

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

💻 코드로 이해하기

        Set<Integer> set = new HashSet<>();
        set.add(6);
        set.add(5);
        set.add(9);
        set.add(3);
        set.add(17); // 17 % 16(버킷 수) = 1
        set.add(54); // 54 % 16 = 6
        set.add(23); // 23 % 16 = 7
        set.add(67); // 67 % 16 = 3
        set.add(7);
        set.add(16); // 16 % 16 = 0
        set.add(28); // 28 % 16 = 12

        for (Integer number: set) {
            System.out.println(number); // 16 17 3 67 5 6 54 23 7 9 28 
        }

인턴하면서 피그마에 빠지게 된....
이렇게 HashSet이 정렬되는 게 아니라 첫 번째 테이블 인덱스부터 순차적으로 탐색하면서 출력하는 것이다.

로드 팩터

HashMap을 기본적으로 선언하게 되면 갖게 되는 디폴트 로드 팩터는 0.75이다.
즉 75%의 버킷이 차면 추가적으로 데이터를 저장할 공간을 확보하게 되는 것이다.
로드 팩터를 초과해 데이터가 저장되면, HashMap은 현재 버킷 개수의 2배만큼 용량을 늘린다.

데이터의 저장 순서를 기억해야 하는 경우에는 LinkedHashSet을 사용하자.
HashSet/HashMap을 쓰는 경우에는 데이터의 저장 및 출력 순서가 중요하지 않고, 데이터의 존재 유무가 중요한 경우가 되는 경우이다.

14개의 데이터를 담아서 75%의 버킷을 차게 해보았다. 2배만큼 용량을 늘려 32개의 버킷으로 확장된다.

        Set<Integer> set = new HashSet<>();
        set.add(6);
        set.add(5);
        set.add(9);
        set.add(3);

        set.add(17);
        set.add(54); // 54 % 32 = 22
        set.add(23);
        set.add(67); // 67 % 32 = 4

        set.add(7);
        set.add(16);
        set.add(28);
        set.add(90); // 90 % 32 = 24

        set.add(70); // 70 % 32 = 6
        set.add(34); // 34 % 32 = 2

        for (Integer number: set) {
            System.out.print(number + " "); // 34 3 67 5 6 70 7 9 16 17 54 23 90 28
        }

참고

• Integer의 해시 코드는 자신의 값을 반환한다.
• >>> 연산은 2진수로 변환하여 우측으로 해당 숫자만큼 시프트 한다.

😇 의문 해결

우아한 프리코스에서는 1~9 사이 랜덤 숫자 3개를 HashSet에 담으므로 항상 정렬된 상태일 수 밖에 없는 것이다.
16개 버킷에서 최대 3개의 버킷을 사용하기 때문에 버킷 수가 늘어나지도 않고, 항상 한 자리 숫자이므로 인덱스는 자신의 숫자가 될 것이니 말이다!
그러므로 이 문제에서 항상 숫자가 정렬되지 않게 하려면, LinkedHashSet 을 써서 랜덤으로 나온 숫자 순서를 저장하기 위해 LinkedHashSet을 사용하길 잘한 듯하다!

출처

• http://kwseo.github.io/2015/09/24/time-complexity-about-collections/
• https://jwdeveloper.tistory.com/278