[자료 구조] 해시 테이블

해시 테이블(hash table)은 자료 구조의 하나입니다. '해시 함수'와 함께 데이터 검색을 효율적으로 하기 위해 사용되는 구조입니다. - 책 알고리즘 도감

 

 

해시 테이블은 키(Key)와 값(Value)이 한 쌍을 이루는 데이터를 저장합니다. 이 예에서는 각 사람의 성별을 데이터로 저장하고 있으며, 이름을 키로, 성별을 값으로 저장하고 있습니다.

 

 

 

 

해시 테이블의 특징을 비교하기 위해 먼저 데이터를 '배열'에 저장하는 경우를 생각해 보겠습니다.

 

 

 

6개의 상자로 이루어진 배열을 준비해서 데이터를 저장합니다. 여기서 Ally의 성별을 알고 싶다고 가정해봅시다. Ally가 배열의 몇 번째 상자에 저장돼 있는지 모르므로 앞에서부터 차례대로 확인해야 합니다. 이 처리를 '선형 탐색'이라고 합니다.

 

이처럼 선형 탐색은 데이터양에 비례해서 계산 시간이 늘어납니다. 배열 탐색에 시간이 걸리므로 탐색에는 적합하지 않은 구조라는 것을 알 수 있습니다.

 

 

 

이 문제를 해결해 주는 것이 해시 테이블입니다. 먼저, 데이터를 저장하기 위한 배열을 준비합니다. 여기에서는 5개의 상자로 구성된 배열을 만듭니다.

 

 

 

 

Joe의 데이터를 추가하는 경우를 같이 보겠습니다.

먼저 '해시 함수'를 이용해서 Joe의 키(문자열 'Joe')에 해당하는 '해시값'을 계산합니다.

여기에서는 4928이라는 결과가 나옵니다. 그다음 구한 해시값을 배열의 상자 수인 5로 나누어 나머지를 구합니다.

나눗셈의 나머지를 구하는 연산을 'mod 연산'이라고 합니다.

mod 연산 결과 3이라는 숫자가 나옵니다. 구한 수와 같은 배열의 3번 상자에 Joe의 데이터를 저장합니다.

 

 

 

만약에 겹치면!?

이 처리를 반복해서 다른 데이터도 하나씩 채워갑니다.

Sue는 1번 상자, Dan은 4번 상자에 들어가게 됩니다. 그런데 Nell 키의 해시값은 6276이라서 5로 mod 연산을 하면 1이 나오는데 1번 상자에는 이미 Sue의 데이터가 저장돼 있습니다. 데이터 저장 위치가 겹치는 것을 '충동'이라고 합니다.

이런 경우에는 리스트 구조로 기존 데이터와 연결합니다.

리스트로 기존의 데이터와 연결!

 

Ally 키의 해시값은 9143이므로 Ally도 3번 상자의 Joe와 리스트로 연결합니다.

Bob 키의 해시값은 5278이므로 Bob도 3번 상자의 Ally와 리스트로 연결합니다.

해시 테이블 완성

 

다음은 데이터 검색 방법을 알아보겠습니다. Dan의 성별을 확인하고 싶은 경우를 생각해 봅시다.

Dan이 배열의 몇 번 상자에 저장돼 있는지 알기 위해서 키인 'Dan'의 해시값을 구하고 배열의 상자 수인 5로 mod 연산을 합니다. 결과는 4이므로 4번 상자에 저장돼 있는 것을 알 수 있습니다. 그리고 배열의 4번 상자에 저장돼 있는 데이터의 키가 Dan과 일치하므로 대응하는 값을 추출합니다.

 

이번에는 Ally의 성별을 찾아봅시다. 먼저 Ally의 해시값을 구한 후 배열의 상자 수인 5로 mod 연산을 하면 3이므로 배열의 3번 상자로 가보지만 3번 상자에 저장돼 있는 데이터의 키는 'Joe'입니다. 따라서 'Joe'를 선두로 해서 만들어져 있는 리스트를 선형 탐색하여 Ally를 찾아내야 합니다.

 

---

<해설>

해시 테이블은 해시 함수를 이용해서 배열 내의 특정 데이터에 빠르게 접근할 수 있습니다. 한 편, 해시값에 mod 연산을 한 값이 충돌하더라도 리스트를 이용하고 있어서 저장할 테이터 수가 정해져 있지 않더라도 유연하게 대응할 수 있습니다.

 

해시 테이블에 사용하는 배열의 크기는 너무 작으면 충돌이 많아지고 선형 탐색의 빈도가 높아지게 됩니다. 반대로, 크기가 너무 크면 데이터가 없는 상자가 많아져서 메모리를 낭비하게 됩니다. 따라서 배열의 크기를 적절히 설정하는 것이 중요합니다.

 

<보충>

데이터를 배열에 저장할 때 충돌이 발생하는 경우는 리스트를 사용해서 기존 데이터의 뒤에 연결했습니다. 이 방법을 '연쇄법(또는 체이닝(chaining))'이라고 합니다.

 

충돌 시의 처리 방법에는 연쇄법 이외에도 몇 가지가 있습니다. 유명한 것으로 '개방 주소법(open addressing)'이라는 것이 있습니다. 이것은 충돌이 발생한 경우 다음 후보가 될 주소(배열 상의 위치)를 구해서 거기에 저장하는 방식입니다. 해당 주소에도 데이터가 존재한다면 다음 후보 주소를 구하며 비어 있는 곳을 찾을 때까지 다음번 주소를 구합니다. '다음 주소'를 어떻게 구하는 가는 해시 함수를 여러 개 사용하는 방법이나 '선형 탐색'등 몇 가지 방법이 있습니다.

 

데이터의 유연한 저장과 빠른 접근이 가능한 해시 테이블은 프로그래밍 언어의 연관 배열(associative array) 등에 사용되고 있습니다.

 

참고 - 책 알고리즘 도감