숫자 중복을 체크하며 발견한 오류

숫자 중복 문제를 어떻게 구현할까 고민하다가 중복을 허용하지 않는 자료형인 Set 이 떠올랐다.

정렬은 하지 않을 것이기 때문에 HashSet을 선택하고 구현했다.

테스트로 123, 456 489 등을 넣었다. 결과 값이 잘 나왔다.

다음으로 986을 넣었더니 689로 출력되었다 뭐지? 하고 찾아보니 HashSet은 순서를 보장하지 않는다는 단점을 발견했다.

이 부분은 LinkedHashSet로 해결했다. 이 참에 Set에 대해 깊게 알아보자.

---

HashSet은 왜 순서를 보장하지 않을까?

내부를 살펴보니 내부가 HashMap 으로 구현 되어 있다. 위에서 언급했듯 HashMap, HashSet 은 순서를 보장하지 않는다는 특징이 있다.

그럼 랜덤으로 결과가 나오나???

직접 찍어보니 매번 똑같이 689 로 나왔다. 결과를 보고 아래와 같이 의문이 생겼다.

• 왜 정렬된 상태로 나오지?
• 왜 랜덤이 아니라 계속 일정한 값 이 나오지?

hashMap은 Key기반으로 데이터를 저장하기 때문에 key 값이 고유해야하니까 

hashCode 값이 작은 값 순서로 저장해서 결과 값이 이렇게 나오나??? 유추해봤다.

HashCode 출력

유추가 틀렸다.. 11의 해시코드가 제일 큰데 첫번째로 저장되어 출력되었다. 무슨 문제인걸까 더 깊게 들어가본다.

HashMap 내부 구조는 배열이었다.

연산 시간을 O(1) 으로 보장하기 위해서 배열에 인덱스에 바로 접근하는 방법이 구현되어 있었다.

배열의 초기 크기는 16이라고한다. 이제 여기서 해싱 방법에 대해 떠올려본다..

내부 메서드 로직을 보자

add -> put -> hash 까지 가니 16으로 계산을 하는 것을 발견했다.

HashTable 적재 방법은 해시코드 % 테이블 크기 = 나머지를 인덱스 주소로 활용하는 것이다.

현재 배열의 초기 크기는 16이니까 나눠서 나머지를 실제 인덱스랑 비교해보자.

순서와 인덱싱 번호가 일치한다.. !! 이거였어 ㅠㅠㅠㅠㅠㅠ 찾았다 찾았어...

왜 입력한 순서대로 저장이 안되는지 파악했다. 이제 순서대로 저장해보자!!!

해결 방법(HashSet -> LinkedHashSet)

위에 적은 그대로 LinkedHashSet 으로 변경해서 사용해주면 된다.

왜냐하면 LinkedList는 노드를 이중으로 연결해 저장하기 때문에 순서가 보장된다.

느낀점

깊게 파고들다보니 시간이 훌쩍 지났다. 자료구조 사용을 위한 메서드가 어떤 것이 있는지는 알았지만, 

내부 동작에 대해서는 잘 몰랐다. 앞으로 자료구조를 사용할 때 내부를 살펴보고 원리를 이해하고 사용하는게 좋을 것 같다.

ps. 글쓰는 방법을 익히는 중이라 글 정리가 잘 안되어 있습니다. (피드백은 언제나 환영입니다!) 

참고

• 자바 비트연산자

• Set Collection 비교

• 해쉬 테이블 저장 방법

• 자바 공식 문서 HashSet