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

➕ Hash Table은 java에서의 HashTable API가 아닌 Hash function을 통해 mapping된 value를 저장하는 Table을 뜻함

👇 이전 글 보기
https://2jinishappy.tistory.com/230

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

서로 다른 key에 대해 hash function으로 변환된 h(x)가 같을 경우, 같은 index에 값을 저장해야 하는 collision이 발생할 수 있다

collision handling 기법을 두 분류로 나누고, 어떠한 예시가 있는지 알아보겠다

🔹 Open Addressing : Key x를 가진 record가 반드시 hash table에서 h(x)에 위치하고 있을 필요는 없다

• Uniform probing, Linear probing, Quadratic probing

🔹Closed Addressing : Key x를 가진 record는 반드시 hash table에서 h(x)에 위치해야 한다

• Chaining

편의를 위해 앞으로는

• h : hash function
• n = hash table에 저장된 record 수
• N = hash table size

라고 하겠당

두 분류의 대표적인 예시인 Linear Probing과 Separate Chaining에 대해 알아본다

 

1️⃣ Separate Chaining

출처: https://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_1_LL.svg

• n > N인 경우 주로 사용(해시 테이블에 저장된 데이터의 개수가 배열 index 범위를 초과하는 경우)
• hash table을 N개의 linked list로 관리한다
• table의 i번째 index에는 linked list 형식으로 h(x) = i인 key x를 가진 모든 record를 저장
  • linked list 안에서의 순서는 상관없음

 

separate chaining에서의 연산은 다음과 같이 이루어진다

• Find(key) : Hash table의 h(key)번째 linked list의 head로부터 key값을 가진 record가 있는지 탐색하여, 있으면 해당 record를 return한다
  • key번째 linked list의 head로부터 해당 key를 가진 record가 나올 때 까지 linear searching을 통해 탐색
• Insert(key, record) : Hash table의 h(key)번째 linked list의 head로부터 key값을 가진 record가 있는지 탐색하여, 없으면 해당 linked list에 record를 추가한다
• Delete(key) : Hash table의 h(key)번째 linked list의 head로부터 key값을 가진 record가 있느지 탐색하여, 있으면 해당 linked list에서 record를 제거한다

 

Worst case: Hash table의 한 index에 모든 record들이 몰려 있을 때

➡ Find, Insert, Delete 연산 모두 O(n)시간이 소모된다

chaining 시 worst case n probe가 필요하다

 

Average case: Hash table에서 각 record가 얼마나 균등하게(uniformly) 분배되어 저장되어 있는 지의 여부로 갈린다

모든 record들이 uniformly distributed할 때: 어떤 key x에 대해 h(x) = i (0 ... N-1)일 확률이 x, i와 상관 없이 모두 1/N

 

hash table에서는 성능 분석 시 probe(table 상의 node 에 접근하는 총 횟수)를 이용

λ = n/N (hash table의 load factor - 탑재율)
table의 각 index에 포함된 record의 평균 개수는 load factor와 같다

• Successful search - Find나 Delete 시 linked list에 포함된 record를 찾을 때 까지의 총 probe 수 (평균 1+λ/2 probe)
• Unsuccessful search - Insert 시(혹은 Find/Delete에서 해당하는 record를 찾지 못할 시) linked list에 해당 record가 없다는 것을 알기까지의 총 probe 수 (평균 λ probe)

separate chaining은 java의 HashMap API의 구현에도 사용되지만, n<N인 경우 공간 낭비가 심하며 (hash table에 빈 공간이 많음에도 collision 발생에 의해 linked list의 node를 위한 추가 공간을 할당해야 함) 실제 구현 시 cache miss가 자주 발생한다

 

2️⃣ Linear Probing

출처:&nbsp;https://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_0_SP.svg

기존의 단일 hash function의 값 h(i)가 아니라, N개의 서로 다른 hash function 값 h(i,0), h(i,1), h(i,2) , ... , h(i,N-1)을 가정했을 때,
key값이 i인 record는 hash table의 h(i,0), h(i,1), h(i,2) , ... , h(i,N-1)번 째 index 중 한 곳에 저장하는 방식을 open addressing이라 한다

그 중에서도 h(i, k)에서 i가 고정된 값일 때

• uniform probing ➡ h(i,0), h(i,1), h(i,2) , ... , h(i,N-1)이 {0, 1, ... , N-1}의 uniformly random permutation
• linear probing ➡ k가 증가함에 따라 h(i, k)의 값이 linear하게 증가
• quadratic probing ➡ k가 증가함에 따라 h(i, k)의 값이 quadratic하게(k에 대한 2차식) 증가

이 중에서도 n<N인 경우 실제 구현에서 가장 빠른 방법 중 하나인 linear probing에 대해 알아본다

h(i, k) = (h(i) + k) mod N = ((i mod N) + k) mod N ➡ for k = 0, 1, ... , N-1
Fixed된 i에 대해 k가 증가함에 따라 h(i, k)의 값이 linear하게 증가

이 때, hash table의 각 entry는 3가지 status를 가진다

1. Empty: 해당 entry는 비어있다(어떤 record도 해당 entry에 저장된 적 없음)
2. Active: 해당 entry에는 record가 저장되어 있음
3. Deleted: 해당 entry에 record가 저장된 후 일정 시간 뒤 지워짐

linear probing에서의 연산은 다음과 같이 이루어진다

• Find(key) : Hash table의 h(key, 0)번째 entry부터 h(key, N-1)번째 entry까지 차례대로 탐색
  • 탐색 도중 중간에 empty상태인 entry를 만나면 종료(active나 deleted인 경우는 계속 진행 가능)
  • 탐색하는 hash table의 entry들 중 active 상태이면서 key를 가진 record가 있으면 해당 record를 반환
• Insert(key, record) : 해당 key를 가진 record가 현재 hash table 상에 없다고 가정
  • Hash table의 h(key, 0)번째 entry부터 h(key, N-1)번째 entry까지 차례대로 탐색하면서 처음으로 접근하는 empty나 deleted 상태인 entry에 해당 record 저장
  • 해당 entry는 active 상태로 바꿔줌
• Delete(key) : Hash table의 h(key, 0)번째 entry부터 h(key, N-1)번째 entry까지 차례대로 탐색하면서 탐색 도중 key값을 가진 record의 상태를 deleted로 바꿈(향후 insert시 덮어 쓰기 가능)
  • 중간에 empty상태인 entry를 만나면 탐색 종료(이 경우 삭제할 record가 hash table 상에 없다)

 

 

Worst case: 특정 i에 대해 h(i, 0), h(i, 1), ... , h(i, n)이 다 active 상태일 때

• h(i) = h(j)인 모든 key j에 대해 Find, Insert, Delete 모두 n probe가 필요
• 이와 같이 table의 연속적인 index들이 모두 non-empty 상태인 원인으로 연산들의 속도가 저하되는 현상을 clustering problem이라 한다
• Clustering problem을 해결하기 위해 load factor가 일정 이상(ex. 0.8)인 경우 rehashing 과정을 거친다
  • Hash table의 size를 두 배 늘려준다
  • Hash function을 새로운 Hash table size에 맞게 변경해준다
  • 변경된 hash function에 맞게 현재 active상태인 record들을 모두 새로 insert 한다

 

Average case: 각 record들이 uniformly distributed하고 N이 충분히 클 때

• Number of Successful Search(평균) = ½ (1+1/(1-λ)) probes
• Number of Unsuccessful Search(평균) = ½ (1+1/(1-λ)²) probes

가 소모된다