해쉬 테이블 개념

Oct 23, 2023

Contents

만약 key 값이 int type 이 아니라 str type 이라면 ?좋은 Hash function 의 조건 충돌 회피 방법 (collision resolution method)open addressing 성능 평가 Chaining

Hash Table: O(1) 만에 삽입, 삭제, 탐색 연산을 제공

파이썬에서는 dictionary 를 통해 해시테이블 사용 가능


D = {} # 빈사전

D['2019317] = '신창수' # 2019317은 key , 신창수는 value 
D['2019111'] = '홍길동'

다음처럼 빈 딕셔너리를 만든 후 key 값과 value를 넣으면서 딕셔너리를 사용 할 수 있다.


D = {2019317 : '신창수' , 2019111 : '홍길동'}

딕셔너리를 생성할 때 key 값과 value 값을 넣으면서 생성 할 수도 있으며 딕셔너리의 key , value 값은 데이터 타입이 다르더라도 사용 가능하다.

만일 딕셔너리 형태처럼 key , value 값을 stack 안에 쌓게 된다면 삽입, 삭제, 탐색까지 걸리는 시간복잡도는 O(n)이다.

stack은 어떤 값을 삽입, 삭제, 탐색 할 때 모든 인덱스를 돌으며 해당 값이 있는지 확인하고, 삽입하거나 삭제한다면 변화가 된 자리에 맞게 바뀐 값들의 인덱스를 모두 수정해줘야 하기 때문이다 .

이는 연산의 효율성에서 좋지 않다.

해시테이블을 알아보기 위해 만약 10가지 공간이 있는 Table 안에 key 값과 valeu 값을 넣기로 해보자 10개의 공간이 있기 때문에 새로운 데이터가 들어올 공간의 인덱스를 key 값을 10으로 나눈 나머지 값으로 지정하기로 했다고 해보자

예를 들어 (2019317, ‘신창수’) 라는 key , value 값을 넣을 때는 7번 인덱스 안에 (2019317, 신창수) 라는 값을 삽입하게 된다. 그 후 2019317 이란 key 값을 가지고 탐색을 시행한다면 2019317 를 10으로 나눈 나머지인 7번 인덱스를 탐색한다. key 값을 index 로 특정 함수를 이용하여 mapping 하기 때문에 상수 시간 안에 탐색, 삽입, 삭제가 가능하다.

다음처럼 key 값을 index로 지정하는 함수를 해시함수 라고 칭하며 현재 사용한 해시함수는

이다. 이 때 m 은 해시 테이블의 크기를 칭한다.

만약 내가 저장하려는 table 에 다른 value 값이 이미 존재한다면 이를 해결하기 위한 방법들이 존재하며 이러한 방법을 collision resolution method (충돌 회피 방법) 라고 한다.

Table 자체는 list 로 존재한다.

해시 함수 (Hash function)

해시 테이블에 저장 공간은 slot이라고 하며, 해시 테이블의 사이즈는 slot 의 개수이며 2의 n 승 개로 가지고 있는 것이 일반적이다.

해당 해시 테이블에 키 값이 28인 key , value 값이 저장된다고 가정해보자

Division hash function

이전 처럼 들어온 key 값을 적절한 p 값 (이 때 p는 소수) 으로 나눈 나머지와 slot 의 개수와의 나머지를 이용하여 index 로 맵핑하는 함수를 Division hash function 이라고 한다.

이는 직관적이지만 동일한 나머지를 가진 key 값이 삽입된다면 slot 안에서 충돌이 일어날 수 있다.

Perfect Hash function

가장 이상적인 hash function 형태로 하나의 key 값이 하나의 slot 안에 저장되도록 만들어주는 함수이다 . 하지만 이러한 경우는 찾기 쉽지가 않다.

Universal hash function

key 값이 x 값인 value 1, key 값이 y 인 value 2 가 있을 때

x , y 의 key 값이 같을 확률이 전체 해시 테이블의 사이즈인 m 과 반비례하도록 하는 function 을 universal hash function 이라고 한다 .

C universal

등등 다양한 기능의 Hash function 이 존재한다.

만약 key 값이 int type 이 아니라 str type 이라면 ?

string 값의 아스키코드 값을 모두 더한 후 slot 의 개수로 나누는 Additive 기법

특정 값을 initial 한 후 해당 값을 다양한 방법으로 연산 하고 특정 방법의 값으로 처리한 후 index 값을 계산하는rocating , universal 방법이 존재한다 .

좋은 Hash function 의 조건

1. Less Collision

2. Fast Computation

key 값간의 충돌이 적게 일어나면서 hash function 의 연산 속도가 빠른 hash function 이 가장 최상의 hash function 일 것이다.

충돌 회피 방법 (collision resolution method)

open addressing

현재 내가 충돌이 일어났다면 주위에 빈칸을 찾아서 저장하는 방법

linear probing

ex : A5, A2 는 뒤에 있는 숫자에 맞춰 value 값을 저장

마지막 slot 과 첫번 째 slot 은 원형처럼 이어져있다고 생각하기로 함
slot 들이 모인 것을 cluster 라고 하는데 최대한 cluster가 작아야 빠르게 연산이 가능함
해당 예시에서 B3 라는 값을 찾으려 한다면 3번 slot 부터 B3를 찾을 때 까지 선형적으로 내려 갈 것이며 만약 B3를 포함한 cluster를 모두 지나 빈 공간을 찾는다면 찾는 값이 없기에 None 값을 return

quadratic probing

double hasing

Linear probing

find_slot(key)

key 값을 해쉬 함수를 거친 후의 값부터 시작하여 그 다음 slot 까지 반복문을 통해 찾으며 search

만약 한바퀴를 돌았는데 while 문이 끝나지 않았다면 (while 문은 그 자리가 차있지 않거나, 내가 찾는 값이면 끝난다) None 값을 return

만약 비어있거나 내가 찾는 값이 있으면 slot 번호를 return 한다.

set(key , value = None)

key 값이 H에 있으면 value 를 update

만약 없으면 key , value 값을 inset

Set 함수는 table이 꽉 차있다면 넣을 공간이 없으니 table의 크기를 키운 후 넣을 공간이 없으니 None 값을 return

만약 차있다면 value 값을 내가 넣고자 하는 value 로 update한다. 비어있다면 key , value 값을 내가 넣고자 하는 값으로 넣어서 update 한다.

remove(key)

key 값을 찾아 h 에서 지우는 것

remove 할 때에는 remove 만 할 것이 아니라 빈 자리를 채워줄지 말지에 대해 생각해봐야 한다.

💡

다음처럼 3번 key 값을 remove 해준 후 빈 자리로 놔둔게 된다면 생길 수 있는 일 2번 key 값을 search : A2 A2가 아니니 3번 key 로 이동하였는데 3번 key 값이 empty 이니 B2를 찾을 수 없다.

그렇기 때문에 특정 key 값을 remove 한다면 밀려나간 값들에 대해서 빈 자리를 채워야 할 것이다.

B2 를 올려준 후 생기는 빈자리를 채울지 말지에 대해 생각해보자 A5 는 5번 key 값에 잘 위치해있다. B5 는 5번 key 값이 채워져있으니 6번 key 값에 잘 채워져있다. 하지만 C2의 경우 2번 key 부터 모두 밀려나간 것이기 때문에 빈자리로 올라가 채워줘야한다.

다음과 같은 조건일 때 옮길 수 있다.

k가 원래 j key 값에 있는 value가 위치해야 할 자리고 i 가 빈자리라면 k < i < j 일 때 옮길 수 있다.

다음과 같은 경우에도 옮길 수 있다.

search(key)

search 는 find slot 과 유사한 방법으로 사용한다.

Quadratic probing : double hashing

linear 때는 선형적으로 이동하였다면 Quadratic probing 은 제곱하며 이동한다.

이는 linear 에 비해서 cluster 의 사이즈를 (cluster 의 길이) 작게 해줄 수 있다.

double hashing 의 경우에는 hash function 이 2가지 이상 필요하며 계산이 더 많다는 단점이 있기도 하지만 많이 사용된다.

성능 평가

linear probing

set, remove, search : cluster size에 따라 영향을 받는다.

cluster size 는 hash function , collsuin resoloution method, load factor 의 영향을 받는다.

load factor 는 n/m 으로 slot 의 크기 대비 차있는 아이템의 개수
load factor가 커지면 커질 수록 연산 횟수가 많이 발생

💡

linear probing 은 왜 cluster size에 영향을 받을까 ? cluster는 table에서 충돌이 일어났을 때 다음 key 값에 value 를 집어넣음에 따라 생성된다. 충돌이 계속 일어남에 따라 clsuter 의 사이즈가 커지게 된다면 충돌이 일어났을 때 clsuter 의 크기 만큼 이동하며 빈 slot 을 찾아야 한다.

이를 해결하기 위해 평균적으로 m > 2n 일 경우 (table 의 slot 수가 넣어야 할 데이터보다 2배 많다면) cluster 내부에서 이동할 때의 시간 복잡도가 O(1) 이 된다. (m 을 늘림에 따라 데이터를 이동시키는 것들까지 포함하여도)