자료구조 - 해시 테이블

해시테이블은 키와 값의 대응으로 이루어진 표(테이블)와 같은 형태의 자료구조를 말한다.

키는 해시 테이블에 대한 입력, 값은 키를 통해 얻고자 하는 데이터라고 볼 수 있다.

특징

• 평균 시간 복잡도: O(1) for 삽입, 삭제, 검색
• 최악의 경우 시간 복잡도: O(n)

해시 테이블 시간 & 공간 복잡도 자세하게 이해하기

평균 시간 복잡도: O(1)

• 해시 함수 계산 : 보통 상수 시간에 처리됨.
• 삽입, 탐색, 삭제 모두 배열 인덱스에 직접 접근 → O(1)

hash_table = {}
hash_table["apple"] = 5       # 삽입 O(1) apple라는 키에 값 넣기
value = hash_table["apple"]   # 검색 O(1) apple라는 키로 찾기
del hash_table["apple"]       # 삭제 O(1) apple라는 키로 삭제

최악 시간 복잡도: O(n)

• 해시 충돌이 심하게 일어나 모든 키가 같은 버킷에 몰릴 경우.
• 체이닝 방식에서는 연결 리스트처럼 선형 탐색 발생.

class BadHash:
    def hash_function(self, key): return 0  # 전부 같은 인덱스로 충돌

# 충돌이 심하면 삽입/검색이 O(n)

공간 복잡도: O(n)

• 저장하는 데이터 수만큼 공간 필요.
• 로드 팩터가 일정 이상이면 리사이징이 필요 → 새 배열에 재배치.

if self.size / self.capacity > 0.7:
    self._resize()  # 용량 2배로 늘리고 재해시

해싱 (Hashing)

• 정의 : 임의의 크기를 가진 데이터를 고정된 크기의 데이터로 변환
• 목적 : 데이터를 빠르게 저장하고 검색하기 위함

해시 함수 (Hash Function)

정의 : 임의의 길이를 지닌 데이터를 고정된 길이의 데이터로 변환하는 단방향 함수

특징

1. 일관성: 동일한 입력에 대해 항상 동일한 출력
2. 효율성: 계산 속도가 빠름
3. 균일성: 해시값이 고르게 분포

해시 함수의 연산방법은 해시 알고리즘이라고 하는데 예시들

MD5, SHA-1, SHA-256 등

해시 테이블 (Hash Table)

• 정의: 해시 함수를 사용하여 키를 해시값으로 변환, 이 값을 색인으로 데이터를 저장하는 자료구조
• 구성 요소
  1. 키 (Key)
  2. 해시 함수 (Hash Function)
  3. 해시값 (Hash Value)
  4. 버킷 (Bucket) / 슬롯 (Slot)

해시 충돌 (Hash Collision)

해시 충돌이란 서로 다른 키에 대해 같은 해시 값에 대응하는 상황.

예를 들어 다른 이름에 같은 전화번호가 대응된 상황

체이닝 (Chaining)

개념 : 충돌이 발생한 데이터를 연결 리스트로 추가하는 방법.

서로 다른 키가 같은 위치로 해서 해시 되어도 단순히 연결 리스트의 노드로 추가될 뿐이기 때문에, 다음과 같이 하나의 테이블 인덱스에 여러 데이터가 연결 리스트의 노드로써 존재할 수 있다.

장점

1. 해시 테이블 확장이 필요 없음
2. 간단한 구현

단점

1. 추가 메모리 필요
2. 최악의 경우 시간 복잡도 O(n)

구현 방법

1. 연결 리스트 (Linked List)
2. 레드-블랙 트리 (Red-Black Tree)

개방 주소법 (Open Addressing)

개념 : 충돌이 발생했을 때, 충돌이 발생한 버킷의 인덱스가 아닌 다른 인덱스에 데이터를 저장하는 방법.

쉽게 말해서 자리 없는 인덱스를 피해서 다른 인덱스를 알아보자는 해결 방식이라고 할 수 있다.

장점

1. 추가 메모리가 필요 없다
2. 캐시 효율성이 좋다

단점

1. 클러스터링 문제 발생 할 수 있다.

연속된 빈 공강인 줄어들고, 데이터들이 한쪽에 몰리는 현상.

1. 삭제 작업이 복잡하다

• 주요 기법

  1. 선형 탐사 (Linear Probing)

     • 충돌이 발생했을 대, 충돌이 발생한 인덱스의 다음 인덱스부터 순차적으로 가용한 인덱스를 찾아 나서는 방법.

     문제는 해시 충돌이 발생한 인덱스 인근에 충돌이 발생한 여러 데이터가 몰려서 저장될 수 있다. 이러한 현상을 군집화라고 한다.

  2. 제곱 탐사 (Quadratic Probing)

     • 충돌 시 제곱수만큼 건너뛴 버킷 확인

  3. 이중 해싱 (Double Hashing)

     • 말 그대로 2개의 해시 함수를 사용하는 방법. 충돌이 발생했을 때 다른 해시 함수(보조)에 대한 해시 값 만큼 떨어진 거리에 위치한 인덱스를 찾는 방법.

해시 테이블의 장단점

장점

빠른 검색, 삽입, 삭제 (평균 O(1))

일반적인 상황에서 해시 테이블을 활용한 검색, 삽입, 삭제 연산의 시간복잡도는 O(1)이다. 이는 입력과 무관하게 항상 일정한 속도를 보장한다는 의미다.

키-값 쌍의 데이터 저장에 효율적

단점

속도가 빠른 만큼 상대적으로 많은 메모리 공간이 소모되서 공간복잡도가 시간복잡도에 비해서 많이 떨어짐.

순서가 있는 데이터 저장에는 부적합

해시 함수의 의존도가 높음

해시 충돌이라는 문제 해결해야 함.