[C/C++] Hash Table vs STL map

| Hash Table

해시 테이블의 값(value)은 키(key)에 대한 해시 함수를 호출하여 저장한다. 

1. 값은 정렬된 순서로 보관되지 않는다. 
2. 삽입 및 탐색 연산은 분할상환적으로 O(1) 시간에 수행된다. (충돌이 적다는 가정하에)
3. 잠재적 충돌을 고려하여 구현해야 한다. 보통은 충돌되는 값을 서로 연결하여(chaining)하여 이 문제를 해결한다. 
4. 즉, 특정 키에 대응되는 인덱스 위치에 모든 값을 연결 리스트로 묶는다. 

| STL map

키를 기준으로 만든 이진 탐색 트리에 키(key) / 값(value) 쌍을 보관한다.

1. 충돌을 처리할 필요가 없고
2. 트리의 균형이 유지되므로 삽입 및 탐색 시간은 O(logN)이 보장된다. 
3. key를 기준으로 정렬된 상태로 저장한다. 물론, 정렬하지 않은 상태로 저장하는 unordered_map 도 있다. 

---

| Hash Table은 어떻게 구현하나?

 해시테이블은 보통 연결 리스트 배열로 구현한다. 키와 값의 쌍을 저장하려면 해시함수를 사용해서 키값을 배열의 인덱스 값으로 대응시킨 다음에 해당 위치에 있는 연결 리스트에 값을 삽입한다. 

 배열 내 특정 인덱스의 연결리스트에 보관되는 값들은 동일한 키를 갖고 있지 않다. 같은 것은 hashFunction(key) 값뿐이다. 따라서 특정 키 값을 가지고 그에 상응하는 값을 추출하기 위해서는 각각의 노드에 값뿐만 아니라 키도 저장해야 한다. 

 

요약하자면, 해시 테이블은 연결 리스트의 배열이며, 연결리스트이 각 노드는 키와 값이 함께 저장되어 있다, 설계 시 유의해야 할 사항은 다음과 같다. 

1. 키들이 잘 분배되도록 좋은 해시 함수를 사용해야한다. 충돌이 많이 발생하면 원소를 찾는 성능이 떨어진다. 
2. 아무리 우수한 해시 함수를 쓰더라도 충돌을 피할 수는 없기 때문에, 충돌을 처리하는 방법을 구현해야 한다. 이 뜻은 대개 연결 리스트를 사용한다는 말이지만, 다른 방법도 있다. 
3. 용량에 따라 해시테이블의 크기를 동적으로 늘리고 줄일 수 있어야 한다. 만약 임계치를 초과한다면 해시 테이블의 크기를 늘려야 하는데, 이에 따른 연산 비용이 비싸므로 너무 자주 일어나지 않도록 해야 한다. 

 

| 입력되는 항목의 수가 적다면 ? 

 STL map이나 이진 트리를 사용할 수 있다. 물론 O(logN) 시간이 걸리겠지만 , 데이터 수가 적으므로 성능 저하는 무시할 만하다.

 

reference : ctci 6th book