[자료구조] 해시 테이블(hash table)

  대부분의 프로그래밍 언어는 해시 테이블(hash table)이라는 자료 구조를 포함하며, 해시 테이블에는 빠른 읽기라는 놀랍고 엄청난 능력이 있다. 해시 테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다.

 

  해시 테이블은 쌍으로 이뤄진 값들의 리스트다. 첫 번째 항목을 키라 부르고, 두 번째 항목을 값이라 부른다. 해시 테이블에서 키와 값은 서로 중요한 관계다. 해시 테이블의 값 룩업은 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다. 

해싱

  문자를 가져와 숫자로 변환하는 이러한 과정을 해싱이라고 부른다. 또한, 글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수라 부른다. 이밖에도 해시 함수는 많다. 또 다른 해시 함수 예제는 각 문자에 해당하는 숫자를 가져와 모든 수를 합쳐 반환하는 것이다. 또 다른 해시 함수 예제는 문자를 해당하는 모든 수를 곱해서 반환하는 것이다. 실제 쓰이는 해시 함수는 이보다 더 복잡하지만 이러한 "곱셈" 해시 함수를 사용하면 예제가 명확하고 간단해진다.

A = 1
B = 2
C = 3
D = 4
E = 5
...
ACE = 135
CAB = 312
DAB = 412

  사실 해시 함수가 유효하려면 딱 한 가지 기준을 충족해야 한다. 해시 함수는 동일한 문자열을 해시 함수에 적용할 때마다 항상 통일한 숫자로 변환해야 한다. 주어진 문자에 대해 반환하는 결과가 일관되지 않으면 그 해시 함수는 유효하지 않다. "곱셈" 해시 함수를 쓰면 BAD는 항상 8로 변환된다. B는 항상 2고, A는 항상 1이고, D는 항상 4이기 때문이다. 다른 결과는 있을 수 없다. 단, DAB는 BAD처럼 8로 변환되는 점은 문제가 되겠지만, 해시 함수의 개념을 이해하기에는 적절하다 할 수 있다.

유의어 사전 만들어 보기

  모든 단어에는 각각 연관된 동의어가 있으므로 동의어는 해시 테이블의 좋은 사용 사례다. 

다음과 같이 해시 테이블로 유의어 사전을 표현할 수 있다.

hash_table = {}

배열과 유사하게 해시 테이블은 내부적으로 데이터를 한 줄로 이뤄진 셀 묶음에 저장한다. 각 셀마다 주소가 있다.

첫 번째 항목을 해시에 추가해 보자.

hash_table["bad"] = "evil"

해시 테이블이 데이터를 어떻게 저장하는지 알아보자.

먼저 컴퓨터는 키에 해시 함수를 적용한다. 다시 말하지만 앞서 설명했던 "곱셈" 해시 함수를 사용해서 설명할 것이다.

BAD = 2 * 1 * 4 = 8

키 ("bad")는 9로 해싱되므로 컴퓨터는 값 ("evil")을 다음과 같이 셀 8에 넣는다.

이제 다른 키/값 쌍을 추가해 보자.

hash_table["cab"] = "taxi"

키를 해싱하면 CAB = 3 * 1 * 2 = 6 이 되므로 값 ("taxi")를 셀 6에 저장한다.

해시 테이블을 만들었으므로 해시 테이블에서 값을 어떻게 룩업 하는지 알아보자.

키 "bad"의 값을 룩업 하고 싶다면 hash_table ["bad"]를 가져와야 한다.

컴퓨터는 간단히 두 단계를 실행한다.

1. 컴퓨터는 룩업 하고 있는 키를 해싱한다. BAD = 2 * 1 * 4 = 8
2. 결과가 8이므로 셀 8을 찾아가서 저장된 값을 반환한다. 여기서는 문자열 "evil"이다.

각 항목의 값을 룩업 하려면 해당 항목을 찾을 때까지 순회하던 배열과 달리 해시 테이블은 더욱 빠르게 룩업 할 수 있다. 해시 테이블을 쓰면 실제 메뉴 항목을 키로 사용해서 해시 테이블 룩업 O(1)만에 할 수 있다. 이것이 바로 해시 테이블의 매력이다.

충돌 해결

  해시 테이블에도 문제는 있다. 바로 충돌의 문제이다. 해싱한 키가 동일해서 충돌이 발생한다.

hash_table["dab"] = "pat"

DAB = 4 * 1 * 2 = 8로 해싱되나 해당 셀에는 "evil"이 이미 존재하고 있다. 이 충돌을 방지해야 한다. 충돌을 해결하는 고전적인 방법 중 하나는 분리 연결법이다. 충돌이 발생했을 때 셀에 하나의 값을 넣는 대신 배열로 참조를 넣는 방법이다.

  이렇게 바꿨을 때 해시 테이블 룩업이 어떻게 동작하는지 차례대로 살펴보자.

1. 컴퓨터는 키를 해싱한다. DAB = 4 * 1 *2 = 8
2. 셀 8을 룩업 한다. 컴퓨터는 셀 8이 하나의 값이 아닌 배열들의 배열을 포함하고 있음을 알게 된다.
3. 각 하위 배열의 인덱스 0을 찾아보며 룩업 하고 있는 단어 ("dab")을 찾을 때까지 배열을 차례대로 검색한다. 일치하는 배열의 인덱스 1에 있는 값을 반환한다.

이렇게 해결하면 모든 데이터가 같은 셀에 존재한다면 배열보다 나을 것이 없다. 그래서 해시 테이블은 충돌이 거의 없이 룩업을 수행하도록 디자인해야 한다.

훌륭한 충돌 조정

  해시 테이블은 다음 세 요인에 따라 효율성이 정해진다.

• 해시 테이블에 얼마나 만은 데이터를 저장하는가
• 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
• 어떤 해시 함수를 사용하는가

해시 테이블에서 해시 함수는 사용 가능한 모든 셀에 데이터를 분산시킬 수 있어야 좋은 해시 함수가 된다. 좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피해야 한다. 충돌 조정을 위해 컴퓨터 과학자는 다음과 같은 경험에 기반한 규칙을 세웠다. 해시 테이블에 저장된 데이터가 7개면 셀은 10개여야 한다. 

 

데이터와 셀 간 이러한 비율을 부하율이라고 부른다. 이상적인 부하율은 0.7 ( 원소 7 / 셀 10개 )라고 할 수 있다.

 

처음에 해시에 데이터를 7개 저장했다면 컴퓨터는 셀 10개로 이뤄진 해시를 할당할 것이다. 하지만 데이터를 더 추가하기 시작하면 새 데이터가 새로운 셀들에 균등하게 분산되도록 컴퓨터는 셀을 더 추가하고 해시 함수를 바꿔서 해시를 확장할 것이다.

 

다행히 해시 테이블 내부는 대부분 사용자가 쓰고 있는 컴퓨터 언어가 관리한다.