[Data Structure] Hash Table
L-j-h-c opened this issue · 1 comments
Hash Table이란?
해시 테이블은 해시 함수를 통해 키가 저장될 자리를 키의 값으로 결정하는 자료구조이다.
특정 키를 검색, 삽입, 삭제하기 위해 사용할 수 있는 자료구조로 리스트, 검색 트리 등을 사용할 수 있는데, 해시 테이블은 여기에 걸리는 시간을 최대한 단축하고자 만들어진 자료구조이다.
배열을 이용한다면 평균 Θ(n) 시간이 걸리고, 일반적인 검색 트리를 이용하면 평균 Θ(log n), 최악의 경우 Θ(n) 시간이 걸린다.
그리고 균형 이진 검색 트리를 사용하면 최악의 경우에도 Θ(log n)을 보장 받을 수 있다. 이러한 자료구조도 좋은 성능을 낼 수 있지만, 더한 효율을 내기 위해서 만들어진 것이 해시테이블이다.
해시 테이블의 기본적인 아이디어는, 앞선 자료구조들이 새로운 키를 저장할 때처럼 기존의 값들과 비교를 통하여 작업을 진행하는 것이 아니라 키가 가진 값 자체로 자리를 정해주는 것이다. 키의 값을 통해 자리를 바로 알 수 있다면, 검색은 그 값에 따른 자리를 찾아서 존재 유무를 파악하면 되고, 삽입 또는 삭제의 경우에도 자리를 찾아가서 키를 삽입하거나 삭제할 수 있다.
특정 키를 해시 테이블에 저장하기 위해서는 키가 가진 값에 따라 자리를 정해주는 hash function이 필요하다. 만약 해시 테이블에 자리가 m개 존재한다면, 해시 함수는 0에서 m-1 사이의 값을 반환하면 된다. 배열의 인덱스로 자리를 정해주는 것이 일반적이기 때문에 해시 함수의 결과값은 정수형이어야 한다.
해시 테이블에서 발생하는 충돌(Collision), 그리고 적재율(Load Factor)
해시 테이블에서는 Collision을 해결할 방법을 반드시 가지고 있어야 한다. Collision(이하 충돌)은 특정 키가 할당받은 자리에 이미 어떠한 키가 저장되어 있어 충돌하는 것을 말한다. 이러한 충돌을 처리하는 것은 해시 테이블의 효율 또는 성질을 결정하는 핵심적인 부분이다.
그리고 이러한 충돌의 발생은 당연히 해시 테이블에 저장된 키가 많을수록 빈번할 것이다. 이러한 경향을 수치화하기 위해 적재율이라는 개념이 존재한다. 적재율은 테이블의 크기에 대한 저장된 키의 비율을 말하는데, 해시 테이블의 크기를 m이라고 하고, 저장된 키의 총 수가 n 이라면 적재율은 n/m이 된다. 적재율은 보통 α로 표현한다.
해시 테이블의 객체 구조
해시 테이블도 기본적인 index interface를 따르기 때문에 유사한 구조를 가지고 있다.
table[] : 해시 테이블 객체는 키를 저장할 공간인
numItems : 테이블이 가진 원소의 개수
search() : 테이블에서 원소 x를 검색한다
insert() : 테이블에 원소 x를 삽입한다
delete() : 테이블에서 원소 x를 삭제한다
isEmpty() : 테이블이 비었는지 알려준다
clear() : 테이블을 비운다
해시 함수와 해시 함수를 만드는 방법
앞서 설명했듯 해시 함수는 키의 값에 따른 테이블에서의 자리를 반환해주는 함수이다. 입력 키가 테이블 전체에 골고루 분산되어야 충돌 확률이 낮아지는데, 그렇기 때문에 해시 함수를 적절하게 잘 정의하면 해시 테이블의 성능이 향상된다.
즉, 두 키의 유사성과 해시값의 유사성에 관계가 없을수록 충돌 확률이 줄어드는 것이다.
해시 함수를 만드는 방법의 대표적인 방법으로 나누기 방법과 곱하기 방법이 있다.
나누기 방법은 키 값을 해시 테이블의 크기로 나눈 나머지를 사용하는 것인데 h(x) = x%m이 가장 기본적인 형태이다. 여기서 해시 테이블의 크기 m은 2의 멱수에 가깝지 않은 소수를 선택하는 것이 좋다.
곱하기 방법은 입력 값을 0과 1 사이의 소수로 대응시킨 다음 해시 테이블의 크기 m으로 곱하여 0에서 m-1로 대응시키는 방법이다. 곱하기 방법은 나누기 방법과는 달리 해시 테이블의 크기를 마음대로 잡을 수 있다는 장점이 있다. 컴퓨터의 메모리는 2의 멱수 크기로 할당되기 때문에 해시 테이블의 크기도 2의 멱수로 잡아주는 것이 좋다.
충돌의 해결
해시 함수까지 만들었으니, 이제 충돌을 해결하는 방법에 대해 알아보자.
충돌 해결 방법은 체이닝(chaining)과 개방 주소 방법 두 가지가 있다.
체이닝 : 충돌이 일어나는 키를 연결 리스트로 연결해주는 방법
체이닝 방법은 중복되는 키를 연결 리스트로 단순히 연결해주면 되기 때문에 적재율에 관계 없이 사용할 수 있다는 장점이 있다.
이론적으로도 개방 주소 방법보다 성능이 뛰어나지만, 실제로는 연결 리스트가 매 자리마다 필요하기 때문에 공간 낭비가 발생하고, 적재율이 높지 않을 것으로 예상되면 개방 주소 방법을 사용하는 것이 좋다.
개방 주소 방법 : 충돌이 일어나면 다음 자리를 계산하여 배치해주는 방법
개방 주소 방법은 충돌이 일어난 경우 다음 자리를 계산하여 배치해주는 방법인데, 검색의 과정에서도 마찬가지로 이러한 계산이 필요하기 때문에 효율이 떨어질 수 있다. 또한 적재율에 민감하다.
체이닝에서는 없지만 개방 주소 방법에서 발생할 수 있는 문제점으로 군집(Clustering)이 있다. 군집이 발생하면 다음 자리를 찾아가는 데에 오랜 시간이 걸리기 때문에 성능에 치명적이다. 따라서 다음 자리를 계산하는 방법을 잘 디자인해야 테이블의 성능을 높일 수 있다.
첫 번째 방법 : 1차원 탐색-Linear Probing
충돌이 일어난 자리에서 일차함수의 보폭으로 점프하여 자리를 찾는다.
h2(x) = (h1(x) + ai + b) % m와 같은 식을 가진다.
이러한 방법은 보폭 a에 따라 1차 군집이 형성될 수 있다는 문제점을 가진다.
두 번째 방법 : 2차원 탐색-Quadratic Probing
충돌이 일어난 자리에서 2차함수의 규칙을 가지고 점프하여 자리를 찾는다.
2차 함수를 사용하면 충돌이 일어난 군집에서 빠르게 벗어날 수 있다.
그러나 같은 초기 해쉬값을 가진 키들이 여럿 들어오면 여전히 동일한 자취를 취하며 자리를 찾아가기 때문에 문제가 생긴다.
이를 2차 군집이라고도 한다.
세 번째 방법 : 더블 해싱-Double Hashing
마지막 방법으로 2차 군집 현상을 해결할 수 있는데, 해쉬 함수를 두 종류 사용하는 것이다.
초기 해시 함수는 h(x)만 두고, 충돌이 발생한 경우 보폭으로 새로운 해시함수 f(x)를 곱해주는 것이다.
특정 키의 h(x) 해시값이 같아도 f(x)의 해시값이 같을 확률이 매우 낮기 때문에 2차 군집 현상을 해결할 수 있는 것이다.