Maps and Sets
해싱 (Hashing)
해싱의 기본 개념
해싱은 요소의 키를 간단한 연산을 통해 배열의 인덱스로 변환하여 해당 위치에 요소를 저장하는 방식입니다. 적절히 구현된 해싱은 평균적으로 상수 시간 (O(1))에 검색, 삽입, 삭제를 처리할 수 있습니다.
목표
해싱의 작동 원리와 사용해야 할 때, 사용하지 말아야 할 때를 이해하기.
- 균일 해싱 가정 (Uniform Hashing Assumption)의 중요성을 설명하기.
충돌 처리 방법 → 체이닝 (Chaining)
1. 순차 검색 (Sequential Search)
정렬되지 않은 배열에서도 사용 가능.
처음부터 끝까지 하나씩 비교하여 원하는 요소를 찾는 방식.
평균 시간 복잡도: O(n)
최악의 경우: 요소가 없거나 마지막 위치에 있는 경우로 O(n)
2. 이진 검색 (Binary Search)
정렬된 배열에서만 사용 가능.
배열의 중간 요소와 비교하여 탐색 범위를 절반으로 줄이는 방식.
평균 및 최악의 시간 복잡도: O(log n)
장점: 빠른 검색 속도.
단점: 배열이 정렬되어 있어야 함.
3. 해싱의 필요성
순차 검색과 이진 검색은 데이터의 양이 많을수록 성능 저하가 심합니다.
해싱은 이러한 문제를 해결하기 위해 개발된 방식으로, 상수 시간 복잡도를 목표로 합니다.
해싱의 핵심은 “빠른 접근을 위해 데이터를 배열의 특정 인덱스에 직접 매핑”하는 것입니다.
HashMap의 Map 인터페이스 구현
HashMap 클래스는 Map 인터페이스를 구현하며, 다음과 같은 기본 메서드를 제공합니다:
- put(): 키-값 쌍을 추가
- remove(): 키를 통해 요소 제거
- containsKey(): 키의 존재 여부 확인
- size(), isEmpty(), clear(): 기본적인 테이블 상태 확인 및 초기화
- toString(), entrySet(), keySet(), valueSet(): 키, 값, 엔트리의 집합 반환
출력 순서 정렬안됨.
TreeMap은 정렬된 맵을 제공하지만 HashMap은 빠른 접근을 위해 순서가 유지되지 않음.
HashMap의 저장 방식
각 키는 hashCode() 메서드를 통해 해시값으로 변환됩니다.
인덱스 계산:
hash(key.hashCode()) & (table.length - 1)
커스텀 객체의 hashCode() 메서드
String 클래스는 이미 최적화된 hashCode() 메서드를 가지고 있지만, 커스텀 객체는 직접 구현해야 합니다.
public int hashCode() {
return name.hashCode() + new Double(grossPay).hashCode();
}
6. 충돌 (Collision) 처리
두 키가 같은 해시 인덱스를 갖는 경우 충돌이 발생합니다. 충돌이 많을수록 검색 속도가 느려지므로 이를 줄이는 것이 중요합니다.
Uniform Hashing Assumption (UHA)
Uniform Hashing Assumption는 해시 테이블의 모든 인덱스에 키가 동일한 확률로 분포된다는 가정입니다. 이를 만족하면 해시 테이블의 성능이 크게 향상됩니다.
핵심 특징
해시 함수를 통해 생성된 인덱스가 테이블 전체에 고르게 분포해야 효율적입니다.
index = hash(key.hashCode()) & (table.length - 1)
이상적으로는 모든 키가 동일한 확률로 모든 인덱스에 매핑되어야 합니다. 하지만 현실적으로 모든 해시 함수가 이 가정을 항상 만족하는 것은 불가능하므로, 충돌은 여전히 발생할 수 있습니다.
Chaining (체이닝)
충돌 처리 방법 → 체이닝은 충돌이 발생할 때 단일 인덱스에 여러 키-값 쌍을 연결 리스트 형태로 저장하는 방식입니다.
- 각 테이블 위치는 단일 연결 리스트로 구성됩니다.
동작 원리
- 초기 테이블의 각 위치는 빈 연결 리스트로 시작합니다.
- 새로운 요소가 추가될 때 리스트의 맨 앞에 삽입됩니다.
- 다음과 같은 키와 인덱스가 있다고 가정합니다:
- 충돌이 포함, 각 인덱스에 여러 요소가 포함될 수 있음을 보여줍니다.
Resizing (리사이징)
해시 테이블은 지정된 임계치를 초과할 때 크기를 확장해야 합니다. 기본적으로 load factor가 0.75로 설정되어 있음.
- 이는 충돌을 줄이고 효율적인 검색을 보장하는 데 중요한 역할을 합니다.
LoadFactor
테이블의 크기(table.length)와 요소 개수(size)의 비율이 최대 얼마까지 허용될지를 결정하는 값입니다. 기본값은 0.75로 설정되어 있으며, 이는 테이블이 75% 찼을 때 리사이징이 발생함을 의미합니다.
- 낮을수록 검색 성능이 향상되지만, 메모리 사용량이 증가할 수 있습니다.
- 반대로 높을수록 메모리 사용은 효율적이지만, 충돌이 증가할 가능성이 있습니다.
Threshold
실제로 리사이징이 발생하는 시점을 결정하는 구체적인 요소 개수입니다.
threshold = (int)(table.length * loadFactor);
기본적으로 테이블의 크기가 2의 거듭제곱이므로, 리사이징은 지수적 증가 형태로 발생합니다. 예를 들어, 초기 용량이 16일 때 threshold는 12가 됩니다.
- 요소가 threshold를 초과하면 테이블이 확장되고
rehash()가 발생합니다.
rehash() - 배열 재구성
배열 크기 확장:
-
oldCapacity << 1: 배열의 크기를 두 배로 증가 - 재분배: 모든 기존 요소를 새로운 배열로 옮기고, 인덱스를 다시 계산하여 배치합니다.
- 이는 시간 복잡도가 O(N)이지만, put()의 평균 시간 복잡도는 상수 (amortized constant)입니다. put() 호출 시 매번 rehash()가 일어나지 않기 때문에 최적화된 성능을 보입니다.
hashCode()와 equals() 오버라이딩
사용자 정의 객체를 키로 사용할 경우, hashCode()와 equals() 메서드를 모두 오버라이딩해야 합니다. 이는 동일한 논리적 객체가 동일한 해시 값을 가지도록 보장하며, 해시맵의 정확한 동작을 위해 필수적입니다.
TreeMap
put(K key, V value)
- 지정된 Key와 Value를 이 Map 객체에 추가합니다.
- 이미 동일한 키가 존재하는 경우, 해당 키의 이전 값을 새로운 값으로 교체합니다.
- 반환값: 이전에 매핑된 값이 있으면 해당 값을 반환하고, 없으면 null을 반환합니다.
containsKey(Object key)
- 지정된 Key가 이 Map 객체에 존재하는지 확인합니다.
- 반환값: 해당 키가 존재하면 true, 없으면 false
TreeMap과 HashMap
- TreeMap
- Red-Black Tree를 기반으로 하며, 키의 순서를 유지합니다.
- 삽입, 삭제, 검색이 최악의 경우에도 O(log n)입니다.
- SortedMap 인터페이스를 구현하여, 키의 정렬이 가능합니다.
- HashMap
- 해시 테이블을 기반으로 하며, 순서가 보장되지 않습니다.
- 평균적으로 O(1)의 시간 복잡도를 가지지만, 최악의 경우 O(n)까지 느려질 수 있습니다.
Java Map 관련 주요 클래스의 시간 복잡도 정리
1. HashMap
- 기반 구조: Hash Table
- 특징: 비순서적, Key의 고유성 보장, null 키와 값 허용
| 연산 | 시간 복잡도 (평균) | 시간 복잡도 (최악) |
|---|---|---|
| put(K, V) | O(1) | O(n) (해시 충돌 시) |
| get(K) | O(1) | O(n) (해시 충돌 시) |
| remove(K) | O(1) | O(n) (해시 충돌 시) |
| containsKey(K) | O(1) | O(n) (해시 충돌 시) |
| containsValue(V) | O(n) | O(n) |
| size() | O(1) | O(1) |
| entrySet() | O(n) | O(n) |
2. LinkedHashMap
- 기반 구조: Hash Table + Doubly Linked List
- 특징: 입력 순서 또는 접근 순서 유지
| 연산 | 시간 복잡도 (평균) | 시간 복잡도 (최악) |
|---|---|---|
| put(K, V) | O(1) | O(n) (해시 충돌 시) |
| get(K) | O(1) | O(n) (해시 충돌 시) |
| remove(K) | O(1) | O(n) (해시 충돌 시) |
| containsKey(K) | O(1) | O(n) (해시 충돌 시) |
| containsValue(V) | O(n) | O(n) |
| size() | O(1) | O(1) |
| entrySet() | O(n) | O(n) |
3. TreeMap
- 기반 구조: Red-Black Tree (Balanced Binary Search Tree)
- 특징: 키가 정렬된 상태로 유지, SortedMap 인터페이스 구현
| 연산 | 시간 복잡도 (평균) | 시간 복잡도 (최악) |
|---|---|---|
| put(K, V) | O(log n) | O(log n) |
| get(K) | O(log n) | O(log n) |
| remove(K) | O(log n) | O(log n) |
| containsKey(K) | O(log n) | O(log n) |
| containsValue(V) | O(n) | O(n) |
| size() | O(1) | O(1) |
| entrySet() | O(n) | O(n) |
4. Hashtable
- 기반 구조: Synchronized Hash Table
- 특징: Thread-safe, null 키와 값 허용하지 않음
| 연산 | 시간 복잡도 (평균) | 시간 복잡도 (최악) |
|---|---|---|
| put(K, V) | O(1) | O(n) (해시 충돌 시) |
| get(K) | O(1) | O(n) (해시 충돌 시) |
| remove(K) | O(1) | O(n) (해시 충돌 시) |
| containsKey(K) | O(1) | O(n) (해시 충돌 시) |
| containsValue(V) | O(n) | O(n) |
| size() | O(1) | O(1) |
| entrySet() | O(n) | O(n) |
주요 차이점 요약
- HashMap: 빠른 접근 속도 (평균 O(1)), 순서 유지 안 함, null 키/값 허용
- LinkedHashMap: 입력/접근 순서 유지, 약간의 메모리 오버헤드
- TreeMap: 키 정렬, 균형 이진 트리 기반 (O(log n))
- Hashtable: 스레드 안전하지만 성능 저하
최악의 경우가 발생하는 상황
- 해시 함수가 매우 비효율적이거나,
- load factor (부하율)가 매우 높아 테이블이 과밀해진 경우,
- 모든 요소가 동일한 hashCode()를 가지는 경우입니다.
Leave a comment