[자료구조] Hash Table (해시 테이블) 알아보기

이미지 최적화 공부를 하다가 문득 ‘데이터를 효율적으로 저장하고 꺼내는 방법’이 얼마나 중요한지 깨달았다.
특히, 브라우저 캐시나 CDN이 내부적으로 어떻게 이미지를 빠르게 찾아내는지를 이해하려면 자료구조의 기본 원리를 알아야 했다.
그중에서도 해시 테이블(Hash Table) 은 데이터를 ‘빠르게 찾는 구조’의 대표적인 예라서, 이번엔 그 원리를 정리해보기로 했다.

---

1. 해시 테이블 이란?

해시 테이블(Hash Table) 은 데이터를 (Key, Value) 형태로 저장하는 자료구조이다.

핵심 원리는 다음과 같다.

데이터를 단순히 순서대로 저장하는 대신, Key 값을 해시 함수(Hash Function) 에 넣어
배열의 인덱스(Index) 로 변환하고, 그 인덱스 위치(=버킷, 슬롯 이라고 부른다.)에 값을 저장한다.

 

즉, 데이터를 직접 찾는 것이 아니라, 데이터의 ‘주소’를 계산해서 바로 접근하는 구조 이다.

이 덕분에 별도의 탐색 과정을 거치지 않고 한 번의 계산으로 원하는 데이터를 얻을 수 있다.

2. 동작 원리

예를 들어 "John Smith" 씨의 전화번호를 저장하려고 할때 

(Key, Value) = ("John Smith", "521-1234") 를 해시 테이블에 저장한다면 어떤 과정을 통해 저장될까?

 

1. Key에 해시 함수 적용

Key를 해시 함수에 입력하여 고유한 숫자(해시값, hash value)를 얻는다.

이 hash_function()은 문자열 "John Smith"를 일정한 규칙으로 숫자로 변환한다.

index = hash_function("John Smith") % 16

여기서 % 16은 테이블의 크기(버킷 개수)에 맞게 인덱스를 조정하는 과정이다.

이렇게 하면 hash_value가 아무리 커도 0~15 사이의 숫자가 나와서 16개의 버킷 중 하나에 정확히 매핑된다.

 

예들들어 index = 5가 나왔다고 해보자.

 

2. 해당 인덱스 위치에 값을 저장

table[5] = "521-1234"

이제 "John Smith"라는 키는 내부적으로 인덱스 5에 연결되어 있고, 그 자리에 그의 전화번호 "521-1234"가 저장돼 있는것이다.

 

3. 데이터를 검색할 때도 같은 과정을 반복

다시 "John Smith"로 검색하면, 동일한 해시 함수로 계산한 인덱스(5)가 나와서
→ table[5]를 바로 읽어 "521-1234"를 얻을 수 있다.

 

이러한 해싱 구조 덕분에,

Key 값으로 데이터를 찾을 때 해시 함수를 단 한 번만 수행하면 되므로 매우 빠르게 데이터를 저장, 삭제, 조회할 수 있다.

 

물론, 해시 함수의 품질이 낮거나 충돌(Collision) 이 발생하면 최악의 경우에는 O(n)까지 느려질 수 있지만,
평균적인 시간 복잡도는 O(1) 이다.

 

+시간복잡도란?

간단히 말해서, 데이터가 많아질수록, 프로그램의 실행 시간이 얼마나 많이 늘어나는지를 나타내는 지표 이다.
즉, 코드가 실행될 때 실제 걸리는 ‘시간’을 숫자로 측정하는 대신 입력 크기(n) 에 따라 걸리는 연산 횟수의 증가 정도를 표현한다.

 

예를들어 배열에서 특정 값을 찾을때,

const arr = ["a", "b", "c", "d", "e"];

여기서 "d"를 찾으려면 a → b → c → d 순서로 하나씩 비교해야한다.
이건 데이터가 5개니까 4번 비교한다.

 

근데 만약 데이터가 10,000개면? 최악의 경우엔 10,000번 비교해야한다.

즉, 데이터 개수(n) 가 늘어나면 실행 시간도 비례해서 늘어나는 것이다.
이걸 O(n) 이라고 표현한다. ( = 데이터가 많아질수록 선형적으로 느려진다 )

 

하지만 해시 테이블은?

hash_function("John Smith") 로 index 계산 → index 5  반환
array[5] === "521-1234" 로 저장

 

해시 함수로 바로 인덱스를 계산해버리니까 데이터가 10개든 10,000개든 연산은 항상 딱 한 번 일어나게 된다.

그래서 해시 함수의 평균적인 시간복잡도를 O(1)  이라고 한다.

데이터 개수와 상관없이 항상 일정한 시간에 처리된다라는 뜻이기도 하다.

3. 해시 값 충돌이란?

해시 테이블은 Key를 해시 함수에 넣어 배열의 인덱스로 변환한 뒤, 그 인덱스 위치에 데이터를 저장한다.

그런데 문제는 서로 다른 Key가 같은 해시 값을 가질 수도 있다는 점이다.
이걸 해시 충돌(Hash Collision) 이라고 한다.

hash("John Smith") → 5  
hash("Mang Kyu") → 5

예를 들어 위와 같이 두 Key의 해시 값이 동일하다면 둘 다 배열의 인덱스 5번에 들어가려 할 것이다.
이 상황을 해결하지 않으면 한 데이터가 덮어씌워지거나 손실될 위험이 있다.

 

그래서 해시 테이블은 충돌을 해결하는 두 가지 주요 방식을 사용한다

 

1. 분리 연결법 (Separate Chaining)

Separate Chaining 은 “같은 인덱스에 여러 개의 데이터를 연결해서 저장하는 방식” 이다.

즉, 각 버킷(bucket) 에 단 하나의 값이 아니라, 연결 리스트(Linked List) 나 트리(Tree) 를 붙여서 여러 데이터를 저장하는 구조이다.

index 5 → [ ("John Smith", "521-1234") → ("Mang Kyu", "010-5678") ]

이런 식으로 한 버킷 안에 데이터들이 연결되어 있다.

그럼 왜 분리 연결법이 왜 좋은 걸까?

 

1. 해시 테이블 전체를 다시 조정할 필요가 없음 

-> 즉, 기존 구조를 건드리지 않고 충돌난 데이터만 처리하면 된다.

 

예를 들어, index 5에 이미 "John Smith"가 있고, "Mang Kyu"도 같은 인덱스로 충돌했다면 

체이닝 방식에서는 그 인덱스의 연결 리스트에 하나 더 이어주기만 하면 끝이다.

이때, 나머지 인덱스(0~15)는 전혀 영향을 받지 않는다.

다시 배열을 재정렬하거나, 빈 칸을 찾아서 데이터를 이동할 필요도 없다.

 

2. 삭제 연산이 비교적 쉽다

-> 그냥 리스트에서 해당 노드만 제거하면 끝

 

체이닝은 한 버킷이 “리스트(혹은 트리)”로 연결되어 있어서 삭제할 때 해당 Key를 찾아 그 노드만 끊어주면 끝이다.

index 5 → [John → Mang → Kim] 

"Mang"을 삭제하고 싶다면, John.next = Kim으로 연결만 다시 해주면 된다.

 

하지만 이런 분리 연결법에도 단점은 존재한다.

 

1. 데이터가 많아지면 특정 버킷에 몰려 탐색이 느려진다 

-> 즉, 해시 함수가 고르게 분포시키지 못하면 연결 리스트가 너무 길어진다.

 

해시 테이블의 크기가 10이라고 해볼때 
해시 함수가 운이 나쁘게도 많은 키들을 같은 인덱스에 몰아넣었다면?

index 0 → [ A → B → C → D → E ]
index 1 → []
index 2 → []
index 3 → []
index 4 → []
index 5 → []
...

이제 "E"를 찾으려면 어떻게 될까?
→ index 0의 리스트를 처음부터 끝까지 순서대로 따라가야 한다.
즉, O(n) 시간이 걸려버린다.

 

왜 이런 일이 생길까?

• 해시 함수가 데이터를 균등하게 분산시키지 못했을 때
• 테이블 크기가 너무 작아서 충돌이 잦을 때
• 데이터 개수가 테이블 크기보다 훨씬 많을 때

결국 체이닝은 충돌이 많아질수록 리스트가 길어진다 → 리스트가 길어질수록 탐색 시간도 길어진다.

 

2. 메모리 사용량이 늘어난다

-> 즉, 각 버킷마다 “리스트 구조”를 붙이니까, 본래 배열보다 훨씬 많은 공간을 쓴다.

 

원래 해시 테이블은 단순한 배열인데 Separate Chaining은 아래와 같이 된다.

[ 0 ] → [node1 → node2 → node3]
[ 1 ] → []
[ 2 ] → [node1 → node2]

여기서 각 node는 실제 데이터 외에도 추가 정보를 가지고 있다.

• 다음 노드 주소(next pointer)
• (언어에 따라) Key, Value, 객체 포인터 등

즉, 단순히 값 하나만 저장하는 게 아니라, 각 데이터마다 연결 정보까지 저장해야 하니까 그만큼 추가 메모리 오버헤드가 생기게 된다.

100개의 데이터지만, 실제 메모리 사용은 120~150개 분량처럼 커질 수 있다는 것이다.

 

그래서 메모리가 한정적인 환경(임베디드 시스템 등)에서는 체이닝이 효율적이지 못한 경우가 있을 수 있다.

 

2. 개방 주소법(Open Addressing)

Open Addressing(개방 주소법) 은
Separate Chaining처럼 추가적인 연결 리스트나 트리 구조를 사용하지 않고,
해시 테이블 내부의 빈 공간을 직접 활용해서 충돌을 해결하는 방식이다.

 

한마디로 충돌이 발생했을 때, 같은 테이블 안에서 빈 칸을 찾아 옮겨 저장하는 방법이다.

이 방식의 핵심은 데이터를 모두 테이블 내부에 유지한다는 것 이다.

그래서 메모리 낭비가 적고, 데이터 접근이 더 용이해져서 캐시 효율도 좋아질 수 있다.

 

Key를 해시 함수에 넣어 인덱스를 계산하고 저장하려고하는데 그 인덱스가 이미 다른 데이터로 차 있다면?

비어 있는 자리를 찾을 때까지 이동해서 저장한다. 

이때 이동 규칙에 따라 Linear / Quadratic / Double Hashing으로 나뉜다.

 

이후 검색할 때도 같은 규칙으로 이동하면서 데이터를 찾는다.

 

주요 방식 3가지 

1. Linear Probing (선형 탐사)

충돌이 발생하면 고정된 폭(보통 +1) 만큼씩 다음 버킷을 차례로 확인하는 것이다.

hash("John") → index 3  
index 3 이미 차있음 → index 4 확인  
index 4 비어있음 → 저장

구현이 간단하고 빠르다는 장점이 있지만

하지만 연속된 충돌이 생기면 클러스터링(Clustering) 문제가 생긴다.
→ 예를 들어, 인덱스 3, 4, 5, 6이 연달아 차면 새로운 데이터가 계속 7, 8, 9로 몰리게 돼서 탐색 효율이 급격히 떨어지게 된다. 

 

2. Quadratic Probing (이차 탐사)

충돌이 발생할 때마다 이동하는 간격을 제곱 단위로 늘리는 방식이다.

즉, 1², 2², 3² ... 만큼 건너뛰면서 빈 칸을 찾는다.

 

선형 탐사보다 클러스터링이 덜 발생하지만 테이블 크기와 해시 함수의 설계가 잘못되면, 탐색 규칙상 도달 불가한 칸 생기게 되어
빈 칸이 있어도 무한 루프에 빠질 수도 있다.

 

3. Double Hashing (이중 해싱)

한 번 충돌이 발생하면, 두 번째 해시 함수를 사용해서 이동할 칸을 계산하며 충돌 패턴의 규칙성을 없애는 방식이다.

빈 칸을 얼마나 건너뛸까?를 매번 같은 숫자(1, 2², 3² …) 로 이동하는 게 아니라,
각 키마다 다른 간격으로 이동하도록 만들어주는 것이다.

 

선형 탐사(Linear Probing)나 이차 탐사(Quadratic Probing)는 이동 간격이 일정하거나 수학적으로 규칙적이기 때문에

비슷한 해시 값을 가진 키들이 같은 경로를 따라가며 충돌이 자주 일어난다.

 

예를 들어,

• 선형 탐사: +1, +1, +1, +1
• 이차 탐사: +1, +4, +9, +16 …

이러면 서로 다른 키들도 비슷한 패턴으로 빈 칸을 탐색하게 돼서 결국 같은 구간에 몰려버린다.

하지만 이중 해싱은 한번 더 해싱하기 때문에 각 키마다 해시값이 다르기 때문에 각 키가 완전히 다른 이동 패턴을 가지게 된다.

그래서 규칙성이 없어지고 충돌 구간이 겹칠 확률이 확 줄어드는 것이다.

 

하지만 2번 해시 계산을 하기 때문에 연산량은 선형탐사, 이차탐사에 비해 많은 편이다.

---

해시 테이블은 단순한 구조 같지만, 그 안에는 빠른 탐색을 위한 아이디어가 숨어 있는 것 같다.
Key를 단순히 저장하지 않고, 해시 함수를 통해 인덱스로 변환해 직접 접근하는 방식은 정말 기발하다.
물론 해시 충돌이라는 현실적인 한계도 있지만, 체이닝과 개방 주소법 같은 여러 해결 방법을 통해
충돌을 최소화하면서 성능을 유지할 수 있다.

결국 해시 테이블을 이해한다는 건 단순히 자료구조 하나를 외우는게 아니라 데이터를 효율적으로 관리하는 사고방식을 배우는 일인 것 같다.

 

 

 

[출처] https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?