해시 테이블

해시 테이블은 매우 빠른 삽입, 삭제, 탐색 연산을 제공하는 자료구조

python에서는 dict를 사용

key와 value의 형태로 해시 테이블에 저장 ( 해시 테이블은 보통 배열을 사용, 이 슬롯의 크기를 m이라 함)

해시 테이블에 저장할 때 hash Function을 이용해서 특정한 인덱스(Hash Code)를 지정해주게 됨

python에서는 hash(key)를 입력하게 되면 특정 key가 출력됨

hash function

1. perfect hash function : 이상적인 h.f

key -> slot 이 1:1로 매치됨

즉, collision이 발생하지 않음 -> 비현실적

2. universal hash function :

x란 key 값과 y란 key 값이 있다고 했을 때

f(x) == f(y) 라면 이것은 collsion이 발생한 것.

Pr(f(x)==f(y)) => f(x)와 f(y)가 같을 확률

Pr(f(x)==f(y)) 일 확률이 전체 해시 테이블 슬롯(m)의 사이즈에 반비례

-> Pr(f(x)==f(y)) = 1/m

-> Pr(f(x)==f(y)) = c/m -> c - universal h.f 실제로 가장 많이 사용하는 h.f

Hash Function의 종류

1. Division

2. Multiplication

3. Folding

4. Mid - Squares

5. Extraction

Key : string 이라면?

key = '12345'

additive : key [i]의 아스키코드값을 모두 더한 후 % m

Rotation : 값 h를 계산 -> init value

key = 'this is key'
h = initvalue
for i in range(len(key)):
    # h를 2의 4승 곱한 값과 h를 2의 28승 나눈 값과 특정 인덱스의 ch와 exclusive or 연산
    h = (h<<4)^(h>>28)^key[i]
# p 는 특정 소수값
return h%p%m

Universal : C ++ STL과 Java에서 사용

key = 'this is key'
h = initvalue
for i in range(len(key)):
    # a는 특정 상수
    h = ((h*a) + key[i])%p
return h%m

좋은 Hash Function?

1. less collision

2. fast computation

둘은 trade off 관계