해쉬 테이블(HashTable)

해쉬 테이블은 map,multimap과 마찬가지로 key를 통해 data를 저장하는 자료구조로서 data의 탐색속도가 매우 빠르다.

 

해쉬 테이블은 기본적으로 배열로 동작한다. 자료를 저장할 때 key값을 배열의 인덱스로 바꾸는 해싱 함수를 통해 적절한 배열의 인덱스에 저장 한다. 

 

 

이 배열을 버켓이라고 한다. (리스트로 따진다면 Node)

 

ex ) idnex = hash_function(key) % arrSize; 

 

이런 식으로 자료를 탐색 및 추가 삭제 하기 때문에 매우 빠른 속도를 자랑하는데 여기에는 항상 문제가 따른다. 

hadh_function(key) % arrSize를 통해 나온 인덱스가 중복될 수 있다는 점이다. 

예를 들어 int를 키값으로 하는 해쉬테이블을 구현했는데 hash_function의 내부 코드가 return key % 5; 라고 가정하고 arrSize가 5라고 가정할때 5,10,15등의 값은 같은 인덱스를 가르키게 된다. 이런 식의 문제를 해싱충돌이라고 하는데 이를 해결하는 대표적인 몇가지 방법이 존재한다. 

 

1. Hash Chaining (해쉬 사슬)

각 버켓에 연결 리스트에 대한 포인터를 가지는 해결방법으로 해싱함수를 통해 나온 인덱스가 충돌을 일으키면
해당 버켓에 연결 리스트 노드를 추가해서 포인터로 잇는다. 

데이터를 탐색 할 때에는 key에 대한 index를 구한뒤 해당 버켓의 리스트를 선형 탐색하면서 key값의 데이터를 찾으면 된다.  

 

JDK에서는 버켓의 리스트 size가 8개 이하 일 때에는 연결 리스트를 사용하고 8개 이상일 때에는 Tree구조로 바뀌게 되어 있다. Tree구조로 바뀌고 자료가 삭제될 때 Tree의 노드가 6개 이하가 되면 다시 연결리스트로 바뀌게 되어있다. 

 

2. Linear Probing (선형 탐색)

선형 탐색 방식은 index에 대한 충돌이 발생 했을 경우 해당 index 뒤에 있는 버켓중에서 빈 버켓을 찾아서 데이터를 삽입한다. 자료를 탐색 할 때에는 해싱함수 % arrSize로 나온 인덱스부터 순차적으로 같은 키값의 버켓을 찾으면 된다. 

 

 

LinearProbing(선형 탐색) 방법의 경우에는 계속해서 자료를 추가 하기 위해서는 벡터와 같이 배열의 크기를 확장 해주어야 한다. HashChaining의 경우에도 마찬가지로 자료가 많아지면 연결 리스트의 노드 수가 많아 지기 때문에 탐색 속도에 많은 저하를 줄 수 있다. 이러한 이유때문에 해쉬 테이블은 버켓이 일정 수 이상이 되면 새로 배열을 확장해 주어야 하는데 JDK의 경우 default값으로 배열을 16개씩 확장한다. 

 

해쉬테이블은 충돌이 없는 상황에 한해서 시간복잡도 O(1)을 지향한다. 시간복잡도는 O(1)이지만 공간을 미리 할당해 두어야 한다는 점에서 공간 효율적이지는 않다. 

그리고 해쉬테이블의 경우 키값의 충돌이 적다는 가정하에서 매우 빠른 탐색속도를 가지지만 잦은 자료의 삽입,삭제에 대해서는 배열의 확장이 일어나기 때문에 이런 경우에는 트리 구조를 사용하는 것이 더 유리하다고 생각된다.