해시 테이블에 대하여 (about Hash Table)

해시 테이블은 한마디로

 

공간을 팔아 시간을 사다

 

라는 말로 표현할 수 있다. 주소를 이용해서 배열같이 직접 탐색이 가능하다.

 

해시테이블의 기본 개념은 다음과 같다.

 

데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여

테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것,

 

이것이 바로 해시 테이블의 기본 개념이다.

해시테이블은 특이하게도 데이터가 입력되지 않은 여유공간이 많아야 제 성능을 발휘할 수 있다.

 

테이블 내의 주소를 계산할 때는 해시함수를 이용하는 데 이에는 두가지 방법이 사용된다.

 

1) 나눗셈법

 주소 = 입력값 % 테이블의 크기

 하지만 이는 충돌과 클러스터 문제가 발생할  가능성이 높다.

 

2) 자릿수 접기

 Hello -> 72 + 101 + 108 + 111 = 500

 하지만 이는 문자열 키가 고정일 경우 해시테이블의 전체크기를 전부 활용못할 수가 있는데,

이는 따로 루프 반복시마다 왼쪽으로 남은 비트씩 끌어올림으로써 해결 할 수 있다.

 하지만 이 역시 충돌 문제는 해결하지 못한다.

 

 

그래서 충돌문제 해결을 위한 방법이 등장한다.

1) 개방 해싱(Open Hashing) : 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습

2) 폐쇄 해싱(Closed Hashing) : 처음에 주어진 해시 테이블의 공간 안에서 문제를 해결

 

 

 개방 해싱 기법에는 Chaining이 있는데 이는 해시 테이블이 데이터 대신 링크드 리스트에 대한

포인터를 관리한다. 링크드 리스트에 데이터 삽입 시에 테일 다음에 붙이면은 탐색비용이 소요되므로

헤드에 붙인다.

 

 체이닝은 순차탐색으로 해시테이블의 '극한의 탐색'을 위해 고안된 성능을 훼손시키므로

해시테이블 + 이진트리탐색( 특히 레드 블랙 트리)를 사용하여 이 문제를 해결한다.

 

 개방 주소법(Open Addressing)은 충돌이 일어날 때 해시 함수에 의해 얻어진 주소가 아니더라도

얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘이다.

 이에 비해 체이닝은 해시 함수에 의해 얻어진 주소만 사용하므로 오픈 해싱 기법인 동시에

폐쇄 주소법(Closed Addressing) 알고리즘이기도 하다.

 

 개방 주소법은 탐사가 중요하다.

 

1) 선형탐사(Linear Probing) : 가장 간단한 탐사방법으로 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가

입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동. 클러스터 문제가 발생한다.

즉 클러스터가 발생하면 새로운 주소를 찾기위해 수행하는 선형 탐사 시간이 길어지고 이로 인해 해시 테이블의

성능은 엄청나게 저하된다.

 

2) 제곱탐사(Quadratic Probing) : 선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해

제곱탐사는 이동폭이 제곱수로 늘어나는 점이 다를 뿐이다. 이 역시도 클러스터 문제가 발생한다.

 

3) 이중 해싱(Double Hashing) : 클러스터 발생 방지를 위해 탐사 주소의 규칙성을 없애버린다. 한가지 아이디어로

rand()를 이용한 난수를 생각할 수도 있겠지만 같은 키를 입력하면 항상 같은 해시 값(주소)를 얻을 수 있어야

하는데, rand()함수를 이요하면 항상 다른 값을 얻게 되므로 적절한 답은 아니다. 이중 해싱은 이동폭을 제2의

해시 함수로 계산한다. 즉 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 사용하고 또 다른 하나는

충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다.

 

 만약 아무리 성능이 뛰어난 충돌 해결 알고리즘도 해시 테이블의 여유공간이 모두 차버려서 발생하는 성능 저하는

당해낼 방법이 없다. 그래서 남은 공간이 거의 없는 해시 테이블에서는 허구헌날 연쇄충돌이 일어날 것이다.

 재해싱(Rehashing)은 이 문제를 해결할 수 있는 방법 중 하나로, 재해싱은 해시 테이블의 크기를 늘리고

늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 해싱한다.

 

 통계적으로 해시 테이블의 공간 사용률이 70% ~ 80% 에 이르면 성능 저하가 나타나기 시작한다. 그러니 재해싱을

이 전에 수행해야 성능저하가 나타나는 것을 막을 수 있다. 하지만 재해싱 역시 만만치 않은 오버헤드를 요구하기

때문에 재해싱을 수행할 임계치를 너무 낮게 잡는 것도 성능 저하의 원인이 되므로, 임계치는 75% 정도를

사용하는 것이 보통이다.

참고 문헌 : 뇌를 자극하는 알고리즘(한빛미디어, 박상현 저)

 

[출처] 해시 테이블에 대해서|작성자 힝아