해시 테이블과 해시 충돌 및 해결방법

해시 테이블(Hash Table)이란?

해시 테이블은 key-value 형태로 데이터를 저장하는 자료구조이다. key를 특정 해시 함수를 통해 해싱한 후 나온 결과를 배열의 인덱스로 사용하여 value를 찾는 방식으로 동작한다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷 또는 슬롯)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블의 평균 시간복잡도는 O(1)이다.

 

 

해시 함수(Hash Function)이란?

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 해시 테이블에 사용되는 대표적인 해시 함수로는 4가지가 있다.

1. Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다. (주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding : 각 key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method : 숫자로 된 key 값 k와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k) = (kAmod1) x m
4. Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

해시 충돌

서로 다른 두 개의 key가 동일한 hash 값을 갖는 경우 "해시 충돌" 이라고 한다. 해시 충돌을 해결하는 방법은 Chaining과 Open Addressing 방법이 있다.

 

1. 체이닝(Chaining) 기법

버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않도록 하여 충돌을 완화하는 방법이다.

  

중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장한다. 이 방법은 연결 리스트로 인해 최악의 경우 수행 시간이 O(n)이 된다. 해시를 사용하는 이유는 O(1)이라는 장점으로 사용하는 것인데 O(n)이 된다면 문제가 된다. 이런 문제로 트리로 구성하여 더 시간 복잡도를 줄일 수도 있다.

 

2. 오픈 어드레싱(Open Addressing) 기법

충돌 발생 시 해시함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다.

오픈 어드레싱은 충돌을 피하기 위해 key를 해시 테이블에 직접 저장한다. 오픈 어드레싱의 장점은 포인터를 사용하지 않아도 되어 구현이 간편하며, 검색도 미세하게 빨라진다. 오픈 어드레싱은 총 3가지 종류가 있다.

 

2-1. 선형 탐사법(Linear probing)

선형 탐사법은 충돌이 발생할 경우 빈 slot이 나올 때까지 탐색 후, 빈 slot이 나오면 위치가 결정된다. 선형 탐사법은 아래와 같은 해시 함수가 사용된다. 여기서 k는 키, i는 충돌 횟수, h()는 해시 함수, m은 해시 테이블 크기를 의미한다.

- 장단점 : 선형 프로빙의 장점은 구현은 매우 쉬우나 1차 군집 현상(primary clustering) 문제가 있다. primary clustering는 한 번 충돌이 나면 집중적으로 충돌이 발생하는 것을 의미한다. 이로 인하여 평균 검색 시간이 증가한다. 따라서, 해당 접근 방법은 해시 자료 구조 전체에 해시 충돌이 균등하게 발생할 때 유용하다.

 

2-2. 제곱 탐사법(Quadratic probing)

제곱 탐사법은 선형 탐사법처럼 한 칸씩 찾는 것이 아닌 제곱으로 늘리면서 빈 버킷을 찾는다. 제곱 탐사법은 아래와 같은 해시 함수를 사용한다. i에 대한 2차 함수 꼴로 slot을 이동하면서 빈 슬롯을 찾는다. 여기서 h는 보조 해시 함수, c1와 c2는 0이 아닌 상수이다.

- 장단점 : 제곱 탐사법은 보폭이 점점 늘어나기 때문에 선형 탐사법처럼 특정 역역에 값이 밀집되어 저장되어도 해당 영역을 빠르게 벗어날 수 있다. 선형 탐사법에 비해 충돌이 적지만 secondary clustering이 발생한다. secondary clustering은 처음 충돌한 위치가 같다면 다음 충돌할 위치도 반복적으로 계속 충돌이 나게 된다는 의미이다. 즉, 여러 값이 해시 함수로 같은 값을 갖게 될 경우 모두 같은 순서로 탐사할 수 밖에 없어 비효율적인 상황이 발생할 수 있다.

 

2-3. 이중 해시(Doubld hasing)

이중 해싱은 해시 충돌이 발생하는 경우, 보조 해시 함수를 사용하는 방법이다. 이중 해시는 다음과 같은 형태의 해시 함수를 사용한다. 충돌이 없을 때는 h1으로 위치를 탐색하고, 충돌이 있으면 h2 mod m 만큼 이동하면서 탐색한다.

- 장단점 : 이중 해싱 방법은 해시 충돌 가능성이 가장 작지만, 추가적인 보조 해시 함수에서 연산이 발생하기 때문에 다른 방식에 비해 많은 연산량이 요구된다.

 

[참고]

https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?

https://ryu-e.tistory.com/87

해시(Hash)와 해시 충돌 해결 방법