코딩 인터뷰 핵심 자료구조 - 해시 테이블(Hash Table)

이번 포스팅에서는 해시 테이블에 대해 소개해볼까 합니다.

 

해시 테이블은 매우 중요한 주제이자 개발자로서 기본기입니다.

이 자료구조를 아주 능숙하게 다룰 수 있도록 노력해야 합니다.

 

해시 테이블(Hash Table)

해시 테이블(hash table)은 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킵니다.

해시테이블을 구현하는 방법은 여러 가지가 있지만, 간단하면서도 흔하게 사용되는 구현 방식에 대해 설명하겠습니다.

 

해시 테이블 구현 방법

첫 번째 - 연결리스트를 이용한 방법

첫 번째 방법은 연결리스트(linked list)와 해시 코드 함수(hash code function)만 있으면 됩니다.

키(key)는 문자열 혹은 다른 어떤 자료형도 가능합니다.

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

 

1. 키의 해시 코드를 계산합니다. 키의 자료형은 보통 int 혹은 long이 됩니다. 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다는 사실을 명심해야 합니다.
2. 그 다음엔 hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구합니다. 물론 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리킬 수도 있습니다.
3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재합니다. 키와 값을 해당 인덱스에 저장합니다. 충돌에 대비해서 반드시 연결리스트를 이용해야 합니다. 여기서 충돌이란 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말합니다.

키에 상응하는 값을 찾기 위해서는 다음의 과정을 반복해야 합니다. 주어진 키로부터 해시 코드를 계산하고, 이 해시 코드를 이용해 인덱스를 계산합니다. 그 다음엔 해당 키에 상응하는 값을 연결리스트에서 탐색합니다.

충돌이 자주 발생한다면, 최악의 경우의 수행 시간(worst case runtime)은 O(N)이 됩니다(N은 키의 개수). 하지만 일반적으로 해시에 대해 이야기할 때는 충돌을 최소화하도록 잘 구현된 경우를 가정하는데 이 경우에 탐색 시간은 O(1)입니다.

 

두 번째 - 균형 이진 탐색 트리(balanced binary search tree)

두 번째 구현 방법은 균형 이진 탐색 트리를 사용하는 방법입니다.

이 경우에 탐색 시간은 O(logN)이 됩니다. 이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있습니다. 또한 키의 집합을 특정 순서로 차례대로 접근할 수 있는데, 어떤 경우에는 이런 기능이 유용하기도 합니다.