해시 테이블 2

해시 테이블에서 본 해시 충돌(hash collision) 처리 방식을 바탕으로, 해시 테이블(hash table)의 성능을 좌우하는 조건을 이어서 다룬다. 테이블이 얼마나 찼는지에 따라 칸을 늘리는 방법과 평균 O(1)이 깨지는 경우를 보고, Java HashMap의 실제 동작과 키 객체가 지켜야 할 규약을 정리한다. 마지막으로 키의 순서가 필요할 때 고르는 트리(tree)와 비교한다.

적재율과 재해싱

적재율(load factor)은 버킷(bucket) 수 대비 저장된 원소 수의 비율이다. 적재율이 높을수록 충돌이 잦아져, 체이닝(chaining)에서는 리스트가 길어지고 개방 주소법(open addressing)에서는 빈칸을 찾을 때까지 다른 칸을 차례로 확인하는 탐사(probing)가 길어진다. 그래서 적재율이 정해 둔 기준을 넘으면 더 큰 배열(array)을 새로 만들고 모든 원소를 옮기는 재해싱(rehashing)을 한다. 버킷 위치는 보통 해시 값을 버킷 수로 나눈 나머지로 정한다. 그래서 버킷 수가 바뀌면 같은 키라도 들어갈 버킷이 달라지고, 원소를 그대로 복사하지 못해 위치를 하나하나 다시 계산해야 한다.

재해싱 한 번은 원소 수만큼 걸리는 O(n) 작업이다. 여기서 O(n)은 빅오 표기법(Big-O notation)으로, 원소 수 n에 비례해 시간이 늘어난다는 뜻이다(O(1)은 원소 수와 상관없이 일정한 시간). 하지만 배열을 매번 두 배처럼 일정 비율로 키우면, 재해싱 사이에 삽입이 점점 더 많이 쌓인다. 그래서 옮긴 원소 수를 모두 더해도 전체 삽입 횟수의 몇 배를 넘지 않고, 삽입 횟수로 나누면 한 번당 O(1)이 된다. 가끔 있는 비싼 작업을 전체 횟수로 나눠 한 번당 비용을 보는 이 방법을 분할 상환 분석(amortized analysis)이라 하고, 이 결과를 분할 상환 O(1)이라 부른다. 아래 표의 "평균"은 이것과 다르다. 키가 버킷에 고르게 흩어진다고 가정했을 때, 여러 경우를 평균 내어 보통 걸리는 비용이다.

연산	평균	최악
찾기·넣기·지우기	O(1)	O(n)

평균 O(1)은 해시 함수(hash function)가 키를 고르게 퍼뜨리고 적재율이 기준 아래로 유지된다는 가정 위에서만 성립한다. 모든 키가 한 버킷에 몰리면 체이닝은 리스트 하나를 끝까지 훑어야 하므로 O(n)이 된다. 해시 함수를 아는 공격자가 일부러 같은 버킷으로 가는 키를 대량으로 보내 서버를 느리게 만드는 해시 플러딩(hash flooding) 공격도 이 약점을 노린다.

Java HashMap과 hashCode·equals

Java의 HashMap은 체이닝 방식 해시 테이블이다.

• 기본 초기 용량은 버킷 16개, 기본 적재율은 0.75다. 원소 수가 "용량 × 적재율"을 넘으면 버킷 수를 약 두 배로 늘려 재해싱한다. 기본값이면 원소가 12개를 넘을 때 처음 늘어난다.
• 이미 원소가 8개 있는 버킷에 또 넣으면, 그 버킷의 리스트를 레드-블랙 트리(red-black tree)로 바꾼다. 레드-블랙 트리는 스스로 높이를 낮게 유지하는 정렬 트리라서, 몰린 버킷 안에서도 O(log n)에 가깝게 찾는다. 단 전체 버킷 수가 64보다 작으면 트리로 바꾸는 대신 테이블을 키운다. 재해싱으로 버킷이 나뉘어 6개 이하가 되면 다시 리스트로 돌아간다¹.

hashCode는 객체의 해시 값을 정수로 돌려주는 메서드이고, equals는 두 객체의 내용이 같은지 판단하는 메서드다. HashMap은 hashCode로 버킷을 고르고 equals로 그 버킷 안의 키를 비교하므로, 키 객체는 두 메서드의 규약을 지켜야 한다. equals로 같은 두 객체는 반드시 같은 hashCode를 돌려줘야 한다. 반대로 hashCode가 같다고 equals까지 같을 필요는 없다(그게 충돌이다). equals만 재정의(override)하고 hashCode를 그대로 두면, 내용이 같은 키로 찾아도 다른 버킷을 보게 되어 값을 못 찾는다.

class Key {
    final int id;
    Key(int id) { this.id = id; }
    @Override public boolean equals(Object o) { return o instanceof Key k && k.id == id; }
    // hashCode를 재정의하지 않았다 → 객체마다 다른 기본 해시 값
}
map.put(new Key(1), "A");
map.get(new Key(1));   // 거의 항상 null: 다른 해시 값으로 다른 버킷을 본다

키로 쓴 객체의 필드를 넣은 뒤에 바꾸는 것도 같은 문제를 만든다. 해시 값이 바뀌어 원래 버킷에서 찾지 못하게 된다.

해시 테이블과 이진 탐색 트리

같은 "키로 값 찾기"를 이진 탐색 트리(binary search tree)로도 할 수 있다. 이진 탐색 트리는 왼쪽에 작은 키, 오른쪽에 큰 키를 두는 트리라서 키가 늘 정렬된 상태로 남는다. 해시 테이블은 키를 흩뿌려 저장하므로 순서 정보가 없다.

기준	해시 테이블	균형 이진 탐색 트리
찾기·넣기·지우기	평균 O(1), 최악 O(n)	항상 O(log n)
키 순서	없음	정렬 순서 유지
범위 찾기·최솟값	전체를 훑어야 함	O(log n)에 시작점을 찾음
Java 예	HashMap	TreeMap

"정확히 이 키"만 찾으면 해시 테이블이 빠르다. "10 이상 20 이하"나 "가장 작은 키"처럼 순서가 필요한 질문이 있으면 트리를 고른다. 자세한 구조는 트리와 이진 탐색 트리 2에서 다룬다.

면접 포인트

• "적재율이 뭔가요?" → 원소 수 / 버킷 수. 기준을 넘으면 재해싱. Java HashMap 기본 0.75.
• "해시 테이블의 최악은?" → 키가 한 버킷에 몰리면 O(n). 평균 O(1)은 고른 분포와 적재율 유지가 전제.
• "equals만 재정의하면?" → 같은 내용의 키가 다른 버킷으로 가 조회 실패. 같으면 같은 hashCode가 규약.
• "해시 테이블 vs 트리" → 순서·범위 질의가 필요하면 트리(TreeMap), 정확한 키 조회면 해시(HashMap).

참고

1. 8·6·64라는 숫자는 OpenJDK HashMap.java 소스의 상수 TREEIFY_THRESHOLD·UNTREEIFY_THRESHOLD·MIN_TREEIFY_CAPACITY이고, API 문서가 약속하는 동작은 아니다. 트리 버킷의 O(log n)도 키의 해시 값이 서로 다르거나 키끼리 크기 비교(Comparable)가 될 때 성립한다고 소스 주석에 적혀 있다. ↩︎