자료구조 - 해시 자료구조

해시 (충돌, 체이닝, 자료구조)

배열·연결리스트·트리·힙은 모두 데이터의 순서나 구조를 메모리에 어떻게 배치할지에 답을 준 자료구조였다. 해시 테이블은 완전히 다른 질문에 답한다. "키만 알면 그 값을 거의 즉시 찾을 수 있는 자료구조가 있을까?"라는 질문이며, 그 답이 평균 O(1) 시간의 조회·삽입·삭제를 보장하는 해시 테이블(Hash Table)이다. 파이썬 dict, 자바 HashMap, JavaScript Object, Redis 같은 거의 모든 현대 키-값 저장소의 토대가 해시 테이블이며, 그 위에서 데이터베이스 인덱스·캐시·세션 저장소·중복 제거 같은 일상적인 기능들이 동작한다. 본 글은 해시 함수·충돌 해결·시간복잡도와 실전 응용까지 세심하게 정리한다(출처: 위키백과 — Hash Table). 제가 학교 알고리즘 시간 초과로 가장 자주 구원받은 자료구조가 정확히 해시 테이블이었고, 같은 문제를 이중 반복문으로 풀어 O(n²)로 시간 초과가 떨어졌다가 해시로 갈아 끼우자 O(n)으로 통과한 경험이 해시의 가치를 손끝으로 가르쳐 주었다.

 

해시 함수와 해시 테이블의 기본 구조

해시 테이블의 핵심 발상은 "키를 정수로 변환하고, 그 정수를 배열 인덱스로 사용한다"이다. 키를 정수로 변환하는 함수가 해시 함수(Hash Function)이며, h(key) → 정수라는 단순한 약속만 지키면 어떤 변환 방식이든 해시 함수가 될 수 있다. 다만 좋은 해시 함수는 세 가지 조건을 동시에 만족해야 한다. 첫째, 같은 키에 대해 항상 같은 값을 반환해야 한다(결정성). 둘째, 가능한 한 키 공간 전체에 고르게 분포해야 한다(균일성). 셋째, 계산이 빨라야 한다(효율성). 여기서 균일 분포란 임의의 두 키가 같은 해시값을 가질 확률이 가능한 한 1/m에 가까워야 한다는 조건을 의미하며, 충돌(collision)을 최소화하는 가장 결정적인 성질이다.

해시 테이블의 기본 구조는 다음과 같다. 크기 m의 배열을 두고, 키 k가 들어오면 index = h(k) % m을 계산해 그 위치에 값을 저장한다. 조회는 같은 식으로 인덱스를 다시 계산해 그 위치를 직접 읽으면 끝이다. 배열 인덱스 접근은 O(1)이므로 해시 함수 계산이 O(1)이라면 전체 조회도 O(1)이 된다.

# 가장 단순한 해시 테이블 — 충돌 무시
class NaiveHashTable:
    def __init__(self, m=16):
        self.m = m
        self.table = [None] * m

    def _index(self, key):
        return hash(key) % self.m       # 파이썬 내장 hash 사용

    def put(self, k, v):
        self.table[self._index(k)] = (k, v)

    def get(self, k):
        cell = self.table[self._index(k)]
        return cell[1] if cell and cell[0] == k else None

이 단순한 형태에는 결정적인 약점이 있다. 두 키가 같은 인덱스에 매핑되는 충돌(Collision)이 발생하면 한쪽 값이 덮어 써지거나 잘못된 값이 반환된다. 비둘기집 원리(Pigeonhole Principle)에 따라 키의 수가 배열 크기를 넘어가는 순간 충돌은 반드시 발생하며, 실제로는 그보다 훨씬 일찍부터 나타난다. 생일 역설(Birthday Paradox)에 따르면 m=365일 때 충돌이 50% 확률로 발생하는 데에는 23명만 있어도 충분하다. 따라서 해시 테이블의 실용성은 사실상 충돌을 어떻게 처리할 것인가라는 한 질문에 달려 있다.

충돌 해결 — 체이닝과 개방 주소법

해시 충돌을 해결하는 방법은 크게 두 부류로 나뉜다. 첫째, 체이닝(Chaining, 분리 연쇄법)은 한 배열 칸에 여러 값이 들어올 수 있도록 그 칸을 연결리스트(또는 동적 배열·트리)로 만든다. 둘째, 개방 주소법(Open Addressing)은 한 칸에 한 값만 두되, 충돌이 발생하면 정해진 규칙에 따라 다른 빈 칸을 찾아간다. 두 방식은 트레이드오프가 명확히 다르므로 시험과 실무 모두에서 구분해 외워둘 필요가 있다.

# 체이닝 기반 해시 테이블
class ChainingHashTable:
    def __init__(self, m=16):
        self.m = m
        self.buckets = [[] for _ in range(m)]   # 각 칸이 리스트

    def _idx(self, k): return hash(k) % self.m

    def put(self, k, v):
        bucket = self.buckets[self._idx(k)]
        for i, (key, _) in enumerate(bucket):
            if key == k:
                bucket[i] = (k, v); return     # 같은 키는 덮어쓰기
        bucket.append((k, v))                   # 새 키는 끝에 추가

    def get(self, k):
        for key, v in self.buckets[self._idx(k)]:
            if key == k: return v
        return None

개방 주소법에는 세 가지 대표적인 탐사(probing) 전략이 있다. 시험 답안에서 자주 묻는 항목이다.

전략	다음 칸 계산	특징
선형 탐사(Linear Probing)	(h(k) + i) % m	구현 단순, 군집화(clustering) 발생
이차 탐사(Quadratic Probing)	(h(k) + i²) % m	1차 군집은 줄지만 2차 군집 가능
이중 해싱(Double Hashing)	(h₁(k) + i·h₂(k)) % m	가장 균일, 두 개의 해시 함수 필요

여기서 군집화(clustering)란 충돌이 한 영역에 몰리면서 그 주변까지 연쇄적으로 충돌이 늘어나는 현상을 의미하며, 선형 탐사의 가장 큰 약점이다. 솔직히 이건 예상 밖이었는데, 학교 시뮬레이션에서 같은 데이터를 두 방식으로 굴려 본 후 선형 탐사의 평균 조회 시간이 이중 해싱의 두 배가 넘는 모습을 직접 본 후로는 "탐사 전략 한 줄의 차이가 실제 성능을 결정한다"는 점을 손끝으로 받아들였다.

두 방식의 비교를 한 표로 정리하면 다음과 같다.

비교 항목	체이닝	개방 주소법
한 칸의 원소 수	여러 개 (리스트)	항상 1개
메모리 오버헤드	포인터 추가	없음 (배열만)
적재율 1.0 이상 가능	가능	불가능 (1 미만으로만)
캐시 효율	나쁨 (불연속 메모리)	좋음
삭제 처리	단순 (노드 제거)	까다로움 (tombstone 필요)
실무 채택	Java 8 HashMap (트리화 포함)	Python dict, Rust HashMap

여기서 적재율(load factor, α)이란 저장된 원소 수 ÷ 배열 크기로 정의되는 비율로, 해시 테이블의 성능을 결정하는 가장 핵심 지표이다. 일반적으로 α가 0.7~0.75를 넘어가면 재해싱(rehashing) 을 통해 배열 크기를 두 배로 늘리는 것이 표준이며, 이 과정에서 모든 원소의 해시값을 다시 계산해 새 배열에 재배치한다.

시간복잡도와 실전 응용

해시 테이블의 시간복잡도를 표로 정리하면 다음과 같다(출처: CLRS — Introduction to Algorithms).

연산	평균	최악
조회(search)	O(1)	O(n) — 모든 키가 한 버킷에 몰리는 경우
삽입(insert)	O(1)	O(n)
삭제(delete)	O(1)	O(n)
공간	O(n)	O(n)

평균 O(1)이 압도적인 강점이지만, 최악 O(n)이라는 위험이 늘 따라붙는다는 점이 결정적이다. 이 최악을 막기 위해 현대 해시 구현체는 두 가지 안전장치를 둔다. 첫째, 해시 함수 무작위화 — 프로그램 실행마다 다른 시드로 해시를 계산해 악의적인 키 충돌 공격(HashDoS)을 방지한다. 둘째, 체인 길이가 일정 임계치를 넘으면 트리로 전환 — 자바 8의 HashMap은 한 버킷의 체인 길이가 8을 넘으면 그 버킷을 Red-Black 트리로 바꿔 최악을 O(log n)으로 끌어내린다. 솔직히 이건 예상 밖이었는데, "HashMap 안에 트리가 들어 있다"는 사실을 처음 알게 된 후로는 자료구조가 단일 형태로 고정되어 있다는 통념이 무너지고, 실무 자료구조는 거의 예외 없이 여러 구조의 하이브리드라는 점을 받아들였다.

해시 테이블의 실전 응용은 다섯 가지로 정리된다. 첫째, 언어 표준 매핑 컨테이너 — Python dict, Java HashMap, C++ std::unordered_map, JavaScript Object/Map이 모두 해시 테이블 위에 서 있다. 둘째, 중복 제거와 집합 연산 — set 자료형의 표준 구현체이며, 큰 입력에서 중복을 제거하거나 교집합·차집합을 계산할 때 O(n)에 끝낸다. 셋째, 캐시(Cache) — Redis·Memcached 같은 인메모리 캐시의 핵심 자료구조가 해시 테이블이며, 일관 해싱(consistent hashing)을 활용해 분산 환경으로 확장된다. 넷째, 데이터베이스 인덱스 일부 — PostgreSQL의 해시 인덱스, MySQL의 메모리 엔진 인덱스가 대표적이다. 다섯째, 알고리즘 가속기 — Two Sum·Anagram·중복 탐지 같은 코딩 테스트 단골 문제가 해시로 거의 O(n)에 풀린다.

# 실전 — Two Sum (코딩 테스트 단골)
def two_sum(nums, target):
    seen = {}                         # 값 → 인덱스 해시
    for i, x in enumerate(nums):
        if target - x in seen:        # O(1) 조회
            return (seen[target - x], i)
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))    # (0, 1)

위 코드의 시간복잡도는 O(n)이며, 같은 문제를 이중 반복문으로 풀면 O(n²)이 된다. n이 10⁵ 이상이면 차이가 10⁴배가 넘기 때문에 시간 초과 여부가 그대로 갈린다. 마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리해 두면, "해시 테이블은 키를 해시 함수로 정수 인덱스로 변환해 배열에 저장하는 자료구조이며, 평균 O(1) 시간에 조회·삽입·삭제가 가능하다. 충돌 해결 방식에는 체이닝과 개방 주소법이 있다"는 두 문장이 표준 답안 표현으로 통한다. 자료구조 학습에서 마지막 핵심 분기점이며, 여기까지 손에 잡히면 거의 모든 코딩 테스트와 실무 자료구조 의사 결정에서 자신감을 가지고 출발할 수 있다.

---

메타 디스크립션: 해시 테이블의 기본 구조와 해시 함수, 충돌 해결 방식(체이닝·개방 주소법·이중 해싱), 시간복잡도와 적재율, 그리고 캐시·중복 제거·Two Sum 같은 실전 응용을 코드 예시와 함께 자료구조 입문자 관점에서 세심하게 정리합니다.