해시테이블
원소의 값에 따라서 원소가 저장될 자리가 결정되는 구조의 자료구조
저장 원리
해시 테이블에 원소를 저장하려면 해당 원소의 해시값을 계산한다.
이 때 해시 값을 계산하는 함수를 해시 함수라고 한다.
따라서 계산만하면 해당 값이 있는지 바로 찾을 수 있는 편리함이 있다.
적재율
해시 테이블에 원소가 차 있는 비율은 해시 테이블 성능에 중요한 영향을 미친다.
이 비율을 적재율이라고 하며 적재율은 저장된 원소의 개수 / 해시 테이블의 크기로 계산한다.
해시 함수
키 값을 받아 해시 테이블상의 주소를 리턴하는 함수
해시 함수의 성질
- 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.(충돌 확률 ↓)
- 계산이 간단해야한다.
만드는 방법
나누기 방법
x를 적절한m으로 나눈 후 나머지를 취한다.
h(x) = x mod m
곱하기 방법
x에0<A<1인A를 곱한 후 소수부만 취한다.- 소수부에
m을 곱한다.
h(x) = m(xA mod 1)
충돌
해시테이블의 해시 함수를 사용했을 시에 저장되는 위치가 충돌하는 경우가 있을 수 있다.
원소를 해시 테이블의 크기로 나누는 해시함수라고 가정해보자
원소의 값 / 해시테이블의 크기
원소의 값이 해시테이블보다 크면 나머지가 같아 중복하는 값이 생길 수 있다.
충돌 처리
충돌을 처리하는 방법에는 크게 두가지 방법이 있다.
체이닝
체이닝 기법은 같은 주소로 들어오게 된 값을 연결리스트로 이어 관리하는 방법이다.
이어달기만 하면 되기 때문에 적재율이 1이 넘어도 사용할 수 있는 장점이 있다.
개방 주소 방법
체이닝과 달리 추가공간을 허용하지 않고 충돌이 일어나면 가진 공간에서 해결해서 모든 원소가 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.
선형 조사
i번째 충돌을 해결하는 해시함수는 다음과 같다
h(x) = (h(x)+i) mod m
이 때 m은 2의 제곱수에 근접하지 않는 소수로 고르는 것이 좋다.
특정 영역에 원소가 몰릴 경우 계속 다음 주소를 탐색해야하기 때문에 성능이 떨어지게 되며 이를 1차 군집이라고 한다.
이차원 조사
보폭을 이차 함수로 넓혀가면서 보는 방법
h(x) = (h(x)+c₁i² + c₂i) mod m
최초의 해시 값이 같은 원소들은 이득을 볼수가 없어서 비효율적이다.
이를 2차 군집이라고 한다.
더블 해싱
두 개의 해시함수를 사용하는 방법
h(x) = (h(x) + i*f(x)) mod m
f(x) = 1+(x mod n)
충돌이 생길 경우 두 번째 해시 값만큼 점프한다.
두 가지 해시함수를 잡을 시 n을 m보다 작은 소수로 잡는 것이 좋다.
또한 f(x)의 값이 테이블 크기와 서로소인 값이어야 한다.
=> f(x)의 값이 m 보다 작은 자연수가 되게 하면 항상 서로소가 된다. (선형조사 파트에 쓰인 것 처럼 m 이 소수이기 때문이다.)
