Hash table은 key-value 데이터를 빠르게 찾기 위한 자료구조입니다. key를 hash function에 넣어 hash 값을 만들고, 그 값을 기반으로 내부 배열의 위치를 결정합니다. 이상적으로는 key로 바로 위치를 찾아가므로 검색, 삽입, 삭제가 평균 O(1)에 가깝습니다.
하지만 서로 다른 key가 같은 위치로 매핑되는 collision이 생길 수 있고, 이를 chaining이나 open addressing 같은 방식으로 처리합니다. 최악의 경우 collision이 많으면 성능이 O(n)에 가까워질 수 있습니다.
꼬리질문
조금 더 깊게 물어본다면
답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.
Collision은 무엇이고 왜 불가피한가요?
서로 다른 key가 같은 bucket index로 매핑되는 것이 collision입니다. hash function의 출력 범위(bucket 수)는 유한하지만 key 공간은 무한하기 때문에 비둘기집 원리에 의해 collision은 피할 수 없습니다.
collision이 많아지면 O(1) 기대 성능이 O(n)에 가까워집니다. 그래서 hash function의 분산 품질과 load factor 관리가 중요합니다.
Chaining은 어떻게 동작하나요?
같은 bucket에 여러 entry를 linked list로 연결해 저장합니다. collision이 나도 bucket 안의 list에 추가하면 되고, 삭제가 간단하며 load factor가 1을 넘어도 동작합니다.
단점은 포인터 오버헤드와 cache 비친화성입니다. linked list의 각 노드가 메모리에 흩어져 있어 CPU cache miss가 늘어납니다. Java의 HashMap이 기본적으로 chaining을 쓰고, bucket의 list가 일정 크기를 넘으면 balanced tree로 전환합니다.
Open addressing은 chaining과 어떻게 다른가요?
collision이 나면 다음 빈 bucket을 찾아 같은 배열 안에 저장합니다. 포인터 없이 배열만 씁니다.
탐사 방식에 따라 나뉩니다.
linear probing: 다음 칸 순서로 탐색합니다. 구현이 단순하고 cache 친화적이지만 값이 연속으로 몰리는 primary cluster가 생기기 쉽습니다.
quadratic probing: 1, 4, 9, 16... 칸씩 건너뜁니다. primary cluster를 줄이지만 모든 bucket을 탐색하지 못할 수 있습니다.
double hashing: 두 번째 hash function으로 탐사 간격을 결정합니다. 분산이 좋지만 계산 비용이 있습니다.
open addressing은 load factor가 높아질수록 성능이 급격히 나빠져 일반적으로 0.7-0.75를 넘기 전에 resizing합니다.
Load factor와 resizing은 어떻게 관리하나요?
load factor = 저장된 entry 수 / bucket 수입니다. load factor가 올라갈수록 collision 확률이 높아집니다.
임계값(보통 0.75)을 넘으면 bucket 수를 늘린 새 배열을 만들고 기존 entry를 모두 rehash합니다. Java HashMap의 기본값이 load factor 0.75, 초기 용량 16입니다. rehashing은 O(n) 비용이지만 분할 상환 분석으로 개별 삽입의 평균 비용은 O(1)에 가깝습니다.
좋은 hash function의 조건은 무엇인가요?
빠르고, 출력이 고르게 분산되어야 합니다.
분산이 나쁘면 특정 bucket에 값이 몰려 O(n)에 가까워집니다. 입력이 조금만 달라도 출력이 크게 달라지는 avalanche effect도 중요합니다. MD5, SHA 같은 암호화 hash는 이 성질이 강하지만 연산이 무거워 hash table에는 MurmurHash, xxHash 같은 비암호화 hash를 주로 씁니다.
악의적인 입력으로 의도적으로 collision을 만드는 HashDoS 공격을 막기 위해 Java, Python 등은 hash 계산에 무작위 seed를 섞습니다.
HashMap과 TreeMap, 어떻게 선택하나요?
HashMap은 hash table 기반으로 평균 O(1) 탐색/삽입/삭제입니다. 순서가 보장되지 않습니다.
TreeMap은 Red-Black Tree 기반으로 O(log n)이지만 key가 정렬된 순서로 유지됩니다. 범위 조회(subMap, headMap, tailMap)나 정렬된 순서 순회가 필요할 때 씁니다.
단순 조회가 목적이면 HashMap, 정렬이나 범위 연산이 필요하면 TreeMap이 적합합니다.
최악의 경우 O(n)이 되는 상황은?
두 경우가 있습니다.
모든 key가 같은 bucket으로 매핑될 때입니다. hash function이 특정 패턴의 입력에 편향되거나, 악의적인 입력으로 의도적으로 collision을 만들면 chaining의 list나 open addressing의 탐사 길이가 O(n)이 됩니다. Java는 이를 위해 bucket list를 일정 크기 초과 시 Red-Black Tree로 전환합니다.
resizing이 일어나는 순간에도 O(n) 비용이 발생합니다. 용량을 미리 지정하거나 incremental resizing으로 비용을 분산하는 방식으로 대응할 수 있습니다.
부가 설명
const map = new Map();map.set("name", "Joon");map.get("name"); // "Joon"
JavaScript의 Map은 언어 수준에서 key-value collection을 제공하지만, 내부적으로 hash table과 비슷한 아이디어를 떠올릴 수 있습니다.
hash table의 핵심은 “key를 비교해서 하나씩 찾지 않고, 계산으로 위치를 찾는다”는 점입니다. 이때 hash function이 값을 고르게 분산해야 collision이 줄어듭니다.
평균 O(1)은 collision이 잘 분산되고 resizing이 적절히 이뤄진다는 전제가 있을 때의 기대 성능입니다.
한 줄 정리
hash table은 key를 hash로 위치에 매핑해 평균적으로 빠른 key-value 접근을 제공하는 자료구조입니다.