해시 (Hash)

해시(Hash)는 임의 길이의 키를 해시 함수(hash function)에 통과시켜 고정된 범위의 값으로 변환하고, 그 값을 배열의 인덱스로 사용해 데이터를 저장하고 찾는 기법이다. 이 원리로 만든 해시 테이블(hash table)은 탐색, 삽입, 삭제를 평균 O(1)에 처리하는 가장 빠른 키-값 저장 구조로, 각 언어의 맵(Map)과 딕셔너리(dictionary), 데이터베이스 인덱스, 캐시 등 어디에나 쓰인다. 다만 서로 다른 키가 같은 인덱스로 몰리는 충돌(collision)을 어떻게 처리하느냐가 성능을 좌우한다.

해시 함수와 동작 원리

해시 테이블은 내부에 버킷(bucket) 배열을 두고, 키의 해시값을 배열 크기로 나눈 나머지를 인덱스로 삼는다. 예를 들어 문자열 키 "apple"의 해시값이 93064인데 버킷이 16개라면, 93064를 16으로 나눈 나머지인 8번 버킷에 저장된다. 조회할 때도 같은 계산을 반복하므로 키에서 위치로 바로 점프할 수 있고, 이것이 평균 O(1)의 근원이다.

좋은 해시 함수는 세 조건을 만족해야 한다. 같은 키에 대해 항상 같은 값을 내는 결정성, 계산이 빠를 것, 그리고 출력이 버킷 전체에 고르게 퍼지는 균등 분포다. 분포가 나쁘면 특정 버킷에 데이터가 몰려 성능이 급락한다. 자바(Java)에서 equals를 재정의하면 hashCode도 함께 재정의해야 한다는 규칙도 여기서 나온다. 같다고 판정되는 두 객체가 다른 해시값을 내면 해시 테이블에서 같은 키를 두 번 넣거나 찾지 못하는 오류가 생기기 때문이다.

충돌 해결 전략

키 공간은 무한에 가깝고 버킷은 유한하므로 충돌은 피할 수 없다. 해결 방식은 크게 두 갈래다.

체이닝(separate chaining)은 각 버킷에 연결 리스트를 두고 충돌한 항목들을 매달아 두는 방식이다. 구현이 단순하고 삭제가 쉬우며 적재율이 높아져도 완만하게 느려진다. 자바의 HashMap이 이 방식이며, 한 버킷의 리스트가 일정 길이(8개)를 넘으면 레드 블랙 트리(Red-Black Tree)로 바꿔 최악의 버킷 탐색을 O(n)에서 O(log n)으로 낮추는 최적화까지 더해져 있다.

개방 주소법(open addressing)은 충돌이 나면 정해진 규칙으로 다른 빈 버킷을 찾아가는 방식이다. 한 칸씩 옆으로 이동하는 선형 조사(linear probing), 제곱수만큼 건너뛰는 제곱 조사(quadratic probing), 두 번째 해시 함수로 보폭을 정하는 이중 해싱(double hashing)이 있다. 별도의 노드 할당이 없어 캐시 효율이 좋지만, 데이터가 몰리는 군집화(clustering)에 취약하고 삭제 시 탐사 사슬이 끊기지 않도록 삭제 표시(tombstone)를 남겨야 하는 부담이 있다. 파이썬(Python)의 dict가 개방 주소법 계열이다.

적재율과 리해싱

저장된 항목 수를 버킷 수로 나눈 값을 적재율(load factor)이라고 한다. 적재율이 높아질수록 충돌이 잦아지므로, 해시 테이블은 임계치(자바 HashMap 기본값 0.75)를 넘으면 버킷 배열을 두 배로 늘리고 모든 항목의 위치를 다시 계산하는 리해싱(rehashing)을 수행한다. 리해싱 자체는 O(n)이지만 발생 빈도가 기하급수적으로 줄어 삽입의 분할 상환(amortized) 비용은 O(1)로 유지된다. 담을 개수를 미리 안다면 초기 용량을 지정해 리해싱을 피하는 것이 실무 최적화 포인트다.

연산	평균	최악
탐색	O(1)	O(n)
삽입	O(1)	O(n)
삭제	O(1)	O(n)

최악의 경우는 모든 키가 한 버킷에 몰릴 때다. 악의적인 입력으로 이를 유도하는 해시 플러딩(hash flooding) 공격이 가능하기 때문에, 여러 언어 런타임은 해시 시드를 무작위화해 방어한다.

class SimpleHashMap {
    static class Entry {
        String key; int value; Entry next;
    }
    Entry[] buckets = new Entry[16];

    int indexOf(String key) {
        return (key.hashCode() & 0x7fffffff) % buckets.length;
    }

    void put(String key, int value) {
        int idx = indexOf(key);
        for (Entry e = buckets[idx]; e != null; e = e.next) {
            if (e.key.equals(key)) { e.value = value; return; }
        }
        Entry e = new Entry();
        e.key = key; e.value = value;
        e.next = buckets[idx];
        buckets[idx] = e; // 리스트 머리에 삽입
    }
}