HashSet 은 중복을 허용하지 않고 순서를 보장하지 않는다는 것은 많은 이들이 알고 있을 것이다.
그러면 어떠한 이유로 인해 순서를 보장하지 않을까? 라고 접근해봤을때 아주 잘 정리된 포스팅이 있어 여기를 참고하면 좋다.(✨정독 강추✨)
짧게 요약하면 다음과 같다.
HashSet 은 내부적으로 HashMap 으로 구현되어 있다.
Key Object에 저장하고 싶은 객체를 저장하고, Value Object에는 dummy data를 넣어 둔다.
Map의 Key 는 고유해야하기 때문에 중복을 허용하지 않는 것이다.
그러면 어떻게 객체를 고유하게 식별하여 관리할 수 있을까? 바로 객체의 고유한 값을 정수로 표현하는 hashCode 를 사용한다.(Object 클래스에 정의되어 있는 hashCode 메서드는 기본적으로 객체의 메모리 번지를 이용해서 정수값을 리턴한다.)
HashMap/HashSet은 데이터 접근에 O(1) 시간 복잡도를 보장하는 자료구조인데 보통 O(1)의 경우는 index 를 확실히 알고 있는 배열에 접근할 때다.
출처: https://joel-dev.site/74
Map 은 기본적으로 버킷을 사용한다. HashMap을 기본적으로 선언하게 되면, 디폴트 버킷 사이즈가 16으로 지정 되는데 위에서 표현되는 배열의 크기라 생각하면 된다.
이때 hashCode를 버킷 수(디폴트 16)로 나눈 나머지를 배열의 index로 사용하여 저장하는 것이다.
예를 들어, 아래 예제 이미지를 참고했을때
출처: https://joel-dev.site/74
"11"의 해시 코드는 1568인데, 이를 버킷수 16으로 나누면 0이라서 배열에 가장 앞에 저장되는 것이다. “1”, “2”, “3” 또한 해시 코드가 49, 50, 51인데 이를 16으로 나누면 1, 2, 3이 되어 배열의 1, 2, 3 번 인덱스에 저장되게 된다.
추가적으로 해시 알고리즘과 관련해선 여기를 참고하면 좋다.