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

해시 테이블(Hash Table)

• 해시 테이블은 (Key, Value) 형식으로 데이터를 저장하는 자료구조 중 하나로, 데이터를 빠르게 검색할 수 있는 자료구조이다.

• 해시 테이블의 검색 속도가 빠른 이유:
  내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시 함수(Hash Function)를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용하여 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷(Bucket) 또는 슬롯(Slot)이라고 한다.

• 해시 함수(Hash Function)를 사용해 Key 값을 index로 변환하는 과정을 해싱(Hashing)이라고 한다.

  

예를 들어 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 할 때,

먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "521-1234"로 전화번호를 저장하게 된다.
이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 따라서 해시 테이블의 평균 시간복잡도는 O(1)이다.

해시 함수(Hash Function)

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다.

해시 테이블에 사용되는 대표적인 해시 함수에는 다음과 같이 3가지가 있다.

1. Division Method
   숫자 key를 테이블의 크기로 나눈 나머지를 인덱스로 사용하는 방법이다.
   ( index = key % 테이블의 크기 )
   이 때, 테이블의 크기를 소수(Prime Number)로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋다. 예를 들어 Key값이 23일 때 테이블 사이즈가 7이라면 index는 2이다.

2. Digit Folding
   각 Key의 문자열을 ASCII 코드로 바꾸고, 그 값을 합하여 테이블 내의 주소로 사용하는 방법이다.
   예를 들어 "Ryan" 같은 문자열을 R->82 + y->121 + a->97 + n->110 = 410을 index로 사용하면 된다. 만약 index가 테이블의 크기를 넘어간다면 Division Method를 적용할 수 있다.

3. Multiplication Method
   숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 index로 사용한다. index = (KA mod 1) * m

이 외에도 다양한 해시 알고리즘이 존재하며, 필요하다면 사용자가 직접 해시 알고리즘을 만들 수도 있다.

• Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.
  
  

해시(Hash) 값이 충돌(Collision)하는 경우

해시 함수를 통해 index값을 구했을 때 중복이 생기면 충돌이 발생할 수 있다.
해시 테이블에서는 이러한 충돌이 발생했을 때
분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing)을 사용하여 문제를 해결할 수 있다.

분리 연결법(Separate Chaining)

분리 연결법이란 동일한 버킷(bucket)의 데이터에 대해 연결 리스트, 트리 등의 자료구조를 활용하여
다음 데이터의 주소를 저장하는 것이다.

위의 그림과 같이 동일한 버킷으로 접근할 경우, 데이터들을 연결해서 관리해준다.
예를 들어 "John Smith"와 "Sandra Dee"를 해시 함수로 변경하였더니 152라는 index로 충돌되었다면, 먼저 저장한 "John Smith"의 다음 원소로 "Sandra Dee"를 저장하면 된다.

이러한 chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 원소를 쉽게 삭제할 수 있다는 장점이 있다.
하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며, 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

개방 주소법(Open Addressing)

개방 주소법이란 추가적인 메모리를 사용하는 chaining 방식과 달리, 비어 있는 해시 테이블의 공간을 활용하는 방법이다. 개방 주소법을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

1. Linear Probing : 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.

2. Quadratic Probing : 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고, 그 다음 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

3. Double Hashing Probing : 해시된 값을 한 번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한 번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 더 많은 연산을 하게 된다.

개방 주소법(Open Addressing)에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되므로
Hash Table을 재정리 해주는 작업이 필요하다.

해시 테이블(Hash Table)의 시간 복잡도

각각의 Key값은 해시 함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있기 때문에
평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다.

하지만 데이터의 충돌이 발생한 경우,
Chaining에 연결된 리스트들까지 검색해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.

충돌을 방지하는 방법들은 데이터의 규칙성(클러스터링)을 방지하기 위한 방식이지만, 공간을 많이 사용한다는 단점이 있다. 만약 테이블이 꽉 차 있는 경우라면 테이블을 확장해주어야 하는데, 이는 매우 심각한 성능의 저하를 불러오기 때문에 가급적이면 확장을 하지 않도록 테이블을 설계해주어야 한다.
(통계적으로 해시 테이블의 공간 사용률이 70% ~ 80% 정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다.)

또한, 해시 테이블에서 자주 사용하게 되는 데이터를 Cache에 적용하면 효율을 높일 수 있다. 자주 hit하게 되는 데이터를 캐시에서 바로 찾음으로써 해시 테이블의 성능을 향상시킬 수 있다.