[Data Structure] 비선형 - Hash Table(해시 테이블)

Hash Table(해시 테이블)

해시 테이블은 '키-값'쌍으로 데이터를 저장하는 자료구조 중 하나로 빠른 검색, 빠른 삽입이 가능하다는 특징을 가진다.

해시 테이블이 빠르게 데이터에 접근할 수 있는 이유는 내부적으로 배열(버킷)을 사용해서 데이터를 저장하기 때문이다. 배열에 저장된 데이터를 데이터 고유의 인덱스로 접근하기 때문에 평균적으로 O(1)의 시간 복잡도로 검색할 수 있다. 고유 인덱스는 데이터의 키 값에 해시 함수(hash function)을 적용해 생성한다.

 

Hash Function

적절한 해시 함수를 사용하는 것은 매우 중요하다. 각각 데이터는 데이터 고유의 인덱스를 가져야 하는데, 어설픈 해시 함수를 사용할 경우 인덱스가 많이 겹치는 경우가 발생할 수 있기 떄문이다. 이 경우를 'collision(충돌)'이 발생했다고 한다. Collision이 많아질 수록 검색에 필요한 시간복잡도가 O(N)에 가까워지기 떄문에 해시 함수는 해시 테이블의 성능에 큰 영향을 미친다.

그렇다면 좋은 해시 함수는 키 값과 인덱스를 무조건 1대 1로 만들어 주는 함수일까?

꼭 그렇지도 않다. 무조건 1대 1로 만드는 것보다는 collision을 최소화하는 방향으로 함수롤 설계하고, collision에 적절히 대응하는 것이 중요하다. 무조건 1대 1로 대응되도록 만드는 것이 거의 불가능하기도 하지만, 그런 해시 함수를 만들어봤자 배열과 다를바 없고 메모리를 너무 차지하기 때문이다.

 

Resolve Conflict

Collision을 해결하는 방법은 크게 두 가지가 있다.

 

1. Open Addressing(개방주소법)

Collision이 발생하면 비어있는 다른 해시 버킷에 데이터를 넣는 방식이다.

다른 해시 버킷을 찾기 위한 대표적인 방법은 다음 세 가지가 존재한다.

• Linear probing
  Collision이 발생한 버킷부터 순차적으로 탐색에 비어있는 버킷을 찾는다.
  하지만 이 방법은 탐사 이동폭이 고정돼 있기 때문에 특정 해시값 주변 버킷이 모두 채워져 있으면 성능이 매우 떨어진다(primary clustering). 예를 들어 인덱스 1부터에서 100까지가 모두 채워져있는데 1에서 collision이 발생한다면 탐사를 100번 수행해야 저장할 수 있다.
• Quadratic probing
  고정폭으로 이동하는 대신 폭을 제곱수로 늘리는 방식이다. 예를 들어 처음 collision이 발생했을 때는 1212만큼, 다음에는 2222, 3232만큼 움직인다.
  이 방법 역시 서로 다른 키들이 동일한 초기 해시값을 가진다면 효율성이 떨어지게 된다(secondary clustering).
• Double hashing probing
  2개의 해시함수를 준비해 하나는 최초의 해시 값을 얻을 때, 하나는 collision이 발생했을 때 탐사 이동폭을 얻기 위해 사용한다.
  탐사할 해시 값의 규칙성을 없애버려 위에서 발생한 문제를 방지하는 기법이다.
  하지만 해시함수를 두 개 사용하기 때문에 위 두 가지 방법보다 많은 연산량이 필요하다.

Open addressing은 해시 테이블에 데이터가 얼마나 차있느냐에 따라 성능이 크게 영향받는다. 따라서 테이블에 데이터가 어느정도 차면 크기를 적절하게 늘리고 처음부터 다시 해싱하는 것이 좋다고 한다.

 

2. Seperate Chaining(분리연결법)

한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 헤시 테이블에 담는 방식이다. 유연하다는 장점을 가지지만 엔트리 수에 제한이 없는 만큼 메모리 문제가 발생할 수 있다.

Seperate chaining은 두 가지 방식으로 구현할 수 있다.

• Linked List
  각각의 버킷들을 연결 리스트로 만들어 collision이 발생하면 해당 버킷에 노드를 추가하는 방식이다.
  삭제 또는 삽입이 간단하다는 장점을 가지지만, 연결 리스트 자체의 오버헤드가 부담스럽다는 단점도 가진다.
• Tree(Red-Black Tree)
  연결 리스트 대신 트리를 사용하는 방식이다. 보통 버킷에 할당된 데이터가 많아지면 트리로 바꿔줘 성능상 이점을 챙긴다. 데이터 개수가 적을 때는 트리와 연결 리스트의 성능상 차이가 거의 없기 때문에 메모리를 덜 사용하는 연결 리스트를 사용하는게 좋다.

두 방식의 비교

두 방식 모두 worst case에서 O(M)(M은 버킷의 크기)를 가진다. Open addressing은 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋아 데이터의 개수가 충분히 적다면 separate chaining보다 성능이 좋다. Seperate chaining은 반면에 collision이 발생해도 같은 버킷을 사용하기 때문에 테이블의 확장을 늦출 수 있다는 장점을 가진다.