[Java] HashSet 개념과 저장 원리(HashMap, 해시테이블, hashcode, equals 메서드)

HashSet 이란?

Python에서 Set(집합)의 개념과 유사합니다.

중복을 허용하지 않고, 요소들의 저장 순서를 유지하지 않는 자료구조입니다.

 

HashSet 특징

• null값을 저장할 수 있습니다.
• 동기화되지 않습니다 
  • 멀티스레드 환경에서 여러 스레드가 동시에 HashSet을 수정하면 ConcurrentModificationException이 발생할 수 있습니다. 따라서 스레드 중 하나 이상이 세트를 수정하는 경우 Collections.synchronizedSet() 을 사용해서, 외부에서 동기화 해야 합니다. 
• 검색 시 O(1) 시간 복잡도가 소요되며 굉장히 성능이 좋습니다. 

 

HashSet 저장 원리 

HashSet의 검색 속도가 빠른 이유가 바로 저장 원리 때문입니다.

 

Java에서 HashSet은 내부적으로 HashMap을 사용하여 데이터를 저장합니다.

HashSet은 값을 저장하지만, 그 값은 실제로 HashMap의 키로 저장됩니다.

그리고 HashSet에서 중복 체크는 HashMap의 키를 사용하여 이루어집니다.

 

HashSet에 "딸기"라는 원소를 넣었다고하면, 어떻게 HashMap 의 키로 저장이 될까요?

바로, hashCode() 메서드를 통해 객체의 해시값을 계산합니다.

같은 해시값이 있으면, equals() 메서드를 호출하여 같은 객체인지 확인합니다.

• equals() 결과가 true면 → 같은 객체이므로 추가하지 않음.
• equals() 결과가 false면 → 해시 충돌이 발생한 다른 객체이므로 체이닝 방식으로 추가.

같은 해시값이 없다면, 해시값을 기반으로 HashTable 내 버킷(bucket)에 저장합니다.

* 체이닝: 동일한 해시 코드 값을 가지는 객체들이 연결 리스트나 트리 ( JDK 1.8부터는 Red-Black Tree )  로 연결되는 방식입니다. 즉, n번 버킷에 여러 개의 값이 저장될 수 있도록 합니다.

 

HashMap이 데이터를 저장하는 구조는 해시 테이블로, 데이터가 버킷에 저장되는 방식입니다.

예를 들어, "딸기"의 hashCode 값이 10이라면, 해당 버킷의 인덱스는 10이 됩니다. 만약 HashMap의 배열(버킷) 크기가 16이라면, 10 % 16 = 10이므로, 10번 버킷에 위치하게 됩니다.

(HashSet의 기본(초기) 버킷 수는 16라고 합니다.)

위에서 언급한 것과 같이, HashSet은 내부적으로 HashMap의 키로 값을 저장하므로, 딸기라는 값을 HashMap의 키로 저장하고, 그 값은 PRESENT라는 더미 객체로 저장됩니다. 

즉 (딸기, PRESENT) 형태로 10번 버킷에 들어가게 되는 것이죠 (같은 해시값이 없다고 가정)

 

여기서 HashSet의 초기 용량을 10으로 다음과 같이 설정할 수도 있습니다.

하지만 버킷의 수는 2의 거듭제곱으로 설정됩니다.

따라서 용량을 10으로 설정해도, 실제 버킷 수는 2의 거듭제곱인 16으로 설정이됩니다.

만약 용량을 7로 설정한다면, 실제 버킷 수는 8이 되는 것이겠죠 ㅎㅎ

HashSet<String> set = new HashSet<>(10);

---

 

💡요약

HashSet은 내부적으로 HashMap을 사용하여 원소를 키로 저장하고, 값은 더미 객체인 PRESENT로 저장됩니다. 이 때, 중복 체크는 해시값과 equals() 메서드를 통해 이루어집니다. 

 

 

 

참고자료

자바 레퍼런스

HashSet (Java Platform SE 8 )