개념
hash table이란 무엇일까?
hash table은 데이터와 그 데이터를 식별하는 key가 대응하는 자료구조입니다.
예를 들어 학생 인적 사항 관리에서는 학번과 학생 정보를 hash table로 관리하죠. 여기서 학번이 key가 되고 학생 정보가 value가 됩니다.
hash table의 특징은 뭘까?
hash table은 key를 통해서 data를 탐색하기 때문에 이상적인 경우 탐색과 삽입 삭제 모두 O(1)의 시간복잡도를 가집니다.
어떻게 그렇게 빠를 수 있죠?
hash table의 구현을 살펴보면 알 수 있습니다.
hash table은 배열을 기반으로 구현됩니다. 배열은 알다시피 ram을 기반으로 상수 시간에 접근할 수 있죠.
헌데 여기서 key를 그대로 사용할 수 없는 이유가 드러납니다. key는 사람의 이름, 매우 큰 정수, 실수 등 다양한 자료형을 가질 수 있습니다.
이렇게 다양한 key를 그대로 index로 사용할 수는 없는 노릇이죠.
그렇기 때문에 key를 hash(indices)로 바꾸어 hash와 data를 대응시키게 됩니다.
이때 key를 hash로 바꾸는 함수를 hash function이라고 부릅니다.
위에서 이상적인 경우에 O(1)이라고 했는데 그렇다면 최악의 경우는 어떤 경우인가요?
먼저 이상적인 경우는 hash가 key와 일대일 대응이 되는 경우입니다. 하지만 해시 함수의 한계, 공간의 낭비 등의 이유로 이렇게 만들기는 힘들죠.
그래서 보통 여러 개의 key가 한 개의 hash에 대응하게 됩니다.
최악의 경우는 모든 key가 하나의 hash에 대응하는 경우입니다.
이렇게 되면 결국 list처럼 모든 데이터를 일일이 찾아서 key를 비교해야하죠.
