해시테이블

해시테이블

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(Index) 삼아 데이터의 값(value)을 키와 함께

저장하는 자료구조를 해시테이블(hashtable)이라고 합니다. 이 때 데이터가 저장되는 곳을 버킷(buket) 또는 슬롯(slot)이라고 합니다.

 

 

Direct-address table

키의 전체 갯수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 합니다. 

Direct-address table의 장점은 키 갯수와 해시테이블 크기가 동일하기 때문에 해시 충돌문제가 발생하지 않는다는 겁니다.

하지만 전체 키 중 실제 사용되는 키의 갯수가 적을 경우 메모리 효율성이 크게떨어집니다.

 

 

그러면 충돌이란 무엇일까요??

해시함수는 해시값의 갯수보 대개 많은 키값을 해시값으로 변환하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시 충돌이 발생하게 됩니다.

 

그래서 충돌 해결법으로는 대표적으로 체인법 (Seperate Chaining) , 개방번지화 (OpenAddressing) 이 있습니다.

 

체인법 (Seperate Chaining) :

해시충돌 문제를 해결하기 위한 간단한 아이디어 가운데 하나는 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것입니다. 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현(연결리스트)하기 때문에 체인이라고 합니다.

 

그래서 해시테이블의 시간복잡도는 평균적으로 O(1)을 갖지만 충돌이 빈번하게 일어나면 최악의  경우인 O(n)의 시간복잡도로 수렴할 수 있습니다.

 

 

개방번지화 (OpenAddressing):

open addressing은 chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블입니다. 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지에서 open addressing이라고 합니다. 해시충돌이 빈번히 생길 수 있습니다.

 

 

1) 선형탐사(Linear probing)
최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(예컨대 1칸)을 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)합니다. 여기에 데이터가 있으면 고정폭으로 또 옮겨 액세스합니다.

2) 제곱탐사(Quadratic probing)
최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 그 폭이 제곱수로 늘어
난다는 특징이 있습니다. 예컨대 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면 1^2칸
을 옮깁니다. 여기에서도 충돌이 일어나면 이번엔 2^2칸, 그 다음엔 3^3칸 옮기는 식입니다.

3) 이중해싱(Double hashing)
탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법입니다. 2개의 해시함수를 준비해서
하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사
용합니다.