해시 테이블 Hash Table (1)

Key, value 로 구성된 자료구조 ( key 와 value 의 쌍으로 이루어짐 )
파이썬에서는 dictionary 가 key 와 value 형태의 해시테이블로 쓰인다.

D = {}
D['2019317'] = '제임스' # 학번(key) 2019317, 이름(value) 제임스 

key, value 의 해시테이블 자료구조에 데이터를 어떻게 저장할수 있을까?

만약 순차적으로 리스트에 저장하게 되면 삽입, 삭제, 탐색이 ( m : 배열의 길이 ) 만큼의 시간 복잡도 O(m) 가 될것이다.
이러한 순차적인 방법은 연산의 효율성 면에서 좋은 방법이 아니다.

이러한 비효율성을 해결하기 위해 해시함수를 만들어 key를 input 으로 받아 해시 함수의 배열의 index 가 output으로 나온다면 조금더 효율적일것이다.
예를 들어 해시함수가 정수의 key 값을 배열의 길이 (m) 으로 나눈 나머지를 배열의 index로 한다고 하자.

• key : 2019317, value : 제임스, 배열의 길이 : 10 이면 7번째 index 에 값을 저장할것이다.
• key : 2019209, value : 알렌, 배열의 길이 : 10 이면 9번째 index 에 값을 저장할것이다.

이런식으로 해시함수를 이용하면 탐색하는데 나머지 연산만 하면 되므로 상수 시간만 소요된다.

key 값을 index 로 맵핑(mapping) 하는것은 나머지 함수이다. 여기에서 나머지 함수가 해시함수인것이다.
f(key) = key % m ( hash function )

충돌

하지만 key 값을 배열의 길이로 나눈 나머지의 값을 구하는 해시함수를 하게 된다면 key 값이 2019105 과 2019295 는 5 라는 같은 결과값이 나온다.
이러한 경우를 충돌 ( collision ) 이라고 한다.
충돌이 일어나면 충돌을 해결하는 것을 "collision resolution method" 라고 한다.

Hash function

1. Perfect Hash Function

• 가장 이상적인 함수
• key 와 slot (해시테이블의 공간) 이 거의 1:1 관계로 골고루 분산되어 있는 함수

2. Universal Hash Function

• Pr[f(x) == f(y)] = 1 / m
• 충돌이 발생할 확률이 전체 헤시테이블 사이즈에 반비례하는 것

3. C-Universal Hash Function

• Pr[f(x) == f(y)] = c / m

좋은 해시 함수는 어떤 함수 일까?

1. less collision

• 충돌이 적을수록 즉 키값을 슬롯에 골고루 분산시킬수록 좋은 해시함수이다.

2. fast computaion

• 계산이 복잡하지 않아 빠른 시간안에 할수 있는 함수가 좋은 해시함수이다.

두 항목은 서로 trade off 관계에 있다. 따라서 적절하게 균형을 맞춰야한다.

요약

1. Table : List
2. Hash function
3. Collision resolution method

Reference
한국외대 자료구조 2020-1 강의를 보면서 정리한것입니다.
https://www.youtube.com/watch?v=Bzmepm6pYQI&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=17