해시테이블(HashTable)

해시 테이블

---

해시 테이블(hash table)은 효율적인 탐색을 위한 자료구조로 키(key)를 값(value)에 대응시킨다.

해시 테이블을 간단히 구현하는 경우, 배열과 해시 함수(hash function)만 있으면 된다.

객체와 키를 해시 테이블에 저장할 경우, 해시 함수가 키를 정수값으로 대응 시키는데, 이 정수 값이 배열의 첨자(index)로 쓰인다. 객체는 배열의 해당 첨자 위치에 저장된다.

하지만.. 이것은 정상적으로 작동하지 않을 수 있다. 왜냐하면 해시 함수가 계산하는 모든 키 값이 유일(unique)해야 하기 때문이다. 해시함수 후에 나오는 결과가 동일한 결과가 나올 경우 우리는 이것을 충돌(collision)이라고 한다. 충돌(collision)을 피하려면 모든 키 값을 고려해서 배열을 극도로 크게 만들어야 한다.

하지만.. 배열을 극도로 크게 만드는 것은 비효율적이기 때문에, 배열은 더 작게만들고 객체를 hash(key) % array_length 위치에 연결리스트(linkedlist) 형태로 저장하는 방법을 사용할 수도 있다. (특정한 키 값을 갖는 객체를 찾아내려면, 해당 키에 대한 연결 리스트를 탐색)

(이미지 출처)

이진 탐색 트리(binary search tree)를 사용해 해시 테이블을 구현할 수도 있다. 그렇게 하면 O(logn)의 탐색시간을 보장할 수 있다. 트리의 균형(balance)를 유지할 수 있기 때문이다. 처음에 배열을 크게 잡아둘 필요도 없기 때문에 저장 공간도 절약된다.

(참고 : 코딩인터뷰 완전분석)