[자료구조] HashTable (feat. python)

HashTable

평균적으로 매우 빠른 삽입, 삭제, 탐색이 가능하며 이는 사전식(key, value) 자료구조를 가지고 있기 때문이다.

HashTable 성능 척도

Less Collision → 적은 충돌

Fast Compution → 빠른 계산

1과 2는 trade-off 관계이기 때문에, 주어진 자원과 상황에 맞게 적절한 조화를 가지는 것이 중요하다.

- HashFunction의 등급

$S =$ 입력값의 집합

$h =$ 해시 함수

$m =$ 슬롯(Slot)의 갯수 $\ \fallingdotseq$ $\ h(x)$ 의 범위 크기

$P(h(x_1) = h(x_2)) =$ 서로 다른 값의 충돌(Collision) 확률

완전 해시 함수 (Perfect HashFunction $=$ Injective HashFunction)
완전 해시 함수는 충돌이 없는 해시 함수이다, 특정한 집합 $S$ 의 각 원소를 고유한 정수로 매핑한다. 상수 시간 복잡도( $O(1)$ )로 데이터를 검색할 수 있어 매우 효율적이다.

수식:
$h(x)= \{0, 1, \ldots, m-1\}$
즉, 완전 해시 함수는 $(key : slot = 1 : 1)$ 관계이다.
유니버설 해시 함수 (Universal HashFunction)
```
> 조건: m > 0 의 상수
```
두 개의 서로 다른 키가 같은 값으로 해싱될 확률을 최소화하는 성질을 가진다.
즉, $S$ 에 포함된 서로 다른 두 키 $x_1$ 과 $x_2$ 에 대해, 이들이 동일한 값으로 충돌할 확률은 최대 $1/m$ 이다.

수식:

$\quad P(h(x_1) = h(x_2)) \leq \frac{1}{m}$
C-유니버설 해시 함수 (C-Universal HashFunction)
```
	> 조건: m > 0 의 상수, C > 0 의 상수
```
C-유니버설 해시 함수는 유니버설 해싱 개념을 확장하여 충돌 확률을 제어할 수 있도록 합니다.
이 경우, $S$ 에 포함된 서로 다른 두 키 $x_1$ 과 $x_2$ 가 동일한 값으로 충돌할 확률은 최대 $C/m$ 입니다.

수식:

$\quad P(h(x_1) = h(x_2)) \leq \frac{C}{m}$

요약

완전 해시 함수:
주어진 키 집합에 대해 충돌을 완전히 제거

유니버설 해시 함수:
일반적인 사용 사례에서 모든 가능한 키 쌍 간의 충돌 확률을 최소화

C-유니버설 해시 함수:
조정 가능한 상수 인자를 통해 충돌 확률을 제한

- HashFunction의 종류들

if typeof key === 'int':

Division

Mutiplication

Folding

Mid Squeares

Extraction

if typeof key === 'string':

Additive

Rotating

- 충돌 회피 방법 (Collision Resolution Method)

Open Addressing (개방 주소법)

Linear Probing (선형 탐사)
- 설명: 충돌이 발생하면 현재 충돌이 발생한 인덱스에서 다음 인덱스를 순차적으로 검사하며 비어 있는 슬롯을 찾음.
- 예: 해시값이 3에서 충돌이 발생하면, 4, 5, ... 순서로 빈 슬롯을 탐색.
- 장점: 구현이 간단.
- 단점: 클러스터링(Clustering) 문제가 발생할 수 있으며, 이는 데이터가 특정 영역에 몰려 평균 탐색 시간이 증가하는 현상.
Quadratic Probing (이차 탐사)
- 설명: 충돌이 발생하면 제곱수의 간격으로 다음 슬롯을 탐색.
- 예: 해시값이 3에서 충돌이 발생하면, 4(1²), 7(2²), 12(3²) 순서로 빈 슬롯을 탐색.
- 장점: 클러스터링 문제를 줄일 수 있습니다.
- 단점: 여전히 이차 클러스터링 문제가 발생할 수 있으며, 테이블의 크기가 소수(prime number)가 아니면 모든 슬롯을 탐색하지 못할 수 있음.
Double Hashing (이중 해싱)
- 설명: 두 개의 서로 다른 해시 함수를 사용하여 충돌 시 이동 폭(probe step)을 계산. 첫 번째 해시 함수는 초기 위치를 결정하고, 두 번째 해시 함수는 충돌 시 이동 간격을 제공.
- 예:
  $h_1(k) = k \mod m$ ,
  $h_2(k) = 1 + (k \mod (m-1))$ .
  충돌 시: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$ .
- 장점: 클러스터링 문제를 효과적으로 해결할 수 있음.
- 단점: 구현이 복잡하며 추가적인 계산 비용이 필요.

Chaining (체이닝)

설명: 각 해시 테이블 슬롯에 연결 리스트(Linked List)를 사용하여 데이터를 저장합니다. 충돌이 발생하면 해당 슬롯의 연결 리스트에 노드를 추가합니다.
장점: 테이블의 크기 제한 없이 데이터를 저장할 수 있습니다. 최악의 경우에도 테이블 크기와 무관하게 데이터를 계속 추가할 수 있습니다.
단점: 연결 리스트가 길어질 경우 검색, 삽입, 삭제의 시간 복잡도가 $O(n)$ 으로 증가할 수 있습니다. 이를 해결하기 위해 연결 리스트 대신 트리 구조(Binary Search Tree)를 사용할 수도 있습니다.

- 주요 함수(set, remove, search)의 동작들이 영향 받는 것

Cluster의 크기에 영향:
- 평균적으로 $2n \leq m$ 과 같이 최소 50% 이상 빈 Slot을 놔두면 Cluster의 평균 Size가 $O(1)$ 이 되게 할 수 있다.
Cluster의 크기는 아래의 세가지에 영향
2-1. HashFunction 성능

2-2. Collision Resolution method 성능
- $\frac{c}{n}= \frac{number \ of \ collision}{items}$ 와 같은 방법으로 성능 평가 가능
2-3. Load Factor:
- $\frac{n}{m} = \frac{items}{slots}$

- HashTable remove 시 유의할 점

상황 가정

해시함수:
Division HashFunction $\rightarrow h(x) =$ $(x\ mod \ m)$

충돌회피방법:
Linear Probing

Slot Size:
$m = 10$
0: S = [10, 2, 22, 24, ...]
1: for s in S: Add(s)
2: ....
3: remove(2)
4: search(22)
위와 같은 상황 가정에서 코드(0~1 line)를 실행할 경우 아래와 같이 $m$ 에 데이터가 저장될텐데
0~1 line: [10, *, 2, 22, 24, *, *, *, *, *]
0~3 line: [10, *, *, 22, 24, *, *, *, *, *] $\rightarrow$ 3-index에 저장된 '22'를 2-index로 옮겨줘야 하는 재보정이 필요함.
삭제(remove) 이후 전체적인 데이터의 보정이 없다면, 그 이후 실행되는 탐색(search)이 영향을 받는다.

- HashTable 만들어보기

해시함수: Division HashFunction

충돌 회피 방법: Linear Probing & Chaining

from typing import TypeVar, List

V_T = TypeVar('value_type')
TableType = List[List[tuple[str, V_T]]]

class HashTable:
    def __init__(self, length=10):
        self.max_len = length
        self.table: TableType = [[] for _ in range(self.max_len)]

    def __len__(self):
        return self.max_len

    def __str__(self):
        return str(self.table)

    def __iter__(self):
        for item in self.table:
            yield item

    def __hash__(self, key: str) -> int:
        target = sum([ord(s) for s in key])
        return target % self.max_len

    def __eq__(self, other):
        return self.table == other.table

    def find_slot(self, key) -> int:
        return self.__hash__(key)

    def set(self, key, value):
        index = self.find_slot(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

    def search(self, key):
        index = self.find_slot(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def remove(self, key) -> None or str:
        index = self.find_slot(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return key
        return None

참고 영상 및 문서:

영상
[1] https://youtu.be/Bzmepm6pYQI?si=gfXz_zUrUDKwGf_8
[2] https://youtu.be/Bj4pd9rJp5c?si=SZO2gXpvBUhfrtAm
[2] https://youtu.be/ghjWopXXUeA?si=7GaY4OD515iGYGyj

문서
[1] https://ryu-e.tistory.com/87
[2] https://www.nossi.dev/436b3b11-fa77-4dcc-9d24-f6b034d6770e
[3] https://engineerinsight.tistory.com/332
[4] https://jun-n.tistory.com/26
[5] https://velog.io/@jaehwan0129/%EC%84%A0%ED%98%95-%EC%A1%B0%EC%82%AC%EB%B2%95Linear-Probing
[6] https://blog.naver.com/beaqon/221300416700
[7] https://eminentstar.tistory.com/40
[8] https://nyang-in.tistory.com/117
[9] https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%EC%B6%A9%EB%8F%8C

SUNG JE KIM

이전 포스트

[자료구조] HashTable (feat. python)

HashTable

- HashFunction의 등급

- HashFunction의 종류들

- 충돌 회피 방법 (Collision Resolution Method)

Open Addressing (개방 주소법)

Chaining (체이닝)

- 주요 함수(set, remove, search)의 동작들이 영향 받는 것

- HashTable remove 시 유의할 점

- HashTable 만들어보기

[자료구조] LinkedList (feat. python)

0개의 댓글