해시테이블과 해시충돌

해시테이블과 해시충돌에 대해 정리해보았습니다.

구글링 및 ChatGPT의 도움을 받아 작성했습니다.

 

 

해시 테이블과 해시 충돌 정리

1. 해시 테이블이란?

키(Key)를 해시 함수로 변환해
배열 인덱스로 사용하여 값을 저장·조회하는 자료구조

 

해시 테이블을 사용하는 핵심 이유는 빠른 탐색이다.

빠른 탐색 (평균 O(1))

 

2. 왜 해시 테이블이 빠른가?

일반적인 자료구조와 비교하면:

구조	탐색 시간
배열	O(1) (인덱스 필요)
리스트	O(N)
트리	O(log N)
해시 테이블	O(1) (평균)

👉 키 → 인덱스로 바로 접근하기 때문

 

3. 해시 테이블의 기본 구성

1) Key

• 검색 기준 값
• 예: ID, 좌표, 문자열

2) Hash Function

• Key → 정수값으로 변환
• 이 값으로 배열 인덱스 결정

3) Bucket (버킷)

• 실제 데이터가 저장되는 공간

 

4. 해시 함수의 역할 (중요)

좋은 해시 함수란:

• 같은 키 → 같은 값
• 다른 키 → 최대한 다른 값
• 계산 비용이 낮음

👉 충돌을 최소화하는 것이 핵심

 

5. 해시 충돌(Hash Collision)이란?

서로 다른 키가
같은 해시 값(같은 버킷)을 가지는 현상

 

hash("Player1") = 3
hash("EnemyA")  = 3

👉 두 데이터가 같은 위치를 차지하려 함

 

6. 해시 충돌은 왜 발생하는가?

• 키의 개수 > 버킷 개수
• 해시 함수 품질이 나쁨
• 특정 패턴의 키가 많음

👉 충돌은 피할 수 없다

7. 해시 충돌 해결 방법

1) 체이닝 (Chaining)

한 버킷에 리스트(또는 벡터) 로 여러 데이터 저장

 

[3] → (A) → (B) → (C)

특징

• 구현 단순
• 충돌 많아지면 O(N)

STL의 unordered_map 기본 방식

 

2) 개방 주소법 (Open Addressing)

충돌 시 다른 빈 버킷을 탐색

방식 예

• Linear Probing (선형 탐사)
  • 충돌 시 한 칸씩 순차적으로 이동하며 빈 공간 탐색
    • index = (hash(key) + i) % tableSize
  • 장점
    • 구현이 매우 간단
    • 캐시 효율 좋음
  • 단점
    • Primary Clustering : 연속된 빈 공간이 하나의 큰 덩어리로 성장
    • 충돌이 연쇄적으로 증가
• Quadratic Probing (제곱 탐사)
  • 충돌 시 제곱 간격으로 이동
    • index = (hash(key) + i²) % tableSize
  • 장점
    • Primary Clustering 완화
    • Linear보다 충돌 분산
  • 단점
    • Secondary Clustering : 같은 hash 값을 가진 키는 같은 탐색 경로를 가짐
    • 빈 칸이 있어도 못 찾을 수 있음
    • 테이블 크기와 수식에 의존
• Double Hashing (이중 해싱)
  • 두 개의 해시 함수를 사용하여 탐색 간격을 결정
    • index = (hash1(key) + i * hash2(key)) % tableSize
  • 장점
    • Primary Clustering ❌
    • Secondary Clustering ❌
    • 충돌 분산 최고
  • 단점
    • 구현 복잡
    • 해시 함수 2개 필요
    • 연산 비용 증가

특징

• 메모리 효율 좋음
• 클러스터링 문제 발생 가능

 

8. Load Factor (부하율)

Load Factor = 저장된 요소 수 / 버킷 수

• 높을수록 → 충돌 증가
• 낮을수록 → 메모리 낭비

👉 일정 수준 이상이면 Rehashing 필요

 

9. Rehashing이란?

버킷 수를 늘리고 모든 데이터를 다시 해시하는 과정

• 비용 큼
• 하지만 성능 유지를 위해 필수

 

10. 게임 개발에서의 활용 예

• 좌표 기반 방문 체크 (A*)
• ID → 객체 빠른 조회
• 네트워크 패킷 처리
• Entity 관리 시스템

 

11. 해시 테이블의 단점

• 최악의 경우 O(N)
• 순서 보장 안 됨
• 메모리 사용량 큼

👉 만능 자료구조는 아님

 

 

12. 요약

해시는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 과정입니다.

이때 사용되는 함수가 해시 함수(Hash Function) 입니다.

 

해시 테이블은 평균적으로 O(1) 탐색을 제공하지만,
해시 충돌로 인해 최악의 경우 O(N)이 될 수 있으며
이를 해결하기 위해 체이닝이나 Open Addressing을 사용합니다.