[자료구조] 해시 함수(Hash Function) / 해시 테이블(Hash Table)

해시 함수(Hash Function)란 ?

데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.

이 때, 매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시값, 매핑하는 과정을 해싱이라고 합니다.

 

해시 함수는 해시값의 개수보다 많은 키값을 해시값으로 변환하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌이 발생하게 됩니다.

이러한 해시 충돌 발생 가능성이 있음에도 불구하고 해시 테이블을 사용하는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위함입니다.

 

해시 함수는 항상 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기와 상관없이 데이터에 빠르게 접근할 수 있으며 색인은 상수 시간으로 작동하기 때문에 매우 효율적입니다. 

즉, 해시는 데이터 [삽입 / 삭제 / 탐색]시 계산복잡성을 O(1)을 지향합니다.

 

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

해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인 혹은 주소 삼아 데이터의 값을 키와 함께 저장하는 자료구조를 뜻합니다.

이 때, 데이터가 저장되는 곳을 버킷 혹은 슬롯이라고 합니다.

해시 테이블의 기본 연산은 [삽입 / 삭제 / 탐색]입니다. 

 

해시 테이블 (Hash Table)

 

이 때, 각 버킷에는 데이터가 다음과 같이 저장됩니다.

 

index (Hash Value)	Data
01	(Lisa Smith, 521-8976)
02	(John Smith, 521-1234)
...	...

Direct-address table

키의 전체 개수와 동일한 크기의 버킷을 가진 해시 테이블을 Direct-address table이라고 합니다.

장점은 키 개수와 해시테이블 크기가 동일하므로 해시 충돌 문제가 많이 발생하지 않는다는 것입니다. 

하지만 전체 키가 실제 사용하는 키보다 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 만들어야 하기 때문에 메모리 효율성이 떨어집니다.

보통 Direct-address table보다는 "해시 테이블 크기(m)가 실제 사용하는 키 개수(n)보다 적은 해시 테이블"을 운용합니다.

이 때, n/m을 load factor(α)라고 하며 이는 한 버킷에 평균 몇 개의 키가 매핑되는 가를 나타내는 지표입니다.

Direct-address table의 load factor은 1 이하이며 1보다 큰 경우 해시충돌 문제가 발생합니다.

해시 충돌 해결하기 위한 기법

1. chaining

한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시 테이블에 담는 방식입니다.

해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현합니다.

유연하다는 장점이 있으나 메모리 문제를 야기할 수 있습니다.

 

계산 복잡성 (n개의 데이터)

• 삽입 : O(n)
• 탐색 : O(n) 
• 삭제 : O(n)

2. open addressing

chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시 테이블입니다.

해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용합니다.

해시값에 해당하는 버킷에 이미 데이터가 존재할 경우, 다음 버킷에 저장하는 방식입니다.

메모리 문제는 발생하지 않지만 해시충돌이 발생할 수 있습니다.

3. probing

앞선 open addressing에서 봤듯이 특정 해시값에 키가 몰리게 되면 효율성이 떨어집니다. 

이는 probing 방식으로 해결할 수 있고, 이는 [삽입 / 삭제 / 탐색]을 수행하기 위해 해시 테이블 내 새로운 주소(해시값)을 찾는 과정입니다.

선형 탐사(Linear probing)

 

최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어있다면 해당 해시값에서 고정 폭을 옮겨 다음 해시값에 해당하는 버킷에 [삽입 / 삭제 / 탐색] 합니다.

하지만 이 방식은 특정 해시값 주변 버킷이 모두 채워진 경우(primary clustring)에 취약합니다.

제곱 탐사(Quadratic probing)

 

고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어납니다.

충돌이 일어나면 1^2칸을 옮기고, 또 충돌이 일어나면 2^2칸을 옮기고, 다음에는 3^2칸을 옮기는 방식입니다.

이 방식은 여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 경우(secondary clustring) 취약합니다.

초기 해시값이 같으면 다음 탐사 위치 또한 동일하므로 효율성이 떨어집니다.

4. 이중 해싱 (double hashing)

탐사할 해시값의 규칙성을 없애 clustering을 방지하는 기법입니다.

2개의 해시 함수를 준비해 하나는 최초의 해시값을 얻을 때, 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용합니다.

이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary와 secondary clustering을 모두 완화할 수 있습니다.

해시 함수로 해시충돌 해결하기 위한 기법

1. division method

숫자로 된 키를 해시 테이블 크기 m으로 나눈 나머지를 해시값으로 반환합니다.

해시 함수 특성상 해시 테이블 크기가 정해진다는 단점이 있습니다.

2. multiplication method

숫자로 된 키가 k이고 A는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의됩니다.

ℎ(𝑘)=(𝑘𝐴 𝑚𝑜𝑑 1) × 𝑚

3. universal hashing

다수의 해시 함수를 만들고, 이 해시 함수의 집합 H에서 무작위로 해시 함수를 선택해 해시값을 만드는 기법입니다.

H에서 무작위로 뽑은 해시 함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 1 / m으로 만드는 것이 목적입니다.

 

---

참고

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/