[Algorithm] 해시 테이블

해시 테이블

원소가 저장될 자리가 원소 값에 의해 결정되는 자료구조. 검색 효율의 극단.

저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한 번의 계산(해시함수)으로 자신의 자리를 찾는다.

하지만, 중요한 장애물이 있다. 계산을 통해 얻은 주소에 다른 값이 저장되어 있는 경우(충돌)

 

해시함수

키 값을 입력으로 받아 해시 테이블 상의 주소를 리턴한다.

두 가지 성질을 만족한다.

 

1) 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.

2) 계산이 간단해야 한다.

 

대표적인 방법으로 나누기 방법, 곱하기 방법이 존재한다.

나누기방법 : 테이블 크기(m)로 나누어 나머지를 주소 값으로 리턴한다.

곱하기방법 : A (0 < A < 1) 를 곱하고, 소수부에 테이블 크기(m)을 곱해 정수부를 주소 값으로 리턴한다.

 

충돌에 대한 해결

해시 테이블 내에 한 주소를 두고 두 개 이상의 원소가 자리를 다투는 것을 충돌이라 한다.

충돌 해결에는 크게 체이닝, 개방 주소 방식이 있다.

 

체이닝

해당 주소에 들어오는 값을 연결 리스트로 관리한다. 같은 주소 값을 가져도 연결 리스트로 추가할 수 있다.

 

개방주소 방식

체이닝과 다르게 추가 공간을 허용하지 않는다. 충돌이 일어날 경우 정해진 규칙에 따라 다음 자리를 찾는다.

선형 조사, 이차원 조사, 더블 해싱과 같은 방법으로 다음 주소 자리를 찾는다.

 

선형조사

충돌이 일어난 경우 바로 뒷 자리를 보는 것

i 번째 해시 함수는 i 만큼 떨어진 자리가 된다.

1차 군집의 문제가 발생할 수 있다. (특정 영역의 원소가 몰릴 때)

 

이차원 조사

충돌이 일어난 경우 i^2만큼 떨어진 자리를 본다.

i 번째 해시 함수는 i^2 만큼 떨어진 자리가 된다.

1차 군집 문제를 해결할 수 있으나, 여러 개의 원소가 동일한 해시 함수 값을 갖게 되면

모두 같은 순서로 조사할 수 밖에 없어 2차 군집 문제가 발생할 수 있다.

 

더블 해싱

두 개의 함수를 사용한다. 두 번째 해시 함수의 설계가 중요하다.

해시 함수 설계에서 가장 권장하는 방식으로

h(x) = x mod m

f(x) = 1 + (x mod m')으로 잡는 것. (m'은 m보다 조금 작은 소수)

 

개방주소 방식에서 주의할 점은 테이블에서 값을 삭제할 경우,

값이 있었던 자리라는 것을 표시해주어야 한다.

4번째 해시함수를 사용한 값을 찾으려 하는데, 3번째 해시함수 값이 삭제 되어있다면,

별도의 표시가 없으면 찾을 수 없기 때문이다.