해시 알고리즘 Hash Algorithm

해슁/해싱 Hashing

key K를 해시함수값인 h(K)의 위치에 저장하는 자료구조.
Direct-Address 테이블에서의 공간 낭비를 줄이면서도, 시간복잡도를 낮추기 위해서 사용하지만 충돌문제가 있으며 이를 해결하기 위한 Chained Hash Table은 시간이 느려질 수 있음.

 

충돌

다른 Key K인데 해시함수값인 h(K)가 동일한 경우

 

체인을 이용한 충돌 해결법

중복되는 Key값이 있을 경우 해당 슬롯을 연결리스트로 저장한다.

Hash Table - WikiPedia

 

 

수행시간

최악의 경우  : O(N)
    - 모든 Key 값 K가 하나의 해쉬함수 값를 갖는 경우
    - 모든 Key 값이 하나의 연결리스트에 저장된 경우
평균의 경우 : O(1+a)
    - a는 적재율  = 윈소의 개수 / 슬롯(버킷)의 개수

 

좋은 해쉬 함수란?

key가 중복없이 m개의 슬롯(버킷)에 동일한 확률로 해쉬되는 경우
Simple Uniform Hashing

 

해쉬함수와 Key

① 해쉬함수에서 Key는 자연수로 가정함.
   - 문자열이면 ASCII 코드로 변환하여 사용함
② 나눗셈 방법 : Key를 m으로 나눈 나머지를 h(k)값으로 사용
   - m은 2ⁿ은 피하고, 2ⁿ에 가까운 소수가 유리함

 

Open Addressing

선형프로빙 Linear Probing의 개념

일반적인 해쉬 함수가 주어졌을 때 보조 해쉬 함수를 사용해서 선형 프로빙을 하는 방식
선형적인 형태로 충돌이 발생하면 1씩 증가하면서 빈 slot을 찾는 작업을 반복한다.
h(k,i) = ( h'(k) + i ) mod m

 

선형프로빙 Linear Probing의 방식

같은 해시 h(k)값이 나오면 빈 슬롯이 나올 때까지 해쉬테이블을 탐색함.
 ① 삽입 : h(k)값에 빈 슬롯이 나오면 key을 삽입
 ② 탐색 : h(k)값의 위치에서 빈 슬롯이 나올 때까지, 혹은 값을 찾을 때까지 하나씩 이동하면 탐색함.
 ③ 삭제 : 실제로 값을 지우는 경우, "DELETED"라고 표기함.

 

 

선형프로빙 Linear Probing의 장단점

구현은 매우 쉬우나 Primary Clustering 문제가 있다.
  * 충돌이 많이 발생하면 slot이 끝 부분에 뭉쳐있는 경우가 있다.
값이 들어있는 slot의 수가 많으면 평균 검색시간이 증가한다.

 

 

 

이차식 프로빙 Quadratic probing의 개념과 장단점

m의 값을 17이라고 가정했을 때, h(10)의 값과 h(27), h(61)의 해쉬함수 값은 10으로 동일하다.

h(10)이 먼저 들어왔다고 가정하면 key가 10 자리에 위치하게 된다. 이어서 27이 들어오면 10자리에서 충돌이 발생하게 된다. 그러면 h(27)을 10 + 1*1의 자리에 저장한다.  마찬가지로 h(61)은 10 + 2*2의 위치에 저장한다. 

 

h( k ) = h( k ) + i² 

 

장점 : 충돌이 일어났을 때 위치를 3i²로 밀어주기 때문에 Primary Clustering을 줄일 수 있음
단점 : Secondary Clustering 문제가 있다.
     * 처음 시작 값이 같으면 매번 계산할 때 마다 이전 key 값과 동일한 위치(3i²)만큼 이동하기 때문에 반복적으로 충돌이 일어나게 된다.

 

*https://www.geeksforgeeks.org/quadratic-probing-in-hashing/

이중 해싱 Double Hashing

충돌이 일어나면 해싱 함수를 두 번 적용한다.

h₁(k) = k mod 13
h₂(k) = i + ( k mod 13 )
h(k,i) = (h₁(k) + i * h₂(k)) mod 13

예를 들어 m이 13d일 때, 11과 37이 들어온다고 가정한다.  h(11)의 해쉬함수 값은 11이 된다. h(37)의 해쉬함수 값도 11이기 때문에 충돌이 일어난다. 이때 해싱 함수를 두번 적용하여 37의 저장위치를 찾아준다.

 ( h(37) + h(37) * 1 ) mod 13 인 23을 h(37)의 저장위치로 지정한다.

 

* https://www.geeksforgeeks.org/double-hashing/

이중 해싱 Double Hashing의 주의점

① h₂(k) 함수값은 해쉬 테이블의 크기 m과 서로소 관계여야 한다.
    (2의 배수이면 매번 해쉬테이블의 중간으로 돌아오는 것을 반복하게 됨)
② m값 설정 주의사항
  - m을 2의 지수승으로 두고, h₂(k)를 홀수로 한다.
  - m을 소수로 하고 h₂(k)가 m보다 작은 양수로 한다.

 

 

 

* 참고자료

https://en.wikipedia.org/wiki/Hash_table

Hash table - Wikipedia

https://en.wikipedia.org/wiki/Linear_probing

Linear probing - Wikipedia

 

T아카데미 컴퓨터 알고리즘 기초 10강 해쉬 알고리즘(1)

T아카데미 컴퓨터 알고리즘 기초 10강 해쉬 알고리즘(2)