[CS50] 자료구조 - 해시 테이블

해시 테이블은 '연결 리스트의 배열'이다. 여러 값을 몇 개의 바구니에 나눠 담는 상황을 생각해보자.

 

각 값들은 '해시 함수'라는 맞춤형 함수를 통해 어떤 바구니에 담길지가 결정된다.

 

각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다.

 

이와 같이 연결 리스트가 담긴 바구니가 여러 개 있는 것이 '연결 리스트의 배열', 즉 '해시 테이블'이 된다.

 

 

해시 테이블의 동작 원리

쉬운 예로 사람의 이름이 해시 테이블에 저장되고 해시 함수는 '이름의 첫 글자'인 경우를 생각해보자.

 

이 경우 알파벳 개수에 해당하는 총 26개의 포인터가 있을 수 있으며 각 포인터는 그 알파벳으로 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다.

 

해시 함수가 이상적이라면 각 바구니에는 단 하나의 값만 담기게 되어 검색 시간은 O(1)이 된다.

 

하지만 그렇지 않은 경우 최악의 상황에서는 단 하나의 바구니에 모든 값이 담겨 검색 시간이 O(n)이 될 수도 있다.

 

일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 실제로는 검색 시간이 거의 O(1)에 가깝다고 볼 수 있다.

 

 

성능

해시 테이블의 성능은 해시 함수의 품질과 해시 테이블의 크기에 크게 의존한다.

 

이상적인 경우 각 값이 고유한 바구니에 저장되어 검색 시간이 O(1)이 된다.

 

그러나 해시 함수가 부적절하거나 해시 테이블이 충분히 크지 않으면 여러 값이 동일한 바구니에 저장되어 검색 시간이 O(n)까지 증가할 수 있다.

 

일반적으로는 해시 테이블이 거의 O(1)의 검색 시간을 제공한다고 볼 수 있다.

 

 

References

https://www.boostcourse.org/cs112/lecture/119042?isDesc=false

모두를 위한 컴퓨터 과학 (CS50 2019)