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

❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.

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

각 값들은 ‘해시 함수’라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정 됩니다.
각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어집니다.

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

쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우를 생각해 보겠습니다.
그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 됩니다.


만약 해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담기게 될 것입니다.
따라서 검색 시간은 O(1)이 됩니다.

하지만 그렇지 않은 경우, 최악의 상황에는 단 하나의 바구니에 모든 값들이 담겨서 O(n)이 될 수도 있습니다.
일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 거의 O(1)에 가깝다고 볼 수 있습니다.

생각해보기

해시 함수는 어떻게 만들 수 있을까요?

x = 데이터 값, m = 해시테이블 크기

1. 나누기 방법
   데이터값(정수일 경우 그냥 사용, 문자(열)의 경우 아스키코드 사용)를 해시 테이블의 크기로 나누어 나머지의 값을 테이블 주소로 사용해 저장하는 방식.
   이 방법은 해시테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 수축시킨다.
   h(x) = x mod m
   
   
2. 곱하기 방법
   입력값을 0과 1 사이의 소수에 대응시킨 후, 해시 테이블 크기 m을 곱해 해시값을 0<h(x)<m에 대응시킨다.
   이 방법을 쓰려면 해시함수의 특성을 결정짓는 상수 A(0<A<1)를 미리 준비해야 한다.
   h(x) = [m(xA mod 1)]
   
   
3. 개방주소방법(충돌해결법 중 하나)의 경우
   • 선형조사법: h_i(x) = (h(x) + i) mod m
   • 이차원조사법: h_i(x) = (h(x) + c_1i^2 + c_2i) mod m
   • 더블 해싱: h_i(x) = (h(x) + if(x)) mod m -> 권장: h(x) = x mod m, f(x) = 1+(x mod m)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기