[자료구조] 3-1 Hash

1. 해시 테이블

해싱(Hashing)은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정이다. 해시 테이블은 무언가를 찾을 수 있도록 한 사물에서 다른 사물로 매핑해야하는 경우에 적합하다. 키를 활용하여 값에 직접 접근이 가능한 구조로,  O(1) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있다. Python 딕셔너리도 해시 테이블의 한 종류다. 

 

1-1 array와의 비교

array의 검색 시간복잡도는 O(n), 해시는 O(1)로서 차이를 보인다.  Hash의 key를 숫자로 바꾸어 index number로 저장하기 때문에 바로 찾을 수 있다. 하지만 array에서는 인덱스로 검색해도 모든 자료를 처음부터 순차적으로 보며 검색하기 때문에 느리다.

 

2. 해시 함수

해시함수는 키를 해시테이블 내의 버킷(=hashes=해시값)으로 매핑시킨다. 입력값의 형태는 다양하고, 출력값의 형태는 숫자이다. 해시함수를 어떻게 구현하는지에 따라 해시의 성능이 결정된다. 충돌이 적은 해시함수를 만드는 것이 해시테이블의 가장 중요한 목적이다.

해시 함수

2-1 좋은 해시함수란?

1) 키와 값의 계산과정이 쉬워야 한다.
2) 충돌을 피할 수 있어야한다.

 

3. 해시 충돌

해시 충돌을 막 접했을 때 가진 의문은 이것이다. '해시 충돌은 왜 날까? 키를 각각의 숫자에 매핑시키는 단순한 과정인데 왜 오류가 날까?'

해시 충돌이 발생하는 이유는 해시 함수의 특성과 키-값 쌍을 저장할 수 있는 공간의 한계 때문이다.

해시함수로 매핑할 수 있는 숫자에는 한계가 있다. 해시테이블에 많은 숫자를 배당하면 메모리를 그만큼 차지하기 때문이다. 

예를 들어, 해시 테이블의 크기가 100이고 해시 함수가 각 키를 0부터 99 사이의 숫자로 매핑한다고 가정해보자. 이런 경우에도 100개를 넘는 키-값 쌍을 저장하려고 하면 반드시 적어도 두 개의 키가 동일한 해시 값을 가지게 되며 이는 해시 충돌로 이어진다.

 

 

4. 해시 충돌 방지법 (체이닝, 오픈 어드레싱)

체이닝은 각 인덱스에 연결 리스트를 저장하여 충돌을 관리하는 방법이며, 오픈 주소법은 충돌이 발생하면 다른 인덱스에 항목을 저장하는 방법이다. 이렇게 해시 충돌을 적절히 관리함으로써 해시 테이블은 빠른 키-값 쌍의 검색을 계속해서 제공할 수 있다.

4-1 체이닝

* 과정
1) 키의 해시값을 계산한다.
2) 해시값을 이용해 리스트의 인덱스를 구한다.
3) 같은 해시값이 있다면(충돌한다면) 리스트로 연결한다.

체이닝

체이닝 방법의 핵심 아이디어는 각 버킷이 단일 값을 저장하는 대신, 값을 저장하는 연결 리스트를 가지도록 하는 것. 그러면 한 버킷에 여러 개의 키-값 쌍이 매핑될 때, 각각의 쌍을 연결 리스트의 다음 노드로 추가할 수 있습니다.

예를 들어 4라는 버킷에 cake, cream 이라는 두개의 키가 연결리스트로 매핑되었다. 우리는 cake의 value를 찾아야한다면 일단 해쉬함수에 넣어 4라는 버킷을 찾은 다음 선형검색을 통해 cake의 value를 찾는다. 

체이닝의 장점은 구현이 비교적 단순하고 충돌 해결 방법이 직관적이라는 것이다. 하지만 해시 테이블의 각 슬롯에 많은 수의 항목이 모이게 되면, 연결 리스트를 순회하는 데 필요한 시간이 증가하므로 성능에 영향을 미칠 수 있다. 이러한 문제는 해시 함수를 개선하거나 해시 테이블의 크기를 증가시키는 등의 방법으로 해결할 수 있다.

4-2 오픈 어드레싱

해시 충돌이 일어나는 경우 빈공간을 찾아 그곳에 데이터를 입력한다. 파이썬의 경우, 내부적으로 오픈어드레싱 방식을 활용한다.

 

주요 장점은 메모리 공간의 효율적인 사용입니다. 오픈 주소법은 추가적인 데이터 구조(예: 체이닝에서 사용되는 연결 리스트) 없이 해시 테이블의 빈 슬롯만을 사용하기 때문에, 메모리 공간을 절약할 수 있다. 그러나 해시 테이블이 거의 가득 차 있을 때는 성능이 저하될 수 있으며 이런 경우 해시 테이블의 크기를 조정해야 하기도.

오픈 어드레싱은 여러 가지 변형을 가지고 있지만, 가장 널리 사용되는 세 가지 방법은 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 그리고 이중 해싱(Double Hashing)이다.

- 선형 탐사(Linear Probing): 가장 간단한 오픈 어드레싱 방법. 충돌이 발생하면, 테이블 내에서 다음 위치를 확인하여 빈 슬롯을 찾을 때까지 계속 이동한다. 이 방법은 구현이 간단하지만, 해시 테이블의 일부 영역에 데이터가 집중되는 부작용이 생길 수도 있다. 

- 제곱 탐사(Quadratic Probing): 제곱 탐사는 선형 탐사의 문제를 해결하기 위한 방법. 충돌이 발생하면, 제곱수(즉, 1, 4, 9, 16, ...)만큼 이동하여 빈 슬롯을 찾는다.

- 이중 해싱(Double Hashing):  해시 함수를 두 번 적용하여 해시 충돌을 해결하는 해시 기법. 선형 탐사와 제곱 탐사의 데이터 쏠림 문제를 효과적으로 해결할 수 있다.