icon

안동민 개발노트

4장: 해시 테이블과 집합

해시 함수와 충돌 해결 전략

해시 테이블은 키를 숫자로 바꿔 버킷에 저장하는 자료구조입니다. 조회가 빠르기 때문에 코테와 실무에서 모두 자주 사용됩니다. 다만 실제 환경에서는 충돌이 반드시 생긴다고 보고 설계해야 합니다.

해시를 제대로 쓰려면 속도만 보면 안 됩니다. 체이닝/오픈 어드레싱 중 어떤 전략을 쓸지, 언제 재해시할지, 삭제를 어떻게 처리할지까지 함께 정해야 합니다. 여기서는 공식 암기보다 어디서 느려지는지를 손으로 확인하는 방식으로 기준을 잡습니다.

핵심 개념: 해시와 충돌 처리

해시를 처음 보면 용어가 많아 보여도 실제로는 세 가지를 이해하면 됩니다. 지금 문제를 기준으로 충돌이 났을 때 어떻게 처리할지 우선 한 줄로 정해 두고 읽어 보세요.

해시 함수는 키를 버킷 번호로 바꾸는 규칙입니다. 정의로는 입력 키를 정수 값으로 매핑해 버킷 인덱스를 계산하는 함수입니다. "apple"을 해시해 bucket[3]에 넣었다면, 조회할 때도 같은 "apple"은 다시 3을 계산해 같은 위치를 확인합니다.

버킷 배열은 해시 결과가 실제로 저장되는 슬롯 집합입니다. 해시 값을 버킷 수로 나눈 나머지를 저장 위치로 쓰기 때문에 배열 인덱스처럼 접근할 수 있습니다. 버킷이 8개라면 인덱스는 항상 0~7 범위가 되고, % 8 결과로 저장 칸이 결정됩니다.

충돌 해결 전략은 서로 다른 키가 같은 버킷에 들어왔을 때의 처리 정책입니다. 정확히는 같은 인덱스에 매핑된 여러 키를 저장하고 다시 찾을 수 있게 만드는 저장 규칙입니다. 체이닝은 같은 버킷에 리스트로 이어 붙이고, 오픈 어드레싱은 빈 슬롯을 찾을 때까지 이동합니다.

해시 설계가 실무에서 중요한 이유

실무에서 해시 장애는 보통 느려짐으로 우선 나타납니다.
특정 키 패턴에서 충돌이 몰리면 조회/삽입이 선형에 가까워질 수 있습니다.

또한 충돌 전략에 따라 삭제 구현 난이도도 달라집니다.
삭제가 많은 시스템에서 전략을 잘못 고르면 성능이 지속적으로 악화됩니다.

충돌 케이스 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

충돌이 어떻게 성능을 바꾸는지 작은 버킷으로 따라가 봅니다.

  • 버킷 수: 4
  • 키 삽입 순서: a, e, i (같은 버킷으로 충돌한다고 가정)
  1. 체이닝은 같은 버킷 리스트 길이가 1 -> 2 -> 3으로 늘어납니다.
  2. 오픈 어드레싱은 빈 슬롯을 찾기 위해 probe 횟수가 증가합니다.
  3. 충돌 자체는 피할 수 없으므로, 전략과 재해시 정책이 핵심입니다.

아래 흐름도를 기준으로 입력 분포와 삭제 빈도를 먼저 판단하면, 체이닝과 선형 탐사를 상황에 맞게 선택할 수 있습니다.

체이닝 기반 해시 구현

문제 의도: 체이닝 전략에서 충돌 버킷 관리와 기본 연산을 확인합니다.
입력 예시: 충돌 가능한 문자열 키 여러 개 삽입 후 조회/삭제
출력 예시: 조회 결과와 버킷 상태 put은 키가 이미 있으면 값을 덮어쓰고, 없으면 새로 추가하는 연산입니다.

main.cpp
#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>
using namespace std;

class ChainHashTable {
private:
    vector<list<pair<string, int>>> buckets;
public:
    explicit ChainHashTable(int size = 8) : buckets(size) {}

    int index(const string& key) const {
        return static_cast<int>(hash<string>{}(key) % buckets.size());
    }

    void put(const string& key, int value) {
        auto& bucket = buckets[index(key)];
        for (auto& kv : bucket) {
            if (kv.first == key) {
                kv.second = value;
                return;
            }
        }
        bucket.push_back({key, value});
    }

    bool get(const string& key, int& out) const {
        const auto& bucket = buckets[index(key)];
        for (const auto& kv : bucket) {
            if (kv.first == key) {
                out = kv.second;
                return true;
            }
        }
        return false;
    }
};

int main() {
    ChainHashTable ht;
    ht.put("alice", 10);
    ht.put("bob", 20);
    ht.put("alice", 30);

    int value = 0;
    cout << (ht.get("alice", value) ? to_string(value) : "None") << "\n";
    cout << (ht.get("carol", value) ? to_string(value) : "None") << "\n";
    return 0;
}
Main.java
import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Entry {
        String key;
        int value;
        Entry(String key, int value) { this.key = key; this.value = value; }
    }

    static class ChainHashTable {
        List<List<Entry>> buckets;

        ChainHashTable(int size) {
            buckets = new ArrayList<>();
            for (int i = 0; i < size; i++) buckets.add(new ArrayList<>());
        }

        ChainHashTable() { this(8); }

        int index(String key) {
            return Math.floorMod(key.hashCode(), buckets.size());
        }

        void put(String key, int value) {
            List<Entry> bucket = buckets.get(index(key));
            for (Entry e : bucket) {
                if (e.key.equals(key)) {
                    e.value = value;
                    return;
                }
            }
            bucket.add(new Entry(key, value));
        }

        Integer get(String key) {
            List<Entry> bucket = buckets.get(index(key));
            for (Entry e : bucket) {
                if (e.key.equals(key)) return e.value;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        ChainHashTable ht = new ChainHashTable();
        ht.put("alice", 10);
        ht.put("bob", 20);
        ht.put("alice", 30);
        System.out.println(ht.get("alice"));
        System.out.println(ht.get("carol"));
    }
}
main.py
class ChainHashTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        i = 0
        while i < len(bucket):
            if bucket[i][0] == key:
                bucket[i] = (key, value)
                return
            i += 1
        bucket.append((key, value))
        self.count += 1

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

ht = ChainHashTable()
ht.put("alice", 10)
ht.put("bob", 20)
ht.put("alice", 30)
print(ht.get("alice"))  # 30
print(ht.get("carol"))  # None
main.rs
#[derive(Clone)]
struct ChainHashTable {
    buckets: Vec<Vec<(String, i32)>>,
}

impl ChainHashTable {
    fn new(size: usize) -> Self {
        Self {
            buckets: vec![Vec::new(); size],
        }
    }

    fn index(&self, key: &str) -> usize {
        let mut h: usize = 0;
        for b in key.as_bytes() {
            h = h.wrapping_mul(131).wrapping_add(*b as usize);
        }
        h % self.buckets.len()
    }

    fn put(&mut self, key: &str, value: i32) {
        let idx = self.index(key);
        for (k, v) in &mut self.buckets[idx] {
            if k == key {
                *v = value;
                return;
            }
        }
        self.buckets[idx].push((key.to_string(), value));
    }

    fn get(&self, key: &str) -> Option<i32> {
        let idx = self.index(key);
        for (k, v) in &self.buckets[idx] {
            if k == key {
                return Some(*v);
            }
        }
        None
    }
}

fn main() {
    let mut ht = ChainHashTable::new(8);
    ht.put("alice", 10);
    ht.put("bob", 20);
    ht.put("alice", 30);
    println!("{:?}", ht.get("alice"));
    println!("{:?}", ht.get("carol"));
}

해시 충돌 처리 결과 해시 충돌 징후 확인

체이닝에서는 버킷 내부 탐색이 선형입니다.
버킷 길이가 짧으면 빠르지만, 충돌이 쌓이면 병목이 됩니다.
따라서 로드 팩터 관리와 재해시 정책이 필수입니다.

  • 평균 시간복잡도: 조회/삽입 O(1)
  • 최악 시간복잡도: 조회/삽입 O(N)
  • 공간복잡도: O(N)

단순 선형 탐사(오픈 어드레싱)

문제 의도: 선형 탐사에서 probe 경로와 삭제 처리 난이도를 이해합니다.
입력 예시: 작은 테이블에 연속 삽입 + 일부 삭제 + 재조회
출력 예시: 슬롯 상태와 조회 성공/실패 결과 idx = (idx + 1) % size 한 줄이 충돌 시 다음 칸으로 이동하는 선형 탐사 규칙입니다.

main.cpp
#include <iostream>
#include <optional>
#include <string>
#include <vector>
using namespace std;

class LinearProbeHash {
private:
    int size;
    vector<optional<pair<string, int>>> table;
public:
    explicit LinearProbeHash(int s = 11) : size(s), table(s) {}

    int index(const string& key) const {
        return static_cast<int>(hash<string>{}(key) % size);
    }

    bool put(const string& key, int value) {
        int idx = index(key);
        for (int i = 0; i < size; ++i) {
            if (!table[idx].has_value() || table[idx]->first == key) {
                table[idx] = make_pair(key, value);
                return true;
            }
            idx = (idx + 1) % size;
        }
        return false;
    }

    optional<int> get(const string& key) const {
        int idx = index(key);
        for (int i = 0; i < size; ++i) {
            if (!table[idx].has_value()) return nullopt;
            if (table[idx]->first == key) return table[idx]->second;
            idx = (idx + 1) % size;
        }
        return nullopt;
    }
};

int main() {
    LinearProbeHash lp;
    lp.put("k1", 1);
    lp.put("k2", 2);
    auto a = lp.get("k1");
    auto b = lp.get("k9");
    cout << (a.has_value() ? to_string(*a) : "None") << "\n";
    cout << (b.has_value() ? to_string(*b) : "None") << "\n";
    return 0;
}
Main.java
public class Main {
    static class Entry {
        String key;
        int value;
        Entry(String key, int value) { this.key = key; this.value = value; }
    }

    static class LinearProbeHash {
        int size;
        Entry[] table;

        LinearProbeHash(int size) {
            this.size = size;
            this.table = new Entry[size];
        }

        LinearProbeHash() { this(11); }

        int index(String key) {
            return Math.floorMod(key.hashCode(), size);
        }

        boolean put(String key, int value) {
            int idx = index(key);
            for (int i = 0; i < size; i++) {
                if (table[idx] == null || table[idx].key.equals(key)) {
                    table[idx] = new Entry(key, value);
                    return true;
                }
                idx = (idx + 1) % size;
            }
            return false;
        }

        Integer get(String key) {
            int idx = index(key);
            for (int i = 0; i < size; i++) {
                if (table[idx] == null) return null;
                if (table[idx].key.equals(key)) return table[idx].value;
                idx = (idx + 1) % size;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        LinearProbeHash lp = new LinearProbeHash();
        lp.put("k1", 1);
        lp.put("k2", 2);
        System.out.println(lp.get("k1"));
        System.out.println(lp.get("k9"));
    }
}
main.py
class LinearProbeHash:
    def __init__(self, size=11):
        self.size = size
        self.table = [None] * size

    def _index(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        idx = self._index(key)
        for _ in range(self.size):
            if self.table[idx] is None or self.table[idx][0] == key:
                self.table[idx] = (key, value)
                return True
            idx = (idx + 1) % self.size
        return False

    def get(self, key):
        idx = self._index(key)
        for _ in range(self.size):
            if self.table[idx] is None:
                return None
            if self.table[idx][0] == key:
                return self.table[idx][1]
            idx = (idx + 1) % self.size
        return None

lp = LinearProbeHash()
lp.put("k1", 1)
lp.put("k2", 2)
print(lp.get("k1"))  # 1
print(lp.get("k9"))  # None
main.rs
#[derive(Clone)]
struct LinearProbeHash {
    size: usize,
    table: Vec<Option<(String, i32)>>,
}

impl LinearProbeHash {
    fn new(size: usize) -> Self {
        Self {
            size,
            table: vec![None; size],
        }
    }

    fn index(&self, key: &str) -> usize {
        let mut h: usize = 0;
        for b in key.as_bytes() {
            h = h.wrapping_mul(131).wrapping_add(*b as usize);
        }
        h % self.size
    }

    fn put(&mut self, key: &str, value: i32) -> bool {
        let mut idx = self.index(key);
        for _ in 0..self.size {
            if self.table[idx].is_none() {
                self.table[idx] = Some((key.to_string(), value));
                return true;
            }
            if let Some((k, _)) = &self.table[idx] {
                if k == key {
                    self.table[idx] = Some((key.to_string(), value));
                    return true;
                }
            }
            idx = (idx + 1) % self.size;
        }
        false
    }

    fn get(&self, key: &str) -> Option<i32> {
        let mut idx = self.index(key);
        for _ in 0..self.size {
            if self.table[idx].is_none() {
                return None;
            }
            if let Some((k, v)) = &self.table[idx] {
                if k == key {
                    return Some(*v);
                }
            }
            idx = (idx + 1) % self.size;
        }
        None
    }
}

fn main() {
    let mut lp = LinearProbeHash::new(11);
    lp.put("k1", 1);
    lp.put("k2", 2);
    println!("{:?}", lp.get("k1"));
    println!("{:?}", lp.get("k9"));
}

해시 충돌 처리 결과 버킷 상태 추적

오픈 어드레싱은 버킷 배열 안에서 충돌을 해결합니다.
메모리 지역성은 좋아질 수 있지만 클러스터링이 생기면 탐색 구간이 길어집니다.
삭제를 안정적으로 지원하려면 tombstone 정책이 필요합니다.

  • 평균 시간복잡도: O(1)
  • 최악 시간복잡도: O(N)
  • 공간복잡도: O(N)

해시 충돌 처리 적용 기준

충돌 전략 선택 시 다음을 기준으로 판단합니다.

  • 삭제 빈도가 높은가
  • 메모리 오버헤드를 허용할 수 있는가
  • 캐시 지역성이 중요한가
  • 최악 성능에 민감한 서비스인가

삭제가 잦고 구현 안정성이 중요하면 체이닝이 유리한 경우가 많습니다.

설계 상충 지점

충돌 해결 전략의 균형점입니다.

  • 체이닝: 구현 단순, 버킷 오버헤드 존재
  • 오픈 어드레싱: 배열 친화적, 삭제/클러스터링 관리 복잡
  • 해시 함수 단순화: 빠르지만 분포 악화 가능
  • 해시 함수 강화: 분포 개선 가능, 상수 비용 증가

속도만이 아니라 유지보수성과 장애 복구 난이도까지 함께 봐야 합니다.

충돌 로그로 보는 실수 포인트

해시 구조에서 자주 놓치는 반례입니다.

  • 키 정규화 누락(대소문자/공백)으로 충돌 증가
  • 로드 팩터 임계치 없이 계속 삽입
  • 오픈 어드레싱에서 삭제 후 탐색 경로 깨짐
  • 사용자 입력 키를 그대로 사용해 편향 분포 발생

반례 입력을 미리 설계하면 운영 장애 가능성을 크게 줄일 수 있습니다.

구현 품질 확인

해시 구현 리뷰에서 우선 확인할 항목입니다.

  • 동일 키 업데이트가 정상적으로 덮어쓰기 되는가
  • 충돌 버킷 길이가 비정상적으로 커지는 구간이 있는가
  • 로드 팩터 임계치와 재해시가 실제로 동작하는가

이 점검을 자동 테스트에 포함하면 장기 성능 퇴행을 빠르게 감지할 수 있습니다.

해시 연산 비용 모델 정리

입력 분포가 치우치면 같은 알고리즘이라도 성능 체감이 달라지므로, 판단 축을 데이터 특성과 함께 기록해 두는 편이 안전합니다.

전략평균최악공간비고
체이닝O(1)O(N)O(N)삭제 구현 용이
오픈 어드레싱O(1)O(N)O(N)클러스터링 주의

평균 O(1)은 로드 팩터 관리와 분포 가정이 충족될 때만 유지됩니다.

해시 인덱스 끝점 참고점

  • 해시 함수와 동등성 비교 규칙(__hash__, __eq__)은 반드시 일관돼야 합니다.
  • 버킷 수 변경 시 전체 재해시 비용을 배치 정책과 함께 설계해야 합니다.
  • 성능 측정은 랜덤 입력과 편향 입력을 분리해 실행해야 합니다.
  • 디버깅 시 버킷 길이 분포를 함께 기록하면 병목 위치를 빨리 찾을 수 있습니다.

해시 구현 전후 점검 목록

  • 충돌 전략(체이닝/오픈 어드레싱) 선택 판단 이유를 명시했는가
  • 로드 팩터 임계치와 재해시 정책을 정의했는가
  • 삭제 후에도 조회 경로가 보존되는지 테스트했는가
  • 편향 입력 반례에서 성능 퇴행을 측정했는가

해시 충돌 전략 정리

해시 테이블의 성능은 해시 함수 하나가 아니라 충돌 전략 전체 설계에서 나옵니다.
충돌을 전제로 모델링하면, 평균 성능과 최악 안정성을 함께 확보할 수 있습니다.

스택/큐 실전 패턴과 디버깅 포인트

이전 페이지

맵과 셋을 활용한 빈도 기반 패턴

다음 페이지

목차

핵심 개념: 해시와 충돌 처리
해시 설계가 실무에서 중요한 이유
충돌 케이스 오답 재현으로 검증하기
체이닝 기반 해시 구현
해시 충돌 처리 결과 해시 충돌 징후 확인
단순 선형 탐사(오픈 어드레싱)
해시 충돌 처리 결과 버킷 상태 추적
해시 충돌 처리 적용 기준
설계 상충 지점
충돌 로그로 보는 실수 포인트
구현 품질 확인
해시 연산 비용 모델 정리
해시 인덱스 끝점 참고점
해시 구현 전후 점검 목록
해시 충돌 전략 정리