해시 테이블과 캐시 충돌: 벤치마크

해시 테이블: 실제 프로젝트에서 캐시 미스 피하기

해시 테이블은 O(1) 조회를 약속하지만, 실제로는 캐시 미스로 인해 선형 배열 스캔에 밀리는 경우가 많습니다. 컴파일러 옵티마이저의 심볼 테이블에서 500개 엔트리가 1024개 버킷에 분포된 상황에서, 500만 명령어 동안 120만 건의 캐시 미스가 발생했습니다. 평범한 배열로 전환하니 3배 빨라졌습니다. 원인? 캐시 라인을 쫓아내는 접근 패턴입니다.

기본 구현과 충돌

단순 직접 매핑 해시 테이블은 충돌 때문에 확장성이 떨어집니다. 기본 코드 예시:

typedef struct {
    char *key;
    int value;
} entry_t;

#define TABLE_SIZE 1024

entry_t *table[TABLE_SIZE];

int hash(const char *key) {
    unsigned int h = 0;
    while (*key) {
        h = h * 31 + *key++;
    }
    return h % TABLE_SIZE;
}

삽입과 조회에는 메모리 할당과 문자열 비교가 필요하지만, 충돌 처리가 없으면 테이블이 무용지물입니다.

충돌 해결 전략

서로 다른 키가 같은 인덱스로 해시될 때 충돌이 발생합니다. 주요 접근법 두 가지:

체이닝(Chaining)

각 버킷당 연결 리스트로 메모리 접근을 분산:

typedef struct entry {
    char *key;
    int value;
    struct entry *next;
} entry_t;

void insert(const char *key, int value) {
    int index = hash(key);
    entry_t *entry = malloc(sizeof(entry_t));
    entry->key = strdup(key);
    entry->value = value;
    entry->next = table[index];
    table[index] = entry;
}

조회 시 포인터를 따라가며 각 단계마다 캐시 미스 위험이 있습니다.

오픈 어드레싱(Open Addressing)

연속 배열에서 선형 프로빙으로 지역성을 유지:

typedef struct {
    char *key;
    int value;
    int occupied;
} entry_t;

entry_t table[TABLE_SIZE];

void insert(const char *key, int value) {
    int index = hash(key);
    while (table[index].occupied) {
        index = (index + 1) % TABLE_SIZE;
    }
    table[index].key = strdup(key);
    table[index].value = value;
    table[index].occupied = 1;
}

순차 접근으로 미스를 최소화: 첫 캐시 라인 로드로 7~8개 요소 커버.

| 전략 | 조회당 캐시 미스 | 지역성 |

|----------------|-------------------|--------|

| 체이닝 | 3–10 (체인 길이 3) | 나쁨 |

| 프로빙 | 1–2 | 좋음 |

캐시 미스 분석

체이닝에서 각 노드는 별도 로드: 버킷(1 미스), 엔트리(2–3), 다음 포인터(1). 총 최대 10 미스.

프로빙은 전체 캐시 라인을 로드해 후속 프로빙이 캐시 히트. 미스 3–5배 적음.

벤치마크: 1000 삽입, 10,000 조회 (로드 팩터 0.5, 2048 버킷):

• 체이닝: 삽입 450k 사이클, 조회 2.1M 사이클, 45k 미스
• 프로빙: 삽입 180k 사이클, 조회 650k 사이클, 12k 미스

프로빙이 전체 3.2배 빠름.

해시 함수 품질

key[0] % size 같은 형편없는 해시는 첫 문자로 키 클러스터링, 평균 체인 길이 38.5.

FNV-1a는 균등 분포:

uint32_t fnv1a_hash(const char *key) {
    uint32_t hash = 2166136261u;
    while (*key) {
        hash ^= (uint8_t)*key++;
        hash *= 16777619u;
    }
    return hash;
}

특화 해시:

• 정수: return key;
• 포인터: (uintptr_t >> 3) * 2654435761u

벤치마크: FNV-1a 평균 체인 길이 0.98 vs 형편없는 해시 38.5.

로드 팩터와 리사이징

로드 팩터 = 엔트리 / 버킷.

• 체이닝: >1.0 OK but 성능 저하
• 프로빙: <0.7–0.8 유지

0.9에서 평균 10.5 프로빙; 0.95에서 20.5.

0.7에서 리사이즈 (2배 크기, 누적 O(1)):

void insert(const char *key, int value) {
    if (count >= table_size * 0.7) {
        resize_table();
    }
    // 삽입
}

캐시 최적화 구조

• 오픈 어드레싱 + 2의 제곱 크기 (해시 & 마스크 대신 %).
• 빽빽한 패킹:

typedef struct {
    uint32_t hash;
    uint32_t key;
    uint32_t value;
} entry_t;  // 12바이트, 캐시 라인당 5개

• 대용량 페이로드용 키/값 분리.
• SIMD 프로빙 (AVX2로 8개 요소 동시 검사).

로빈 후드 해싱

프로빙 변형: 삽입 시 프로브 거리가 낮은 요소에서 "훔쳐" 균형.

예: key4 (해시=1)가 key2 (거리=1 > 0)를 밀어냄. 프로브 길이 분산 최소화.

핵심 요약

• 선형 프로빙 오픈 어드레싱이 체이닝보다 3–5배 캐시 효율적.
• 품질 좋은 해시(FNV-1a)가 충돌 40배 줄임.
• 로드 팩터 <0.7 + 2배 리사이즈 = 누적 O(1).
• 빽빽한 패킹 + 2의 제곱 크기 = 미스 최소.
• 로빈 후드 해싱으로 프로브 분포 최적화.

— Editorial Team