Data Structure 기본 개념 (2) - hash table

hash-table

해시 테이블은 해시 함수로 인덱스를 결정하여 O(1)의 시간 복잡도로 원하는 데이터를 찾기 위해 고안된 자료 구조이다. 어떤 값을 해시 함수를 거쳐 나온 결과 값을 인덱스로 하여 해당 인덱스의 버킷으로 바로 접근하는 아이디어이다. 당연히 해시 함수가 고르고(uniform) 무작위(random)하게 값을 해시해야 한다. 어떤 해시 함수가 고르고 무작위한지 증명하는 것은 매우 어려운 문제이기 때문에 완전히 고르고 무작위한 해시 함수를 만들기보다는 적당한 해시 함수를 사용하면서 충돌을 잘 처리해주는 방식을 사용한다. 충돌 처리를 위해서는 Overflow chaning, Open hashing 등의 방법을 사용한다.

앞서 말한 정적 해싱 방법은 충돌 처리가 실용적이지 않기 때문에 실제 자료 구조로 쓰기 위해서는 동적 해싱 방법을 사용하며, 동적 해싱을 이용한 자료 구조는 데이터베이스의 인덱스 방식 중 하나로 활용된다. 자꾸 데이터베이스를 예시로 쓰는 것 같지만, 실제로 데이터베이스는 자료 구조를 잘 활용해야 하는 프로그램 중 하나이기 때문에 자료 구조의 예로 많이 들 수밖에 없다. 동적 해싱 방법으로는 Exendible hashing, Linear hashing 등이 존재한다.

해시 충돌 (Hash Collision): 해시 함수로 해시를 산출하는 과정에서 서로 다른 key가 같은 hash로 변경되는 문제가 발생할 수 있는데, 이는 key 와 value가 1:1로 매칭이 되어야 한다는 규칠을 위배한 것이되므로 이 문제를 해결하면서 저장되어야 한다.

해시(hash)를 이용한 자료구조 방식에 필연적으로 나타날 수 있는 문제는,

무한한 값(해시테이블에서는 KEY를 의미한다.)을 유한한 값(해시 테이블에서는 Hash를 의미한다.)으로 표현하면서 서로 다른 두 개 이상의 유한한 값이 동일한 출력 값을 가지게 된다는 것이다.

Collision Resolution!!

1. Separate Chaining(간추려서 Chaining)

Sandra가 들어가는데 충돌이 일어나니 기존에 있던 John의 값에 연결시켰다.체이닝(Chaining)은 자료 저장 시, 저장소(bucket)에서 충돌이 일어나면 해당 값을 기존 값과 연결시키는 기법이다.

Chaining 장단점

• 장점
  1. 한정된 저장소(Bucket)을 효율적으로 사용할 수 있다.
  2. 해시 함수(Hash Function)을 선택하는 중요성이 상대적으로 적다.
  3. 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.
• 단점
  1. 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.
  2. 외부 저장 공간을 사용한다.
  3. 외부 저장 공간 작업을 추가로 해야 한다.

2. Open Addressing(개방주소법)

개방주소법은 데이터의 해시(hash)가 변경되지 않았던 chaining과는 달리 비어있는 해시(hash)를 찾아 데이터를 저장하는 기법이다. 따라서 개방주소법에서의 해시테이블은 1개의 해시와 1개의 값(value)가 매칭되어 있는 형태로 유지된다.

위의 그림을 보면, Sandra가 저장될때 해시가 John으로 채워져 있어서 그 다음 Hash에 Sandra를 저장했다. 그리고 Ted의 해시도 Sandra가 저장되어 있으므로 그 다음 해시에 Ted를 저장했다. 이처럼 비어있는 해시를 찾아 저장하는 방법을 Open Addressing라고 한다.

이 때, 비어있는 해시(Hash)를 찾는 과정은 동일해야 한다.(일정한 규칙을 따라 찾아가야 한다.)

Open Addressing는 위에서 언급한 비어있는 해시를 찾는 규칙에 따라 다음과 같이 구분할 수 있다.

• 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장한다.
• 제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장한다.
• 이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장한다.

Open Addressing의 장단점

• 장점
  1. 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
  2. 또 다른 저장공간에서의 추가적인 작업이 없다.
• 단점
  1. 해시 함수(Hash Function)의 성능에 전체 해시테이블의 성능이 좌지우지된다.
  2. 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다.

⇒ m / n = ɑ ( ɑ ≤ 1) 이 ɑ에 따라서 성능 차이가 남. 현재 버켓 차있는 양 / 전체 버켓 양

Hash Table의 단점

• 순서가 있는 배열에는 어울리지 않는다.

  상하관계가 있거나, 순서가 중요한 데이터의 경우 Hash Table은 어울리지 않다. 순서와 상관없이 key만을 가지고 hash를 찾아 저장하기 때문이다.

• 공간 효율성이 떨어진다.

  데이터가 저장되기 전에 미리 저장공간을 확보해 놓아야 한다. 공간이 부족하거나 아예 채워지지 않은 경우가 생길 가능성이 있다.

• Hash Function의 의존도가 높다.

  평균 데이터 처리의 시간복잡도는 O(1)이지만, 이는 해시 함수의 연산을 고려하지 않는 결과이다. 해시함수가 매우 복잡하다면 해시테이블의 모든 연산의 시간 효율성은 증가할 것이다.

⇒ 하지만 가장 큰 장점으로는 키 / 밸류는 저장하고 그것을 찾는데 빠른 속도로 찾을 수 있다는 장점이 있다.

ref

정주홍님의 블로그

ratsgo님의 블로그