[ 비선형 자료구조 ] 해시 테이블(Hash Table)

1. 해시 테이블

  해시 테이블은 key-value 쌍으로 데이터를 저장하는 자료구조입니다. 해시 테이블은 내부적 배열을 이용하며, 각 key에 해시 함수를 적용해 얻은 인덱스에 value를 저장합니다. 이때 value가 저장되는 장소를 슬롯이라 하며, 이러한 특성을 바탕으로 데이터 검색에서 빠른 퍼포먼스를 보여줍니다. 즉, 해시 테이블에서 각 key는 대응되는 인덱스를 가지며 O(1)의 시간 복잡도를 보여줍니다.(해시 테이블에 데이터가 찰수록 충돌 발생 가능성이 높아지고 가용 가능한 슬롯의 검색에 대한 비용이 추가되어 O(N) 까지 증가할 수 있습니다.)

 

  해시 함수는 문자열 혹은 다른 데이터 타입의 인풋 인자를 받아 인풋 인자에 대응하는 고유하고, 고정된 사이즈의 아웃풋(일반적으로 수 혹은 문자열)을 출력하는 함수 입니다. 이때 인풋 인자를 key, 아웃풋을 hash value 혹은 hash code라 하며 과정 자체는 hashing이라고 합니다. 

 

2. 해시 값의 충돌

    value가 저장되는 곳을 버킷 혹은 슬롯이라 합니다. 키와 대응되는 슬롯의 크기가 동일한 경우 direct address table 라고 하며, 이 경우 실제 사용하지 않는 키가 많아 메모리 낭비가 심해지는 문제가 있습니다. 그렇기에 일반적으로 슬롯의 크기를 실제 사용하는 key의 개수보다 적게하며 이를 hash table이라 합니다.

 

  해시 테이블이 가장 큰 문제점은 충돌입니다. 서로다른 key에 해시함수를 적용해 얻은 해시값이 같아 동일한 슬롯에 저장되는 경우를 충돌이라 합니다. [해시 테이블 크기 / 키 개수]로 나타내는 load factor(α)는 해시테이블의 한 슬롯에 평균적으로 몇 개의 키가 할당되는지 나타내는 지표이며, load factor가 1 보다 큰 경우 해시 충돌 문제가 발생할 가능성이 더욱 높아집니다.

 

  해시 충돌 문제는 chaining, open addressing, 해시 함수 개선 등의 기법을 통해 최소화됩니다. chaining의 경우 해시 테이블의 크기를 동적으로 조절하는 방법이며 open addressing의 경우 고정적인 해시테이블에서 빈 슬롯을 찾는 데 초점을 맞춘 방법입니다.

 

(1) chaining

 

  체이닝이란 슬롯에 저장되는 데이터수에 제한을 두지 않는 방식입니다. chaining은 슬롯에 이미 저장된 데이터가 존재한다면 연결리스트처럼 노드를 추가해 다음 노드(데이터)를 가리키는 방식으로 모든 자료를 담을 수 있도록 합니다. 즉, 모든 데이터는 연결 리스트와 같은 방식을 취하게 됩니다.

 

  체이닝에서 데이터의 저장은 연결리스트 방식을 따르며 데이터의 추가는 head에서 이루어집니다. 따라서 O(1)의 복잡도를 갖습니다.  추가, 삭제, 탐색의 시간복잡도는 아래와 같습니다.(a는 해당 슬롯의 데이터 크기를 나타냅니다.)

1. 추가 : O(1) / 해싱( O(1) ) + 추가( O(1) )
2. 삭제 : O(1 + a) / 해싱( O(1) ) + 탐색( O(a) )
3. 탐색 : O(1 + a) / 해싱( O(1) ) + 탐색( O(a) )

  즉, 체이닝 방식의 경우 탐색과 삭제의 복잡도는 슬롯의 요소의 개수에 좌우되며, 한 슬롯에 모든 요소가 저장된 경우 O(n)의 복잡도를 가질 수 있습니다.

 

(2) open addressing

  open addressing은 해시 충돌이 발생한 경우 다른 주소를 사용하는 것을 허용하는 방식입니다. 이때, 다른 주소를 찾는 과정을 probing 이라 합니다. probing엔 여러 종류가 있으며 이 글에서는 선형 탐사(linear probing), 제곱 탐사(quadratic probing), 이중 해싱(double hashing) 방식을 소개하겠습니다.

 

선형 탐사(linear probing)

  최초 해시값에 대응하는 슬롯이 사용중이면 다음 슬롯의 사용 여부를 확인하고 빈 슬롯이 나올 때 까지 다음 슬롯으로 이동하는 방식입니다. 이 방식은 충돌이 일어날 경우 특정 슬롯 주변에 클러스터링을 유발할 가능성이 크고, 그 결과 데이터가 밀집되어 있는 부분에서의 probing에 비용이 많이들게 되는 문제점 있습니다.

 

제곱 탐사(quadratic probing)

  슬롯을 옮기는 폭을 고정값이 아닌 [1 -> 4 -> 9 -> 16 -> ...]과 같이 제곱수로 늘어나는 탐사 방식입니다. 즉, 다음 슬롯의 위치를 특정하기 위해 이차함수를 사용합니다. 이 방식 또한 클러스터링이 발생할 가능성이 있습니다. 특히, 처음 해시값이 동일할 경우 이어지는 해시값들 또한 동일한 값으로 계산되기에 충돌이 반복적으로 발생하는 secondary clustering이라는 문제점을 가집니다.

 

이중 해싱(double hashing) 

  이중 해싱은 제곱 탐사에서의 secondary clustering 문제를 해결하기 위한 방법입니다. 이중 탐사는 명칭에서 알 수 있듯이 해시 햄수가 2개로 구성되며, 처음 해시함수로 해시값을 찾고 충돌이 발생했을 경우 두 번째 해시함수로 probing을 진행합니다.

 

(3) 해시 함수 개선

 

나눗셈법(division method)

  key를 해시 테이블의 크기(m)으로 나눈 나머지를 해시값으로 반환합니다. 예를 들어, 테이블의 사이즈가 100이라 가정하고 key가 23이라 한다면, 해시값은 23이 됩니다. 이러한 나눗셈법은 테이블의 크기가 소수일 때 해시값이 테이블 전체에 고르게 분포되게 하므로 테이블의 크기가 소수일 때 보다 효과적입니다.

 

곱셈법(multiplication method)

  key에 0~1사이의 값을 곱하고 결과값의 소수 부분을 반환합니다. 예를 들어, key가 113이고 곱해지는 값을 0.11이라 가정한다면 0.43을 반환합니다. 곱셈법은 나눗셈법 보다 더욱 균등하게 나누어진 해시값을 만들수 있습니다.

 

universal hasing

  여러 해시함수를 만들고 무작위로 선택해 해시값을 만드는 방식입니다. 이러한 방식은 모든 key 집합에 대해 충돌 가능성을 낮추는데 더 나은 성능을 제공할 수 있지만, 계산에 드는 비용이 크다는 단점이 있습니다.