해싱 : Hashing

대부분의 탐색 방법들은 탐색 키를 저장된 키값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다.

이에 반해 해싱은 키값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하는 방법이다. 키값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(Hash Table), 해시 테이블을 이용한 탐색을 해싱(Hashing)이라 한다.

기존의 탐색 방법들은 정렬의 유무에 따라 O(N), O(log N)이 있었다. 해싱은 이론적으로 O(1)의 시간 안에 탐색이 가능한 방법이다.

해싱은 배열을 사용하여 자료를 저장한다. 배열은 단점도 있지만 원하는 항목이 저장된 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있는 장점이 있는 자료구조이다. 그렇다면 배열의 인덱스를 어떻게 결정할까?

해싱은 키를 해시 함수(Hash Function)를 통해 해시 주소(Hash Address)를 생성하고 이 해시 주소가 배열로 구현된 해시 테이블(Hash Table)의 인덱스가 된다.

 

일반적인 해시 함수는 탐색 키를 해시 테이블의 크기로 나누어서 그 나머지를 해시 테이블의 주소로 하는 것이다.

 

하지만 M을 단순한 숫자로 하게 된다면 똑같은 해시 주소를 가리키게 되면서 충돌이 발생할 수 있다. 예를 들어 1~100의 정수가 있는데 M이 10이라면 1, 11은 똑같은 ht[1]을 가리키게 된다.

충돌이 발생하게 되면 저장할 공간도 부족해지고 탐색 시간이 길어진다. 이를 해결하기 위해 M을 해시 테이블의 크기보다 큰 소수로 한다면 충돌을 방지할 수 있다.

 

충돌을 해결하는 방법은 대표적으로 2가지가 있다.

• 선형 조사법(Linear Probing) : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
• 체이닝(Chaining) : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경

 

선형 조사법은 ht[k]에서 충돌이 일어난다면 그다음 주소인 ht[k+1]을 조사하여 빈 공간이면 저장하는 것이다. ht[k+1]도 이미 저장되어 있다면 계속해서 순차적으로 빈 공간을 조사한다.

선형 조사법은 탐색 시간이 많이 소요된다. 그 이유는 해시 주소가 다른 탐색 키하고도 비교해야하기 때문이다. 만약 해시 주소가 같은 탐색 키들을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것이다.

​

체이닝은 이를 해결하기 위해 리스트를 고정된 리스트가 아니라 삽입과 삭제가 용이한 연결 리스트로 구현하는 것이다. ht[k]에서 충돌이 일어난다면 ht[k+1]를 확인하는 것이 아니라 새로운 노드를 생성하여 저장한다.

한 가지 결정해야 할 것은 연결 리스트의 어디에다 새로운 항목을 삽입하느냐 하는 것이다. 탐색 키들의 중복을 허용한다면 연결 리스트의 처음에다 삽입하는 것이 가장 능률적이다. 중복이 허용되지 않는다면 연결 리스트를 처음부터 탐색하여야 하므로 어차피 연결 리스트의 뒤로 가야 하고 여기에다 삽입하는 것이 자연스럽다.