해시 테이블(Hash Table)

🗂️ 해시 테이블 (Hash Table)

자료구조를 공부하다 보면 "탐색 시간 O(1)"이라는 표현을 자주 만납니다.
그게 어떻게 가능한지 궁금해서 한번 정리해 봤습니다 😅

---

🤔 해시 테이블이란?

해시 테이블은 키(Key)와 값(Value)을 쌍으로 저장하는 자료구조입니다.
데이터를 저장할 위치를 해시 함수(Hash Function) 로 계산하기 때문에, 평균적으로 O(1) 의 시간복잡도로 데이터를 저장하고 찾을 수 있습니다.

쉽게 생각해볼게요..🧐

도서관에서 책을 찾는다고 생각해보죠.
만약 책이 아무 규칙 없이 꽂혀있다면 전부 뒤져야 하지만, 책마다 청구기호(숫자)가 붙어 있다면 해당 번호 서가로 바로 가면 됩니다.

해시 테이블에서 해시 함수가 바로 그 청구기호를 만들어주는 역할을 합니다.
키를 넣으면 → 번호가 나오고 → 그 번호의 버킷으로 바로 찾아가는 구조예요.

⚙️ 핵심 구성 요소

구성 요소	설명
키 (Key)	데이터를 식별하는 값
값 (Value)	키에 대응하는 실제 데이터
해시 함수	키를 받아 버킷 인덱스를 계산하는 함수
버킷 (Bucket)	데이터를 실제로 저장하는 배열의 각 칸

🤔 이게 어떻게 연결되는 걸까요?

  "apple"                    ← 키 (Key)
     ↓
 해시 함수                    ← 키를 숫자로 변환
     ↓
    10번                     ← 버킷 인덱스
     ↓
버킷[10] → ("apple", 1)     ← 키-값 쌍으로 저장

키를 해시 함수에 넣으면 번호가 나오고, 그 번호의 버킷에 키-값 쌍을 저장합니다.
찾을 때도 똑같이 키 → 해시 함수 → 번호 → 버킷 순서로 바로 찾아가요.

---

🔁 동작 방식

📥 데이터 저장 (삽입)

1️⃣ 키를 해시 함수에 넣어 해시 값 계산
2️⃣ 해시 값으로 버킷 인덱스 결정
3️⃣ 해당 버킷에 키-값 쌍 저장

🔍 데이터 조회

1️⃣ 키를 해시 함수에 넣어 버킷 인덱스 계산
2️⃣ 해당 버킷으로 바로 이동
3️⃣ 키와 일치하는 값 반환

👉 저장할 때와 찾을 때 같은 해시 함수를 사용하기 때문에, 위치를 바로 알 수 있습니다.

---

⚠️ 해시 충돌 (Hash Collision)

해시 함수가 아무리 좋아도 서로 다른 키가 같은 버킷 번호를 가지는 경우가 생길 수 있습니다.
이걸 해시 충돌이라고 합니다.

🤔 왜 충돌이 생길 수밖에 없을까요?

버킷은 메모리를 사용하기 때문에 무한정 늘릴 수 없습니다.
예를 들어 버킷이 16개라면, 해시 함수는 어떤 키가 들어오든 0~15 사이 숫자만 반환해야 합니다.

근데 저장할 키는 "apple", "banana", "hello" ... 사실상 무한히 많습니다.
16개 칸에 무한한 키를 넣다 보면 언젠가는 같은 번호가 나올 수밖에 없습니다.

"apple"  → 해시 함수 → 10번 버킷
"mango"  → 해시 함수 → 10번 버킷  ← 충돌 발생!

버킷을 엄청 크게 만들면 되지 않을까요?
버킷 100만 개를 만들어도 실제 데이터가 100개뿐이라면
나머지 999,900개는 빈 채로 메모리만 잡아먹습니다.

그래서 적당한 버킷 수를 유지하면서 충돌을 해결하는 방법이 필요합니다.
대표적인 방법이 두 가지입니다.👇👇

1️⃣ 체이닝 (Separate Chaining)

버킷 수는 그대로 유지하되, 충돌이 발생하면 같은 버킷 안에 연결 리스트로 이어 붙이는 방식입니다.

버킷[0] → null
버킷[1] → null
버킷[3] → ("cat", 10) → ("car", 20) → null   ← 충돌난 것들이 줄줄이
버킷[9] → null

"cat"과 "car"가 둘 다 3번 버킷으로 배정됐을 때,
3번 버킷에 첫 번째 데이터를 넣고 뒤에 이어 붙이는 거예요.

나중에 "car"를 찾을 때는 3번 버킷으로 가서 → "cat" 아님 → "car" 맞음! 순서로 찾습니다.

장점	단점
구현이 단순함	한 버킷에 데이터가 몰리면 하나씩 다 뒤져야 해서 느려짐
버킷이 꽉 차도 계속 삽입 가능	캐시 성능이 상대적으로 떨어짐

2️⃣ 개방 주소법 (Open Addressing)

연결 리스트 없이 충돌 시 다른 빈 버킷을 찾아서 저장하는 방식입니다.
빈 자리가 나올 때까지 계속 탐색합니다.

버킷[3] → ("cat", 10)   ← "cat" 먼저 저장
버킷[4] → ("car", 20)   ← "car"도 3번인데 충돌! 다음 칸 4번이 비어있으니 거기 저장

나중에 "car"를 찾을 때는 해시 함수가 3번을 알려주는데, 3번엔 "cat"이 있으니
→ "car" 맞는지 확인 → 아님 → 4번 확인 → 맞다! 이런 식으로 찾습니다.

어떤 순서로 탐색하느냐에 따라 방식이 나뉩니다.

방식	탐색 순서	특징
선형 탐사	바로 다음 칸, 그 다음 칸 순서대로	구현 간단, 클러스터링 발생 가능
이차 탐사	1칸, 4칸, 9칸... 간격을 넓혀가며	클러스터링 완화
이중 해싱	두 번째 해시 함수로 간격 계산	가장 고른 분포

ℹ️ 클러스터링(Clustering)이란?

데이터가 한쪽 버킷에 몰리는 현상입니다.
선형 탐사에서 특히 자주 발생하며, 클러스터링이 심해지면 빈 버킷을 찾기 위해 계속 다음 칸을 뒤져야 해서 성능이 급격히 저하됩니다.

---

📊 시간복잡도

연산	평균	최악
삽입	O(1)	O(n)
삭제	O(1)	O(n)
탐색	O(1)	O(n)

🤔 O(1)과 O(n)이 뭔가요?

데이터가 늘어날수록 연산이 얼마나 느려지는지를 나타내는 척도입니다.

• O(1) → 데이터가 100개든 10,000개든 항상 한 번에 찾음
• O(n) → 데이터가 100개면 최대 100번, 10,000개면 최대 10,000번 탐색

해시 테이블은 키만 알면 버킷으로 바로 찾아가기 때문에 평균 O(1)입니다.
단, 모든 키가 같은 버킷에 몰리면 하나씩 다 뒤져야 해서 최악의 경우 O(n)이 됩니다.

좋은 해시 함수와 적절한 로드 팩터를 유지하면 평균 O(1)을 기대할 수 있어요.

ℹ️ 로드 팩터(Load Factor)란?

해시 테이블의 채워진 정도를 나타내는 값입니다.

 로드 팩터 = 저장된 데이터 수 / 전체 버킷 수

로드 팩터가 높아질수록 충돌 가능성이 올라갑니다.

---

🌍 언어별 해시 테이블 구현체

언어	구현체
Java	HashMap, HashSet
Python	dict, set
C++	unordered_map, unordered_set
JavaScript	Map, Set

---

☕ 마무리

개념	설명
해시 테이블	키-값 쌍을 해시 함수로 위치를 결정해 저장하는 자료구조
해시 함수	키를 버킷 인덱스로 변환하는 함수
해시 충돌	서로 다른 키가 같은 인덱스를 가지는 현상
체이닝	충돌 시 연결 리스트로 이어서 저장
개방 주소법	충돌 시 다른 빈 버킷을 탐사해서 저장
로드 팩터	테이블의 채워진 정도 (높을수록 충돌 증가)

📚 참고자료

• Wikipedia — Hash table
• GeeksforGeeks — Separate Chaining
• GeeksforGeeks — Open Addressing