해시 테이블 토막 정리

 

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

해시테이블을 구현하는 방법은 여러 가지가 있다.

하지만, 간단하면서도 흔하게 사용되는 구현 방식에 대해서 설명하고자 한다.

 

간단한 해시테이블을 구현하기 위해선, 연결리스트와 해시 코드 함수만 있으면 된다.

키와 값을 해시테이블에 넣을 때는 다음의 과정을 거친다.

 

1. 처음엔 키의 해시 코드를 계산한다.

키의 자료형은 보통 int 혹은 long이 된다.

키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에

서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다는 사심을 명심하자.

 

2. 그 다음엔 hash(key) % array_length 와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.

물론 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있다.

 

3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다.

키와 값을 해당 인덱스에 저장한다.

충돌에 대비해서 반드시 연결리스트를 이용해야 한다.

여기서 충돌이란 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 

서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말한다.

 

키에 상응하는 값을 찾기 위해선 다음의 과정을 반복해야 한다.

주어진 키로부터 해시 코드를 계산하고,

이 해시 코드를 이용해 인덱스를 계산한다.

그 다음엔 해당 키에 상응하는 값을 연결리스트에서 탐색한다.

충돌이 자주 발생하면, 최악의 경우의 수행 시간은 O(N)이 된다. 여기서 N은 키의 개수이다.

하지만 일반적으로 해시에 대해 이야기할 때는 충돌을 최소화하도록 잘 구현된 경우를 가정하는데 이 경우에 탐색 시간은 O(1)이다.

 

또 다른 구현 방법으로는 균형 이진 탐색 트리를 사용하는 방법이 있다.

이 경우에 탐색 시간은 O(log N)이 된다.

이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다.

또한 키의 집합을 특정 순서로 차례대로 접근할 수 있는데, 어떤 경우에는 이런 기능이 유용하기도 하다.