빠른 데이터 검색을 위한 Hashing과 Hash Table

select * from ~ where key="name"

우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다

데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 것이 효과적인지 고민하는 과정에서 해싱의 원리를 찾을 수 있다.

 

특정 key가 주어졌을 때, 해당 key 값을 가진 record를 찾기 위한 방법으로는

1️⃣ Key를 index로 가진 array로 table 구현

2️⃣ BST 이용

1번은 조회하는 데 O(1)이 소모되는 대신 |max(key)|만큼의 메모리를 요구하기 때문에 실제로 사용하기에는 어렵다.

2번 또한 1번에 비해서는 get, insert의 평균적인 시간이 짧긴 하지만 O(log n)도 수천, 수만개의 record를 반복해서 get insert하기에는 무리가 있다.

 

해싱은 이를 위해 Array를 사용하되 각 key를 integer로 mapping 시켜준 뒤, mapping된 value를 array의 index로 이용하는 방법을 통해 record를 조회한다.

만약 Mapping function을 알고 해당 연산을 O(1)에 수행할 수 있으면 원하는 record를 찾기 위해 O(1) 시간 밖에 소모되지 않는다.

Hash Function: 특정 key 값을 0과 N-1 사이의 integer로 mapping 시키는 함수 
ex) modular hash function, multiplicative hash function 등 

Hash Table: 어떤 key 값 x에 대한 hash function을 h(x)라 할 때, index h(x)에 x의 record를 저장한 size N의 table

Abstract Data Type으로 구현된 Hash Table에는 Find(key), Insert(key, record), Delete(key)연산이 존재한다

 

Modular Hash Function: 어떤 integer key x에 대해 hash function h(x) = x mod N ( x%N )으로 정의한다(이 때 N은 보통 prime number)

-> 모든 key들은 0~N-1의 integer로 mapping되며 hash table을 size N인 array로 관리 가능하다.

Integer key가 아닌 경우에는 hash function이 두 번의 mapping 과정을 거친다

h1: keys -> Integers
h2: Integers -> [0, N-1]

hash function h(x) = h2(h1(key))    (x is rational number)

h1(x) = (ax+b) mod p (p is prime number)
h2(y) = y mod p (if p >> N, N can be any number)

∴ h(x) = ((ax+b) mod p) mod N

 

하지만 hash function으로 계산한 key값을 항상 온전히 사용할 수 있는 것은 아니다.

예를 들면 hash function h(x) = x mod 100이고, 찾으려는 key값이 58, 158일 경우 h(58) = h(158)인 상황이 발생한다. 이러한 경우에 x=58일 때 값을 저장하고, x=158일 때 값을 다시 저장하면 이전에 저장했던 값이 사라지는 경우가 발생할 수 있다.

이렇게 hash function으로 얻어낸 key값이 중복되는 상황을 Collision이라고 한다

 

물론 좋은 Hash function이란 Collision이 최대한 적게 일어나는 function을 말한다

hash table에 저장되어 있는 각 recode의 key 값 x에 대해 h(x)가 모두 다르다면 collision은 일어나지 않으며, 이것을 perfect hash function이라고 하지만

실제 구현 상에서 perfect hash function은 거의 존재하지 않으므로, collision을 줄일 수 있는 hash function을 설계하는 것이 포인트이다.

따라서 실제 case에서는 좋은 hash function을 각 hash table의 index에 해당하는 record들이 얼마나 균일하게 분포되어 있는지(uniformly distributed), collision이 발생하면 어떻게 대처하는지로 판단한다

 

다음 포스팅에서는 collision handling 기법들을 알아보도록 한다 . . . 

https://2jinishappy.tistory.com/231

Hash Table에서의 Collision Handling - Linear Probing, Separate Chaining

 

🥱