해시 테이블

Q: 해시 테이블의 시간 복잡도는 어떻게 되나요?

해시 함수가 키를 고르게 분산하고 적재율이 낮게 유지될 때 삽입, 조회, 삭제는 평균 `O(1)`입니다. 최악의 경우 - 모든 키가 하나의 버킷으로 충돌하는 경우 - `O(n)`으로 저하되므로 좋은 해시 함수와 크기 조정이 중요합니다.

Q: 이진 탐색 트리 대신 해시 테이블을 언제 사용해야 하나요?

정확 일치 조회만 필요하고 순서 요구 사항 없이 평균 `O(1)` 속도를 원할 때 해시 테이블을 사용하세요. 정렬된 키, 범위 질의, 선행자/후행자 조회가 필요할 때는 균형 이진 탐색 트리를 사용하세요. 이는 해시 테이블이 효율적으로 할 수 없습니다. BST는 보장된 `O(log n)` 연산을 제공하는 반면, 해시 테이블은 그 보장을 더 빠른 평균 성능과 맞바꿉니다.

마지막 업데이트 2026년 7월 1일

해시 테이블은 항목을 버킷 배열에 저장합니다. 키를 배치하거나 찾으려면 키를 해시 함수에 통과시키고 그 결과를 버킷 수로 나눈 나머지를 취합니다. 이렇게 하면 O(1)에 버킷 인덱스를 얻습니다. 위의 재생을 누르면 각 키가 버킷으로 해싱되어 저장되고, 이어서 조회가 올바른 버킷으로 바로 이동하는 모습을 볼 수 있습니다.

두 키가 같은 버킷에 들어가면(충돌) 이 시각화는 분리 연결법을 사용합니다. 각 버킷은 작은 리스트를 보유하고, 충돌한 키는 거기에 추가됩니다. 테이블이 너무 가득 차지 않고(낮은 적재율) 해시가 키를 잘 분산하는 한, 체인은 짧게 유지되며 삽입, 조회, 삭제는 평균적으로 O(1)입니다.

시간 복잡도

연산	평균	최악의 경우
삽입	O(1)	O(n) (모든 키가 충돌)
조회	O(1)	O(n)
삭제	O(1)	O(n)
공간	O(n)	O(n)

핵심 개념

용어	의미
해시 함수	키를 버킷 인덱스에 매핑
충돌	두 키가 같은 버킷에 들어감
분리 연결법	각 버킷이 충돌한 항목들의 리스트를 보유
개방 주소법	대안: 다음 빈 슬롯을 탐사
적재율	항목 수 / 버킷 수 - 크기 조정을 결정

예제 풀이

hash(k) = k % 7을 사용하여 키 20, 34, 9, 13을 버킷이 7개인 테이블에 삽입:

단계	구조	동작
`20` 삽입	버킷 6: `[20]`	`20 % 7 = 6`, 버킷 6 비어 있음, `20` 저장
`34` 삽입	버킷 6: `[20, 34]`	`34 % 7 = 6`, `20`과 충돌, `34`를 체인에 추가
`9` 삽입	버킷 2: `[9]`	`9 % 7 = 2`, 버킷 2 비어 있음, `9` 저장
`13` 삽입	버킷 6: `[20, 34, 13]`	`13 % 7 = 6`, 충돌, `13`을 버킷 6의 체인에 추가
`34` 조회	버킷 6: `[20, 34, 13]`	`34 % 7 = 6`, 체인 탐색: `20` 아님, `34` 일치 - 찾음

해시 테이블을 사용해야 할 때

사용할 때	피해야 할 때
키 기준 삽입, 조회, 삭제를 평균 `O(1)`로 해야 할 때	키를 정렬된 순서로 유지해야 할 때 - 균형 BST 사용
키에 유용한 순서가 없고 정확 일치 멤버십만 확인할 때	범위 질의나 가장 가까운 키 조회가 필요할 때
버킷과 낮은 적재율을 위해 약간의 추가 메모리를 감당할 수 있을 때	메모리가 극도로 부족하고 모든 바이트가 중요할 때
키 타입에 대해 좋은 해시 함수가 존재할 때	최악의 경우 지연 시간이 제한되어야 할 때 - 충돌이 `O(n)`으로 만듦

Hash Table 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Hash Table 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Hash Table 코드Python
1class HashTable:2    def __init__(self, size=8):3        self.size = size4        self.buckets = [[] for _ in range(size)]5
6    def _index(self, key):7        # Hash the key to a bucket; different keys can collide8        return sum(ord(ch) for ch in key) % self.size9
10    def set(self, key, value):11        bucket = self.buckets[self._index(key)]12        for i, (k, _) in enumerate(bucket):13            if k == key:14                bucket[i] = (key, value)  # update existing key15                return16        bucket.append((key, value))  # chain on collision17
18    def get(self, key):19        for k, v in self.buckets[self._index(key)]:20            if k == key:21                return v22        raise KeyError(key)23
24    def delete(self, key):25        bucket = self.buckets[self._index(key)]26        for i, (k, _) in enumerate(bucket):27            if k == key:28                del bucket[i]29                return30        raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple  ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple  ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Hash Table 코드JavaScript
1class HashTable {2    constructor(size = 8) {3        this.size = size;4        this.buckets = Array.from({ length: size }, () => []);5    }6
7    // Fold character codes into a bucket index8    hash(key) {9        let h = 0;10        for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11        return h;12    }13
14    set(key, value) {15        const bucket = this.buckets[this.hash(key)];16        const pair = bucket.find(([k]) => k === key);17        if (pair) pair[1] = value;18        else bucket.push([key, value]); // Separate chaining on collision19    }20
21    get(key) {22        const bucket = this.buckets[this.hash(key)];23        const pair = bucket.find(([k]) => k === key);24        return pair ? pair[1] : undefined;25    }26
27    delete(key) {28        const bucket = this.buckets[this.hash(key)];29        const index = bucket.findIndex(([k]) => k === key);30        if (index === -1) return false;31        bucket.splice(index, 1);32        return true;33    }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Hash Table 코드Java
1public class Main {2    static class Entry {3        String key; int value;4        Entry next; // chain for keys sharing a bucket5        Entry(String key, int value) { this.key = key; this.value = value; }6    }7
8    static final int CAPACITY = 8;9    static Entry[] buckets = new Entry[CAPACITY];10
11    static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13    static void put(String key, int value) {14        int i = index(key);15        for (Entry e = buckets[i]; e != null; e = e.next) {16            if (e.key.equals(key)) { e.value = value; return; }17        }18        Entry entry = new Entry(key, value);19        entry.next = buckets[i]; // prepend to the chain20        buckets[i] = entry;21    }22
23    static Integer get(String key) {24        for (Entry e = buckets[index(key)]; e != null; e = e.next) {25            if (e.key.equals(key)) return e.value;26        }27        return null;28    }29
30    static void remove(String key) {31        int i = index(key);32        Entry prev = null;33        for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34            if (e.key.equals(key)) {35                if (prev == null) buckets[i] = e.next;36                else prev.next = e.next;37                return;38            }39        }40    }41
42    public static void main(String[] args) {43        put("apple", 3); put("banana", 7); put("cherry", 5);44        System.out.println("apple -> " + get("apple"));45        put("apple", 10); // update in place46        System.out.println("apple -> " + get("apple"));47        remove("banana");48        System.out.println("banana -> " + get("banana"));49    }50}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Hash Table 코드C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6    static constexpr int CAPACITY = 8;7    // Separate chaining: each bucket holds (key, value) pairs8    std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10    size_t hash(const std::string& key) const {11        size_t h = 0;12        for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13        return h % CAPACITY;14    }15
16    void set(const std::string& key, int value) {17        auto& bucket = buckets[hash(key)];18        for (auto& entry : bucket) {19            if (entry.first == key) {20                entry.second = value;  // update existing key21                return;22            }23        }24        bucket.push_back({key, value});25    }26
27    const int* get(const std::string& key) const {28        for (const auto& entry : buckets[hash(key)]) {29            if (entry.first == key) return &entry.second;30        }31        return nullptr;32    }33
34    void erase(const std::string& key) {35        auto& bucket = buckets[hash(key)];36        for (size_t i = 0; i < bucket.size(); ++i) {37            if (bucket[i].first == key) {38                bucket.erase(bucket.begin() + i);39                return;40            }41        }42    }43};44
45int main() {46    HashTable table;47    table.set("apple", 3);48    table.set("banana", 7);49    table.set("apple", 4);  // overwrites the old value50    for (const std::string& key : {"apple", "banana", "grape"}) {51        const int* value = table.get(key);52        if (value != nullptr) std::cout << key << " = " << *value << "\n";53        else std::cout << key << " not found\n";54    }55    table.erase("banana");56    std::cout << "banana after erase: "57              << (table.get("banana") ? "found" : "not found") << "\n";58    return 0;59}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Hash Table 코드C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9    char key[16];10    int value;11    struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17    unsigned int h = 5381;  // djb2, then modulo the bucket count18    for (; *key; key++) h = h * 33 + (unsigned char)*key;19    return h % CAPACITY;20}21
22void set(const char* key, int value) {23    unsigned int i = hash(key);24    for (Entry* e = buckets[i]; e != NULL; e = e->next) {25        if (strcmp(e->key, key) == 0) {26            e->value = value;  // update existing key27            return;28        }29    }30    Entry* e = malloc(sizeof(Entry));31    strcpy(e->key, key);32    e->value = value;33    e->next = buckets[i];34    buckets[i] = e;35}36
37int* get(const char* key) {38    for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39        if (strcmp(e->key, key) == 0) return &e->value;40    }41    return NULL;42}43
44void removeKey(const char* key) {45    Entry** link = &buckets[hash(key)];46    while (*link != NULL) {47        if (strcmp((*link)->key, key) == 0) {48            Entry* old = *link;49            *link = old->next;50            free(old);51            return;52        }53        link = &(*link)->next;54    }55}56
57void printBuckets(void) {58    for (int i = 0; i < CAPACITY; i++) {59        printf("bucket %d:", i);60        for (Entry* e = buckets[i]; e != NULL; e = e->next) {61            printf(" (%s=%d)", e->key, e->value);62        }63        printf("\n");64    }65}66
67int main(void) {68    set("apple", 3);69    set("banana", 7);70    set("apple", 4);  // overwrites the old value71    set("grape", 9);72    printBuckets();73    int* value = get("apple");74    printf("get(apple): %d\n", value ? *value : -1);75    removeKey("banana");76    printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77    return 0;78}
이 코드를 C 플레이그라운드에서 실행하기

해시 테이블 자주 묻는 질문

해시 충돌이란 무엇이며 어떻게 해결하나요?

충돌은 서로 다른 두 키가 같은 버킷으로 해싱될 때 발생합니다. 두 가지 일반적인 해결책은 분리 연결법(각 버킷이 리스트를 보유하고 충돌한 키를 추가 - 여기서 보여줌)과 개방 주소법(배열에서 다음 빈 슬롯을 탐사)입니다. 둘 다 조회의 정확성을 유지하지만, 메모리 배치와 높은 부하에서의 성능이 다릅니다.

해시 테이블의 시간 복잡도는 어떻게 되나요?

해시 함수가 키를 고르게 분산하고 적재율이 낮게 유지될 때 삽입, 조회, 삭제는 평균 O(1)입니다. 최악의 경우 - 모든 키가 하나의 버킷으로 충돌하는 경우 - O(n)으로 저하되므로 좋은 해시 함수와 크기 조정이 중요합니다.

적재율이란 무엇인가요?

적재율은 저장된 항목 수를 버킷 수로 나눈 값입니다. 이 값이 커지면 체인이 길어지고 연산이 느려지므로, 대부분의 해시 테이블은 0.75 같은 임계값을 넘으면 크기를 조정합니다(더 큰 배열로 재해싱).

이진 탐색 트리 대신 해시 테이블을 언제 사용해야 하나요?

정확 일치 조회만 필요하고 순서 요구 사항 없이 평균 O(1) 속도를 원할 때 해시 테이블을 사용하세요. 정렬된 키, 범위 질의, 선행자/후행자 조회가 필요할 때는 균형 이진 탐색 트리를 사용하세요. 이는 해시 테이블이 효율적으로 할 수 없습니다. BST는 보장된 O(log n) 연산을 제공하는 반면, 해시 테이블은 그 보장을 더 빠른 평균 성능과 맞바꿉니다.

분리 연결법과 개방 주소법의 차이는 무엇인가요?

분리 연결법은 충돌한 키를 버킷별 리스트에 저장하므로, 한 버킷이 많은 항목을 보유할 수 있고 테이블이 진짜로 가득 차는 일이 없습니다. 개방 주소법은 모든 것을 배열 자체에 보관하고 충돌 시 다음 빈 슬롯을 탐사하는데, 캐시 친화적이지만 적재율이 1에 가까워지면 급격히 저하되고 삭제를 신중히 처리해야 합니다. 연결법은 더 높은 적재율을 허용하고, 개방 주소법은 메모리를 더 조밀하게 사용합니다.

해시 테이블이 키를 삽입 순서나 정렬 순서로 유지한다고 왜 믿을 수 없나요?

해시 함수는 군집을 피하기 위해 키를 버킷 전체에 의도적으로 흩뿌리므로, 반복 순서는 삽입 순서나 정렬 순서가 아니라 버킷 배치를 반영합니다. 순서가 필요하면 순서 있는 맵/트리나 삽입 순서를 보존하는 맵 같은 구조를 사용하세요(예: 파이썬의 dict는 삽입 순서를 보존하지만, 이는 언어의 보장이지 해시 테이블 본연의 속성이 아닙니다). 언어가 명시적으로 약속하지 않는 한, 반복 순서가 키를 삽입한 방식과 일치한다고 절대 가정하지 마세요.