[자료구조] 해시 테이블

학습 목표

해시 테이블의 원리와 구조를 설명할 수 있다.

왜?

연결리스트나 트리에서는 값을 검색할 때 O(n) 또는 O(log n)의 시간이 걸렸다. 이 시간을 조금 더 단축해서 거의 O(1)에 가깝게 할 수도 있을까?
이것을 가능하게 해주는 해시 테이블이라는 자료 구조에 대해서 알아보자.

1. 해시 테이블?

해시 테이블은 연결 리스트의 배열이다.
여러 값들을 바구니에 나눠 담는 상황을 생각해보자.
각 값들은 해시 함수라는 맞춤형 함수를 통해서 어떤 바구니에 들어갈지 결정이 된다.

 

각 바구니에 들어가있는 값이 여러 개라면 그 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다.
한 바구니에 1, 3, 4가 들어있다면 1, 3, 4는 연결 리스트로 이어진다.

 

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

2. 예시

해리포터에 등장하는 캐릭터들을 불러보자. 이 캐릭터들의 이름을 아래와 같이 하나씩 바구니에 넣을 것이다.

• 캐릭터의 이름은 해시 테이블에 저장이 되고, 해시 함수는 이름의 첫 알파벳인 경우이다.
• 알파벳이 총 26개이므로, 총 26개의 포인터가 있을 수 있고 각 포인터는 그 알파벳으로 시작되는 이름들을 저장하는 연결 리스트를 가리키게 된다.
• 이름의 첫 알파벳이 L인 경우, L을 가리키고 있는 포인터는 L로 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다.
  
  

3. 검색 시간

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

 

하지만 그렇지 않다면?
최악의 경우에는 하나의 바구니에 모든 값들이 담겨서 하늘까지 치솟아있다고 생각해보자. 이 경우에 검색시간은 O(n)이 될 수도 있다.

 

일반적인 경우라면, 해시 테이블은 최대한 많은 바구니를 만드는 해시 함수를 사용한다.
예를 들어, 그림에는 L 바구니에 Luna, Lilly, Lucius가 담겨져 있는데, L 바구니가 아닌 La...Li..Lu 이렇게 더 세분화 된 바구니를 만들어 놓는 것이다.
그렇기 때문에 검색 시간은 O(1)에 가깝다고 볼 수 있다.