해시 테이블

해시 테이블이란

해시 테이블(Hash Table)은 키를 해시 함수에 넣어 나온 값을 배열 인덱스로 쓰는 자료구조다. 키만 알면 그 칸으로 바로 가므로 탐색·삽입·삭제가 평균 O(1) 이다. 다른 원소를 밀거나 당길 필요가 없다는 점이 배열·연결 리스트와 다르다.

flowchart LR
  K["key #quot;apple#quot;"] -->|"hash()"| H["93847102"]
  H -->|"mod 버킷 수(16)"| I["인덱스 6"]
  I --> B["buckets[6]"]

평균이 O(1)이고 최악이 O(n)인 이유는 충돌이다. 키가 한 버킷에 몰리면 그 안을 순서대로 뒤져야 한다.

좋은 해시 함수

키의 공간은 버킷 수보다 훨씬 크므로 충돌을 없앨 수는 없다. 1:1 대응을 만들려면 키 공간만큼 배열이 필요해 해시 테이블을 쓰는 의미가 사라진다. 그래서 목표는 충돌을 줄이는 함수와, 생긴 충돌을 싸게 처리하는 방법 두 가지다.

보조 해시 함수(supplemental hash) 는 키의 해시값을 한 번 더 섞어 버킷 인덱스가 고르게 나오게 한다. 버킷 수가 2의 거듭제곱이면 hash & (n - 1)로 하위 비트만 쓰게 되는데, 상위 비트가 버려지지 않도록 섞는 것이다. Java HashMap은 h ^ (h >>> 16)으로 상위 16비트를 하위에 섞는다.

공격자가 같은 버킷으로 가는 키를 대량으로 보내 서버를 O(n²)로 떨어뜨리는 해시 플러딩(hash flooding) 도 있다. 그래서 Python str·Rust HashMap은 실행마다 바뀌는 시드를 넣은 SipHash 계열 함수를 쓴다.

충돌 해결

개방 주소법 (Open Addressing)

충돌이 나면 배열 안의 다른 빈 버킷을 찾아 넣는다. 원소가 모두 배열 안에 있다. 다음 칸을 고르는 규칙(탐사, probing)에 따라 나뉜다.

이중 해싱은 키마다 탐사 간격이 달라 군집이 거의 없다는 것이 장점이다. 단점과 해결은 다음과 같다.

• 삭제한 칸을 그냥 비우면 그 뒤로 이어지던 탐사가 끊긴다. 그래서 「지워졌음」 표시(tombstone)를 남긴다.
• 적재율이 높아지면 빈칸을 찾는 길이가 급격히 늘어난다. 보통 0.5~0.9 사이에서 리사이즈한다.

분리 연결법 (Separate Chaining)

각 버킷이 원소 목록을 따로 가지고, 충돌한 원소는 그 목록에 붙는다.

두 방식 비교

원소가 작고 적재율을 낮게 유지할 수 있으면 개방 주소법이 빠르다. 최신 고성능 해시 테이블(Google의 Swiss Table, Rust hashbrown, Go 1.24 이후 map)은 개방 주소법에 메타데이터 바이트와 SIMD 비교를 더해 한 번에 여러 칸을 검사한다.

적재율과 리사이즈

버킷이 적으면 메모리는 아끼지만 충돌이 늘어난다. 그래서 적재율이 임계값을 넘으면 버킷 배열을 보통 2배로 늘리고 모든 원소를 새 인덱스로 다시 넣는다(rehash). 리사이즈 한 번은 O(n)이지만 드물게 일어나므로 삽입의 분할 상환(amortized) 비용은 O(1) 이다.

임계값을 어디에 둘지는 적재율 α에 따른 평균 탐사 횟수로 정한다. 키가 버킷에 고르게 퍼진다고 가정한 기댓값이다.

분리 연결법은 α에 비례해 천천히 늘지만, 개방 주소법은 1/(1 − α) 꼴이라 α가 1에 다가가면 폭발한다. 군집이 생기는 선형 탐사는 더 빨리 나빠진다. 개방 주소법 구현이 적재율을 0.5~0.9 아래로 묶는 이유다.

버킷 16개, 적재율 0.75 → 원소 12개를 넘는 순간 32개로 확장 → 다음 임계값 24개

원소 수를 미리 알면 처음부터 충분한 크기로 만들어 리사이즈를 피한다(new HashMap<>(expected / 0.75f + 1), Java 19 이상은 HashMap.newHashMap(expected)).

언어별 구현

트리 전환 기준이 8과 6으로 벌어져 있는 것은 경계에서 원소 하나가 들고 날 때마다 리스트와 트리를 오가는 비용을 막기 위해서다. 7개 언저리에서는 지금 구조를 그대로 유지한다. Java 7까지는 연결 리스트만 썼고, Java 8에서 트리 버킷이 들어왔다.

문제 풀이에서 쓰는 패턴

알고리즘 문제에서 가장 자주 쓰는 자료구조다. 막히면 「해시 테이블로 무엇을 O(1)에 조회하면 풀리나」부터 따져 본다. 면접에서는 평균 O(1)을 기준으로 이야기한다.

해시 맵 + 연결 리스트: LRU·LFU 캐시

캐시가 꽉 찼을 때 무엇을 버릴지 정하는 정책 중 LRU(Least Recently Used) 는 가장 오래 안 쓴 것을, LFU(Least Frequently Used) 는 가장 적게 쓴 것을 버린다. 정책의 장단점은 캐시 전략, 페이지 교체에서의 쓰임은 가상 메모리에 있다. 여기서는 두 정책을 모든 연산 O(1)로 만드는 자료구조 조합만 다룬다.

이중 연결 리스트가 필요한 이유는 노드 하나를 쥔 채로 O(1)에 떼어 내기 위해서다. 단일 연결 리스트는 앞 노드를 찾느라 O(n)이 든다. 맵의 값이 리스트 노드를 가리키므로 「찾기」는 맵이, 「순서 바꾸기」는 리스트가 맡는다.

from collections import OrderedDict    # 해시 맵 + 이중 연결 리스트를 묶어 둔 타입
 
class LRUCache:
    def __init__(self, capacity):
        self.cap, self.data = capacity, OrderedDict()
 
    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)          # 가장 최근으로
        return self.data[key]
 
    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)   # 가장 오래된 것 제거

Java는 new LinkedHashMap<>(16, 0.75f, true)(접근 순서 모드)에 removeEldestEntry를 재정의하면 같은 캐시가 된다. 면접에서는 이 라이브러리 없이 노드 클래스와 머리·꼬리 더미 노드로 직접 짜기를 기대하는 경우가 많다.

해시는 원소의 순서를 기억하지 않는다. 회문처럼 순서가 답을 정하는 문제에는 투 포인터가 맞다.

정리

• 해시 테이블 = 해시 함수로 인덱스를 계산하는 배열. 평균 O(1), 충돌이 몰리면 최악 O(n)
• 충돌은 피할 수 없다. 고르게 퍼지는 해시 함수와 충돌 처리 방식이 성능을 정한다
• 개방 주소법은 캐시에 강하고 적재율에 민감하다. 분리 연결법은 적재율에 너그럽고 포인터 비용이 든다
• 적재율 임계값에서 2배로 리사이즈해 삽입을 분할 상환 O(1)로 유지한다
• Java HashMap은 체이닝 + 8/6 기준 트리 버킷, Python dict·Go map은 개방 주소법이다

관련 노트: 기초 자료구조: 배열에서 트라이까지, 트리와 이진 탐색 트리, 빅오 표기법, Java 관용구