Hash Table 자료구조

Hash Table은 어떤 자료 구조인가요?

위와 같은 질문을 받았을때 핵심 답변은 아래와 같다고 생각한다.

hash table은 빠른 탐색을 위한 자료구조로써 key - value 쌍의 데이터를 입력받는다.

hash 함수 h에 키값을 입력으로 넣음으로써 얻은 해쉬값 h(k)를 위치로 지정하여 key - value 데이터 쌍을 저장한다.

저장, 삭제, 검색의 시간 복잡도는 모드 O(1)이다.

 

 

직접 주소화 방법

직접 주소화 방법은 키값을 인덱스의 번호로 저장하는 방식입니다.

예를 들면 1 - 김지수, 2 - 홍길동, 5 - 강감찬 이런식일때

1번 인덱스, 2번 인덱스, 5번 인덱스 이렇게 저장되므로 중간에 불필요한 저장공간을 사용하게 됩니다.

그렇기 때문에 key - value 데이터 쌍을 저장하기 위한 방법으로 직접 주소화 방법은 잘 맞지 않습니다.

 

hash table은 hash function h를 이용해서 (key, value)를 index : h(k)에 저장합니다.

이때 '키 k값을 갖는 원소 위치 h(k)에 hash 된다.' 또는 'h(k)는 키 k의 해시값이다.' 라고 표현합니다.

hash table을 구성하고 있는 key - value 데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 합니다.

 

 

1 - 김지수, 2 - 홍길동, 5 - 강감찬 가 있을때 키값인 1을 hash 함수를 통해 해쉬를 얻은 후 키 벨류로 저장하게 됩니다.

1	김지수
2	홍길동
5	강감찬

hash function

index	key	value
1	1	김지수
2	2	홍길동
3	5	강감찬

 

하지만 위와 같이 hash function 을 통해 해쉬를 구한 후 저장하면 해쉬가 같아지는 문제가 발생할 수 있습니다.

이것을 Collision이라고 합니다.

 

Collision

Collision이란 서로 다른 key의 해시값이 똑같아지는 것을 말합니다. 중복되는 key는 없지만 해시값이 중복될때 Collision이 발생했다고 합니다. 따라서 Collision이 최대한 적게 나도록 hash function을 잘 설계해야하고, 어쩔 수 없이 Collision이 발생하는 경우 seperate chining 또는 open addressing등의 방법을 사용하여 해결합니다.

 

Collision이 발생할경우 대표적으로 2가지로 해결할 수 있습니다.

첫번째 open addressing 방식은 Collision이 발생하면 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다.

빈 slot을 찾는 방법에는 크케 linear probing, Quadratic probing, Double Hasing으로 나눈다.

 

 

두번째, separete chining 방식은 linked list를 이용합니다. 만약에 Collision이 발생하면 linked list에 노드(slot)을 추가하여 데이터를 저장합니다.

 

 

Open addressing

미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다. 추가적인 메모리를 사용하지 않으므로 linked list 또는 tree자료 구조를 통해 추가로 메모리 할당을 하는 separate chaining 방식에 비해 메모리를 적게  사용합니다.

 

Linear probing(선형 조사법) & Quadratic probing(이차 조사법) : 선형 조사법은 충돌이 발생한 해시갑으로 부터 일정한 값만큼( +1, +2..) 건너 뛰어, 비어 있는 slot에 데이터를 저장합니다. 이차 조사법은 제곱수(+1 제곱) 로 건너 뛰어, 비어있는 slot을 찾습니다.

충돌이 려어번 발생하면 여러번 건너 뛰어 빈 slot을 찾습니다. 선형 조사법과 이차 조사법의 경우 충돌 횟수가 많아지면 특정영역에 데이터가 집중적으로 몰리는 클러스링현상이 발생하는 단점이 있습니다. 

 

Double Hasing(이중해시, 중복해시) : 이중 해싱은 linear probing이나 quadratic probing을 통ㅎ해 탐사할 때는 탐사이동폭이 같기 때문에 클러스터링 문제가 발생할 수 있습니다. 클러스터링문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식을 이중 해싱이라고합니다. 하나는 최초의 해시값을 얻을때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용합니다.

 

Separete chining

Separete chining 방식은 linked list(또는 tree)를 이용하여 collision을 해결합니다.

충돌이 발생하면 linked list에 노드(slot)를 추가하여 데이터를 저장한다.

삽입 : 서로 다른 두 key가 같은 해시값을 가지게 된다면 lined list에 node를 추가하여 데이터 쌍을 저장한다.

검색 : 기본적으로 0(1)의 시간 복잡도를 가지지만 최악의 경우 O(n)의 시간 복잡도를 가집니다.

삭제 : 삭제를 하기 위해선 검색을 먼저 해야하므로 검색의 시간 복잡도와 동일하다.