해슁/해싱 Hashing
key K를 해시함수값인 h(K)의 위치에 저장하는 자료구조.
Direct-Address 테이블에서의 공간 낭비를 줄이면서도, 시간복잡도를 낮추기 위해서 사용하지만 충돌문제가 있으며 이를 해결하기 위한 Chained Hash Table은 시간이 느려질 수 있음.
충돌
다른 Key K인데 해시함수값인 h(K)가 동일한 경우
체인을 이용한 충돌 해결법
중복되는 Key값이 있을 경우 해당 슬롯을 연결리스트로 저장한다.
수행시간
최악의 경우 : 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의 개념과 장단점
h(k,i) = ( k + i + 3i²) mod m
장점 : 충돌이 일어났을 때 위치를 3i²로 밀어주기 때문에 Primary Clustering을 줄일 수 있음
단점 : Secondary Clustering 문제가 있다.
* 처음 시작 값이 같으면 매번 계산할 때 마다 이전 key 값과 동일한 위치(3i²)만큼 이동하기 때문에 반복적으로 충돌이 일어나게 된다.
이중 해싱 Double Hashing
충돌이 일어나면 해싱 함수를 두 번 적용한다.
h₁(k) = k mod 13
h₂(k) = 1 + ( k mod 11 )
h(k,i) = (h₁(k) + i * h₂(k)) mod 13
이중 해싱 Double Hashingd의 주의점
① h₂(k) 함수값은 해쉬 테이블의 크기 m과 서로소 관계여야 한다.
(2의 배수이면 매번 해쉬테이블의 중간으로 돌아오는 것을 반복하게 됨)
② m값 설정 주의사항
- m을 2의 지수승으로 두고, h₂(k)를 홀수로 한다.
- m을 소수로 하고 h₂(k)가 m보다 작은 양수로 한다.
* 참고자료
https://en.wikipedia.org/wiki/Hash_table
https://en.wikipedia.org/wiki/Linear_probing
T아카데미 컴퓨터 알고리즘 기초 10강 해쉬 알고리즘(1)
T아카데미 컴퓨터 알고리즘 기초 10강 해쉬 알고리즘(2)
반응형