사람들이 해시 테이블을 설명할 때 가장 자주 하는 말은 “평균 O(1)이라서 빠르다”입니다. 맞는 말이지만, 이 말만으로는 왜 빠른지 감이 잘 안 옵니다. 이 글에서는 practical scene부터 시작해서 버킷, 해시 함수, 충돌, average O(1), 리사이징이 어떻게 연결되는지 직관적으로 정리해보겠습니다.
핵심은 의외로 단순합니다. 해시 테이블은 데이터를 공중에서 꺼내는 마법이 아니라, 키를 배열의 위치 힌트로 바꿔서 탐색 범위를 줄이는 방식입니다. 그래서 배열과 연결 리스트만 따로 보면 설명이 부족하고, 이 둘을 묶는 추상화까지 같이 봐야 이해가 됩니다.
먼저 장면부터: 사물함은 빠르고 명단 대조는 느리다
학생 이름과 사물함 번호를 저장한다고 해보겠습니다. 배열만 있으면 7번 칸처럼 번호로는 빨리 갈 수 있지만, “민수”라는 이름으로는 하나씩 비교해야 할 수 있습니다. 연결 리스트도 결국 앞에서부터 따라가야 하니, 원하는 이름을 곧바로 찾기 어렵습니다.
해시 테이블은 여기서 “민수는 12번 버킷 쪽부터 보자” 같은 힌트를 먼저 줍니다. 즉, 전체를 훑는 대신 처음부터 작은 후보 구역으로 점프하게 만듭니다. 이 점프 능력이 바로 속도의 출발점입니다.
해시 테이블은 배열을 버린 구조가 아니다
해시 테이블은 대개 배열을 바탕으로 동작합니다. 차이는 배열이 인덱스를 직접 받는다면, 해시 테이블은 키를 받아 인덱스로 바꾼다는 점입니다. 이 변환 규칙이 바로 해시 함수입니다.
OpenDSA는 해싱을 키를 테이블의 위치로 매핑하는 과정으로 설명합니다. 이 한 줄만 제대로 잡아도 해시 테이블은 훨씬 덜 추상적으로 느껴집니다.
해시 테이블이 빠른 이유는 키를 배열의 위치 힌트로 바꿔서 처음부터 탐색 범위를 줄이기 때문입니다.
버킷을 이해하면 절반은 끝난다
버킷은 거창한 개념이 아닙니다. 그냥 “이 키들이 일단 들어갈 후보 칸”이라고 생각하면 됩니다. 버킷이 8개라면 해시 함수는 어떤 키든 0부터 7 사이 위치로 보냅니다.
- "apple" → 2번 버킷
- "banana" → 5번 버킷
- "grape" → 2번 버킷
여기서 `apple`과 `grape`가 같은 버킷으로 가면 충돌이 생깁니다. 중요한 점은 해시 테이블이 충돌이 없어서 빠른 구조가 아니라, 충돌이 있어도 전체가 아니라 작은 버킷 안에서만 해결하려는 구조라는 점입니다.
배열과 연결 리스트만으로는 설명이 부족한 이유
해시 테이블을 “배열이다”라고만 말하면 왜 문자열 키를 빠르게 찾는지 설명이 안 됩니다. 반대로 “버킷마다 연결 리스트를 둔다”라고만 말하면 왜 평균적으로 빠른지 부족합니다.
핵심은 둘의 조합입니다. 배열은 큰 탐색 범위를 잘게 나누는 뼈대를 제공하고, 버킷 안의 충돌 해결 구조는 같은 칸에 모인 원소를 안전하게 처리합니다. 그래서 해시 테이블은 구현 부품보다 키를 위치 힌트로 바꾸는 추상화로 이해하는 편이 더 정확합니다.
아주 단순한 코드로 보는 버킷과 충돌
아래 코드는 설명용으로 단순화한 작은 해시 테이블입니다. 실제 라이브러리 구현과 똑같지는 않지만, 버킷과 충돌 감각을 보기에는 충분합니다.
buckets = [[], [], [], []]
def simple_hash(key):
return len(key) % 4
def put(key, value):
idx = simple_hash(key)
bucket = buckets[idx]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(key):
idx = simple_hash(key)
bucket = buckets[idx]
for k, v in bucket:
if k == key:
return v
return None
put("cat", 1)
put("dog", 2)
put("lion", 3)
print(buckets)
print(get("dog"))여기서 `cat`과 `dog`는 같은 버킷으로 갑니다. 그래도 `get(“dog”)`는 전체를 다 보지 않습니다. 일단 해당 버킷으로 점프하고, 그 안에서만 비교합니다. 바로 이 점프가 해시 테이블의 속도 감각입니다.
해시 함수의 역할: 정답이 아니라 구역 힌트
해시 함수는 완벽한 위치를 알려주는 마법 함수라기보다, 키들을 가능한 한 고르게 버킷에 퍼뜨리는 규칙에 가깝습니다. OpenDSA도 실용적인 해시 함수는 버킷 범위 안의 값을 반환해야 하고, 가능하면 균등하게 분산시켜야 한다고 설명합니다.
좋은 해시 함수는 충돌 0개를 약속하지 않습니다. 대신 한쪽 버킷에만 몰리지 않게 도와줍니다. 그래야 각 버킷 안에서 확인해야 할 개수가 작게 유지되고, 조회도 짧게 끝납니다.
충돌
충돌은 서로 다른 키가 같은 버킷으로 갈 때 생깁니다. 키의 세계는 넓고 버킷 수는 유한하기 때문에, 현실적인 해시 테이블에서 충돌을 완전히 없애는 것은 보통 기대하지 않습니다.
그래서 중요한 질문은 충돌이 있느냐가 아니라, 충돌이 생겼을 때도 비용이 감당 가능한가입니다. 해시 테이블은 이 질문에 꽤 잘 답하도록 설계된 구조입니다.
average O(1)은 왜 average인가
Oracle의 HashMap 문서는 해시 함수가 원소를 버킷에 적절히 분산시킨다는 가정 아래 `get`과 `put`이 constant-time performance를 제공한다고 설명합니다. 즉, 항상 한 번에 찾는다는 뜻이 아니라 대부분의 조회가 아주 작은 구역에서 끝나도록 기대한다는 뜻에 가깝습니다.
반대로 키가 한 버킷에 심하게 몰리면 최악에는 거의 선형 탐색처럼 느려질 수 있습니다. 그래서 해시 테이블 설명은 보통 평균 O(1)과 최악 O(n)을 함께 말합니다.
해시 테이블의 빠름은 절대 보장이 아니라, 잘 분산되도록 관리된 평균 성능 약속이라고 보는 편이 정확합니다.
리사이징
원소를 계속 넣다 보면 버킷 하나당 들어 있는 원소 수도 서서히 늘어납니다. 그러면 충돌 비용이 커질 수 있습니다. 그래서 해시 테이블은 어느 정도 차면 버킷 수를 늘리고 다시 배치합니다.
Oracle 문서는 capacity를 버킷 수, load factor를 얼마나 차기 전까지 늘리지 않을지의 기준으로 설명하고, 임계치를 넘으면 rehash로 내부 구조를 다시 만든다고 설명합니다. 직관적으로는 좁아진 책상을 더 큰 책상으로 바꾸고 물건을 다시 펼쳐 놓는 과정에 가깝습니다.
그 순간만 보면 비용이 들지만, 덕분에 이후 조회와 삽입이 다시 짧아집니다. 즉 리사이징은 느려진 뒤 뒤늦게 고치는 일이 아니라, 평균 성능을 지키기 위한 예방 조치입니다.
왜 이 구조를 추상화로도 봐야 할까
해시 테이블은 단지 버킷 여러 개가 있는 컨테이너가 아닙니다. 더 본질적으로는, 어떤 키가 오더라도 “어디부터 찾으면 될지”를 먼저 알려주는 방식입니다. 그래서 Java의 `HashMap`, Python의 `dict`, C++의 `unordered_map`처럼 여러 언어에서 비슷한 철학이 반복됩니다.
즉 우리가 기억해야 할 것은 O(1) 슬로건 하나보다, 키 기반 조회를 평균적으로 싸게 만들기 위해 배열, 해시 함수, 충돌 해결, 리사이징을 묶어 둔 아이디어라는 점입니다. 이 관점이 잡히면 해시 테이블은 더 이상 마법처럼 보이지 않습니다.
한 번에 정리
- 해시 테이블은 배열 위에서 동작한다
- 해시 함수가 키를 버킷 위치 힌트로 바꾼다
- 충돌은 자연스럽게 생기며, 중요한 것은 충돌을 감당하는 방식이다
- 그래서 전체 탐색 대신 작은 버킷 안의 탐색으로 줄일 수 있다
- 원소가 너무 몰리면 리사이징으로 다시 퍼뜨려 평균 성능을 지킨다
결국 해시 테이블이 빠른 이유는 충돌이 없어서도 아니고, 언제나 한 번에 찾아서도 아닙니다. 대부분의 경우 전체를 훑지 않고 작은 후보 구역만 보게 만들기 때문입니다.
같이 보면 좋은 글
자바 HashMap과 TreeMap 차이: 정렬, 순서, 성능 기준으로 고르기
