HashSet은 내부적으로 HashMap을 사용하고, HashMap은 다시 “버킷 배열(배열) + 각 버킷에서의 연결 리스트 혹은 트리(레드-블랙 트리)”로 구성됩니다.
1. Hashing(해싱)과 해시 함수
1) 해싱의 목적
특정 키(Key)를 해시 함수에 넣어, 그 결과(해시 값)를 인덱스로 삼아 요소를 저장합니다. 이로 인해 평균 O(1)에 가까운 접근이 가능해집니다.
2) 해시 함수
객체(또는 값) -> 정수로 매핑하는 함수입니다. HashSet은 이 값을 바탕으로 객체가 들어갈 자리(버킷bucket)를 결정합니다.
2. 내부 자료 구조
1) 배열(Array) + 연결 리스트(또는 트리 구조)
내부적으로는 해시 버킷(버킷 배열)을 가지고 있습니다. 중복되는 해시 값이 나오는 경우 하나의 버킷에 여러 요소를 담을 수 있도록 버킷 하나하나는 연결 리스트(Linked List)나 트리(Tree) 형태로 관리됩니다.
- Java 8 이후에는 해시 충돌이 잦아지는 경우 연결 리스트가 레드-블랙 트리로 변환되어 탐색 성능을 개선하기도 합니다.
2) HashSet vs HashMap
Java의 HashSet은 사실상 내부에서 HashMap을 활용합니다. HashSet에 값을 추가하면 내부적으로 HashMap의 key로 사용됩니다(Value는 dummy 값).
3. 삽입(put/add) 과정
HashSet에 원소를 추가한다는 것은 내부적으로 HashMap.put(key, dummyValue)를 호출하는 것과 같습니다.
Java HashMap의 put 동작을 예시로 설명해보면 다음과 같은 단계를 거칩니다.
1. hashCode() 호출 및 해시 값 생성
- 새로 추가하려는 객체의
hashCode()를 호출합니다. - 이 해시코드(hashCode)는 Java HashMap에서 추가로 “고유한 해싱 로직”(고차 해싱, hash 스크램블 등)을 거쳐 최종 해시 값(정수)으로 변환됩니다.
2. 버킷 인덱스 계산
- 해시 값과 버킷 배열의 크기를 바탕으로, 객체가 들어갈 배열 인덱스를 계산합니다.
- 예)
index = (hash & (table.length - 1))(비트 연산 형태) - 기존에는
index = hash % table.length와 유사한 효과지만, 비트 마스크 연산으로 최적화된 형태를 취합니다.
3. 해당 버킷 탐색 및 연결 리스트/트리 확인
- 해당 인덱스 위치에 아무것도 없는 경우(노드 없음)라면 새 노드를 생성하여 바로 삽입합니다.
- 이미 노드가 존재(충돌)한다면, 연결 리스트나 트리 형태로 구성된 노드들을 순회합니다.
- equals() 검사를 통해 동일 객체가 이미 들어있는지 확인합니다.
- 만약 동등 객체(= 같은 HashSet의 요소)가 있으면 삽입을 무시합니다(중복 불가).
- 없으면 새 노드를 연결 리스트 또는 트리에 추가합니다.
4. 트리화(Treeify) 혹은 해시 충돌 처리
- Java 8부터 버킷 내 충돌(= 같은 인덱스에 여러 노드)이 많아지는 경우, 연결 리스트가 레드-블랙 트리로 변환될 수 있습니다.
- 기본적으로 버킷에 8개 이상의 노드가 쌓이면 트리화 과정을 시도합니다.
- 단, 배열 크기가 작으면(기본적으로 64 미만 등) 먼저 리사이징을 하도록 유도한 뒤 트리화를 늦추는 식으로 동작합니다.
5. 리사이징(Resize) 검사
- 원소 삽입 후, 전체 원소 수가
capacity * loadFactor를 초과하면 버킷 배열 크기를 두 배로 늘립니다. - 예: 기본
loadFactor는 0.75, 기본 capacity는 16 → 12개를 초과하면 리사이징 발생 - 리사이징이 일어나면 기존 노드를 새 배열로 옮기는
rehash과정(인덱스 재계산)이 진행됩니다.
6. 결과
- 최종적으로 HashMap에 해당 key가 정상 삽입되면, HashSet에 대해서도 add가 성공한 것으로 간주됩니다.
정리하자면, HashSet의 add는 내부적으로 해시 값 → 버킷 찾기 → 해당 버킷 노드들 확인(equals) → 새 노드 삽입 → 필요 시 트리화, 리사이징 과정을 거칩니다.
충돌 처리 예시. Open Addressing과 Seperate Chaining형식이 있다.
4. 검색(contains) 과정
HashSet에 원소가 존재하는지 확인하는 과정은 내부적으로 HashMap.containsKey(key)와 동일합니다.
1. hashCode() 호출 및 해시 값 생성
- 검색 대상 객체의
hashCode()를 구하고, HashMap의 해싱 로직에 따라 최종 해시 값을 결정합니다.
2. 버킷 인덱스 계산
index = (hash & (table.length - 1))형태로 버킷 위치를 알아냅니다.
3. 노드 검색
- 버킷(인덱스 위치)에 연결된 연결 리스트 또는 트리를 탐색합니다.
- 각 노드의 키(= HashSet에서의 원소)와 equals()로 비교하여 동일 객체인지를 확인합니다.
- 만약 동일 객체가 발견되면 true, 찾을 수 없으면 false를 반환합니다.
4. 트리인 경우
- 버킷이 트리 구조라면, 레드-블랙 트리 특유의 이진 탐색 로직을 사용하여 equals나 compareTo 등을 통해 노드를 찾습니다.
- 일반 연결 리스트보다 빠른 평균 성능(O(log n))을 낼 수 있습니다.
5. 삭제(remove) 과정
HashSet에서 원소를 제거하는 것은 내부적으로 HashMap.remove(key)를 호출하는 것과 동일합니다.
1. hashCode() 호출 및 인덱스 계산
- 삭제할 객체의
hashCode()→ 해시 함수 적용 → (hash & (table.length - 1))로 버킷 인덱스 결정.
2. 해당 버킷에서 노드 탐색
- 버킷 내 연결 리스트(또는 트리)를 순회하며,
equals()로 동일한 노드를 찾습니다.
3. 노드 제거
- 연결 리스트의 경우 해당 노드를 찾으면 앞뒤 노드를 연결(링크 재설정)하면서 제거합니다.
- 트리인 경우 해당 노드를 삭제하고, 레드-블랙 트리 규칙이 깨지지 않도록 재균형(Rebalance) 과정을 거칠 수 있습니다.
- HashMap의 구조 상, 찾고자 하는 노드가 없으면 아무 동작 없이 끝납니다.
4. size 감소
- 삭제가 성공하면 HashMap의 size가 1 감소하고, HashSet도 동일하게 크기가 감소합니다.
remove 과정도 결론적으로 “hash → 인덱스 → 연결 리스트 혹은 트리에서 노드 탐색 → 제거 및 링크 혹은 트리 재조정” 식으로 정리할 수 있습니다.
6. 요약
1. 삽입 (add)
- hashCode() → 해시 조정 → 인덱스 산출 → 해당 버킷의 연결 리스트/트리 탐색
- 만약 같은 객체(equals 동일)가 이미 있다면 삽입 중단, 없으면 새 노드로 삽입
- 버킷 충돌이 많으면 트리화 / 전체 요소 수가 일정 임계값(loadFactor) 넘어가면 리사이징
2. 검색 (contains)
- hashCode() → 인덱스 → 연결 리스트/트리 순회(이진 탐색) → equals로 동일 객체 찾기
- 찾으면 true, 없으면 false
3. 삭제 (remove)
- hashCode() → 인덱스 → 연결 리스트/트리 순회 → 동일 노드 발견 시 제거 → 링크 재설정 or 트리 재균형
- 정상 제거 시 size 감소
결론적으로 해시 함수와 동등성 비교(equals)가 잘 설계되어 있어야, 해시 충돌이 줄어들고 삽입/검색/삭제 모두 평균 O(1) 성능을 유지할 수 있습니다. 충돌이 심하면 연결 리스트/트리를 많이 탐색해야 하므로 최악의 경우 O(n)으로 악화될 수도 있습니다.
7. 추가 참고 사항
-
Load Factor (기본: 0.75)
너무 충돌이 많아지지 않도록, 최대 적재량이 넘으면 배열 크기를 2배로 늘립니다(Resizing + Rehash). -
트리 변환(Chain to Tree)
- 기본적으로 하나의 버킷(인덱스)에 8개 이상의 노드가 연결되면 트리화(Treeify)를 시도.
- 하지만 테이블 전체 크기가 작으면 먼저 테이블 확장을 통해 충돌 수를 줄이려 하고, 그래도 계속 충돌이 많으면 트리화 진행.
-
정렬 순서 보장 없음
- HashSet은 해싱 기반이라 순서를 보장하지 않음.
- 순서가 필요한 경우 LinkedHashSet(버킷에 이중 연결 리스트를 추가) 사용 가능.
-
중복 원소 없음
- HashSet은 동일 객체(equals == true)가 이미 존재할 시 삽입이 이루어지지 않음.
이미지 출처 : yoseph0310.tistory.com
