[자바/JAVA] HashSet을 사용해서 정렬이 되는 이유 찾아보기

 

 

HashSet

HashSet은 인터페이스 Set을 구현할 때 사용하며 HashMap 인스턴스로 Set 자료구조 형식을 나타낸다.
Set은 비선형 자료구조로 순서가 보장되지 않고, 중복이 허용되지 않는 특징이 있다.
HashSet말고도 TreeSet, LinkedHashSet, SortedSet과 같은 방식을 사용하기도 한다.

 

 

순서가 보장되지 않는 Set의 성질

자바 컬렉션은 Set을 기본으로 제공한다. Set을 구현하는 방법은 여러가지가 있지만, 각자 성질이 조금씩 다르다. SortedSet과 이를 상속받은 TreeSet은 오름차순으로 정렬이 되고, HashSet을 상속받은 LinkedHashSet은 저장된 순서에 따라서 해시테이블에 저장된다.

순서 없이 나오는 Set을 보기 위해 HashSet을 통해서 동작을 확인하고 있었다. 그런데 막상 출력하니 순서대로 저장된 모습이 보였다.

 

 

---

 

 

실제 테스트 코드

실행 코드	출력 결과

실제 결과와 비교하기 위해 코드블럭이 아닌 스크린샷으로 가져왔다.

 

set에 저장은 [2, 6, 4, 11] 순서로 했고, HashSet은 해시함수를 통해 해시테이블에 저장된다.
순서를 보장하지 않아 출력 형태도 값이 랜덤으로 나올 거라고 생각했다.

하지만 출력 결과는 예쁜 오름차순 형태였다.

 

 

 

값의 크기에 따라 오름차순으로 정렬되는 TreeSet과 비교해보았다.

	실행 코드	출력 결과
HashSet
TreeSet

 

처음과 동일한 형태로 순서대로 정렬된 것을 볼 수 있다.
값에 따라 오름차순 정렬되는 TreeSet과 비교하니, 순서가 보장되지 않는다는 HashSet이 특징이 더 드러나지 않았다.

 

너무 작은 값을 넣어서 우연이 맞았나? 싶어서 더 큰 값을 넣어주었다.

 

 

실행 코드	출력 결과

 

중복된 값은 저장하지 않는 Set의 성질이라도 보고 싶어서 이번엔 중복값을 넣어보았다.
그리고 전보다 더 큰 값을 삽입하고 결과를 출력했다.

 

눈치를 챘다면 이번에도 정렬이 된 모습을 볼 수 있다.

중복된 마지막 값(27)은 제외하고, 나머지 값들이 저장한 순서대로 정렬되어 있는 것

 

저장한 순서에 따라 정렬되는 건 HashSet을 상속받는 LinkedHashSet의 성질이었다. 이건 LinkedHashSet이 아닌데.. 값의 크기에 따라 정렬되지는 않았지만, 값을 저장한 순서에 따라 정렬이 되고 있다.

 

 

순서를 보장하지 않는다. → 해시 함수에 따라서 순서대로 저장 될 수도 있다.

 

 

우연이 이렇게 여러번 겹칠 수 있을까..?

 

 

실행 코드	출력 결과

 

맨 처음에 의도했던 순서가 보장되지 않고, 중복이 허용되지 않는 Set의 형태를 이루고 있다.

실행을 하는 것과는 별개로 들어가는 값의 크기에 따라서 해시 테이블에 저장되는 순서가 달라지는 것 같았다.

 

마지막 테스트를 하고 난 뒤에 HashSet 코드를 살펴보았다.

 

 

---

 

Hashing

해시테이블은 자료구조의 하나로 key를 통해 value를 가져온다.

파이썬의 Dictionary, 자바의 Map이 (key, value) 형태로 되어 있고, JSON을 사용할 때도 (key, value) 구조로 사용한다. 개념 자체는 여러 곳에서 사용하는 만큼 단순한 구조이다. 여기에 해시함수 라는 개념이 추가된다.

 

해시함수를 통해 산술적인 연산을 적용하고, 그 결과값으로 테이블 주소에 접근한다. 보통 곱하거나 나머지를 구하거나, 무작위로 선택하는 방법 등 여러가지가 있다. 외부로부터 테이블을 보호하기 위해 암호화를 통해 해시함수를 구현하기도 한다.

HashSet은 이런 Hash구조의 Map형태로 구현된다. 

 

 

생성자 HashSet ( Collection <? extends E> c)

매개변수로 Collection타입을 받을 때 Hashset의 생성자는 아래와 같다.

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

HashSet의 내부는 HashMap으로 구현된다.
여기서 초기 용량을 계산하고 있는 것이 보인다.

 

Math.max(..., 16)

앞의 (c.size ... )는 저장 용량을 계산하고 있고, 그 뒤에 16이라고 적힌 수가 초기 용량을 의미한다.
16보다 작으면 기본 용량은 16을 사용하고, 이 크기를 넘게 되면 resizing을 통해 용량을 늘린다.

 

용량을 늘리는 구조도 보고싶어 HashMap코드를 보았는데, HashSet보다 HashMap이 더 복잡해서 포기했다!!

처음 궁금했던 건 "왜 순서대로 저장이 되지?" 였기 때문에 위 초기 용량이 16이라는 점으로 궁금증 해소에 도움이 됐다.

 

제일 처음에 테스트했던 코드를 가져와 다시 살펴보자.

 

 

---

 

 

HashSet 확인 후 재 테스트

실행 코드	출력 결과

 

처음에 테스트했던 최대값이 12인 작은 수를 삽입하는 코드.

 

중복된 값을 넣어주어도 다시 실행해도 예쁜 오름차순 형태로 출력되었다.
초기 용량이 16으로 정해져있으면, 16을 뛰어넘는 수가 들어가면 어디에 저장이 될까?

 

 

	실행 코드	출력 결과
add(18)
add(20)

 

add(18) → [1]에 저장

16보다 큰 수, 18을 넣었더니 1번 인덱스에 위치했다.
16이 마지막이고, 16의 다음 수인 17은 1번과 인덱스가 겹쳐 다음 공간으로 넘어간다. 

18을 넣으면 2와 인덱스가 겹쳐 2가 들어갈 자리 = 1의 다음 인덱스로 들어갔다.

 

[1, 4, 8, 12]에서 두번째로 작은 4와 동일한 인덱스로 위치하게 하려면 16+4=20
예상이 맞다면 4의 다음 인덱스에 자리해야 한다.

 

 

add(20) → [2]에 저장

기존 4의 자리였던 [1]의 다음에 20이 저장된 걸 볼 수 있다.
기본으로 정의한 용량에서 벗어나면 차이를 계산하여 알맞은 인덱스에 위치한다.
그리고 그 인덱스 값을 가져오게 된다.

 

 

# 두번째 테스트 코드

실행 코드	출력 결과

두번째로 테스트했던 코드를 가져왔다.
여기서 저장한 순서로 예쁘게 출력 되는 건 그냥 숫자를 넣은 순서가 우연이었던걸까..?

위에서 추측한대로 16을 기준으로 [50, 27, 12, 95] 를 계산해보았다.
16으로 나눈 나머지를 구하니 그 인덱스는 [50:2, 27:11, 12:12, 95:15] → [2, 11, 12, 15]

우연의 일치로 테스트하기 위해 무작위로 작성했던 숫자들이 해시함수 결과 순서에 잘 맞았다.
순서에 따라 정렬되는 모습은 그저 우연이었다.

 

 

 

새로운 테스트

 

추측

HashSet의 기본 용량은 16이고, 16을 벗어나면 16으로 나눈 나머지를 사용한다.
만약 값이 중복되면 더 작은 숫자 뒤로 밀리거나, 입력한 순서대로 밀릴 것이다.

 

 

기대

직접 계산한 삽입될 값과 예상 인덱스 [50, 43, 12, 91, 27] → [2, 11, 12, 11, 11]

중복되는 11을 가지는 [43, 91, 27]은 체이닝이나 개방주소법을 활용해 다른 곳에 저장될 것이다.
계속 작성하던 코드에 따르면, 테이블에 다른 데이터가 들어가있으면 그 다음으로 넘어가는듯 했다.

 

바로 다음 인덱스로 차례차례 넘어가는게 맞다면 [50, 43, 91, 27, 12]로 출력되지 않을까?

 

 

결과

실행 코드	출력 결과

 

 

 

---

 

 

후기

어제는 하루종일 개념 공부를 해서 오늘 프로젝트 과제를 하느라 시간 가는 줄 몰랐다.
강의 과제와 프로젝트를 하다보니 개인공부를 못해서 자바 Set이라도 사용해보려고 했고, 덕분에 새로운 정보 발견

너무너무 재밌다..!