[Data Structures & Algorithms] Hashing

Hashing

• Why Hashing?
• 만약 어떤 Searching 알고리즘의 성능이 O(log2n) 인 경우, 이 정도면 매우 빠른 알고리즘임. O(n)인 알고리즘과 비교!
  • (예 : n이 10만개인 경우 약 17번, 100만 개인 경우 약 20번)
• 그러나 실시간 응용에서는 이 속도도 느릴 수 있음.
  • (예: ATM, Emergency Call, Real Time Processing)
• Hashing은 근본적으로 비교 연산을 안 함.

• Hashing은 Key의 개수 n과 무관하게 O(1)을 지향

• Applications of Hashing
• Data Dictionary
• Spelling Checker
• Symbol tables (Compiler)
• Encryption Forensics
• Database File Indexing

• We store the keys in a fixed memory called a hashing table.
  • We use a function f to decide the address (= location) of key X in the hash table.
  • By using f(X), each key X is mapped into some number in the range 0 to (HashTableSize – 1)

Hashing Table

• Ha-h table consists of b buckets;
• Each bucket consist of s slotsf⚫ Size of a hash table = s * b

Example: Hashing

Key의 예: 주민번호, 학번, 이름, 단어. . 등

Collision

• Hash function f might map several different keys into the same bucket.
• Two keys Ki and Kj are synonyms with a hash function f if f(Ki) = f(Kj) where Ki ≠ Kj
• A collision occurs when we hash two different keys into the same bucket.
• An overflow occurs when we hash some key into a full bucket.
• Collisions and overflows occur simultaneously if bucket size is 1.

Collision/Overflow

• Example:
  • Keys(K) : {acos, define, float, exp, char, atan, ceil, floor, clock, ctime}
  • Hash table : b = 26 buckets, s = 2 slots
  • Hash function f(K) : Get first letter of K and convert it into integer

• {acos, atan}, {char, ceil} {float, floor}: collision 발생
• {clock, ctime}: overflow 발생; 이 key들은 bucket 2에 삽입 불가능

• If no collision occurs; then hashing is the best (O(1)) among all searching algorithms.
• If collision occurs, then we must search within a bucket;
  • Usually, use sequential search in this case.
• If overflow occurs, then we must search another buckets.
• In worst case, we must find all the buckets (O(b)); Thus, O(n)
• In general, we can never avoid collisions and overflows.

# Loading Factor (부하율)

• Loading Factor(α) = n/(s*b) (즉, 총 key의 개수/ hash table size)
  • n : the number of keys
  • s : the number of slots
  • b : the number of buckets
  • For example: n = 1,000, b = 750, s = 2: Then, α = 1000/1500 = 67%
• If $\alpha$ is high, good space utilization! But lots of overhead for searching and insertions.
• Experiments show if $\alpha$ > 70%, collisions increase; So, we typically leave 20 ~ 30% empty space in each bucket.
  • For example: n = 1,000, s = 2, 20% extra space per bucket;
    • Then, b = (1,000/2)/0.8 = 6,250 buckets

Choice of Hash Functions

• The bad hash function maps many key values to the same bucket; In this case, many collisions occur and searching time increases seriously. Here are examples of bad hash functions;
• Phone numbers : bad with first 3 digits (better with last 3 digits).
• Date of births : bad with birth year (better with birthday)
• Person names : bad with the first letter (better with the middle)
• Account balances : Map the balance in range 1 to 100K into 10 buckets [1, 10K), [10K, 20K), . . . , [90K, 100K]
  • Seems good, since each bucket has the same number of differentbalance values
  • But not uniform, since key values with balances between 1 to 10K are more common than key values with balances between 90K and 100K.

• What is a good hash function? Minimize the number of collisions.
  • (1) Easy to compute
  • (2) Uniform (= Unbiased) hash function: (즉 균등하게 분배)
  • If we randomly choose a key X, the probability that f(X) = i is 1/ b for all buckets i.
  • Then, the random key X has an equal chance of hashing into any of the b buckets
• Hash table size(= number of buckets(b)) also needs to be considered;
  • b is large enough to minimize the number of collisions
  • b must not be so large that bucket occupancy is small and too much space is wasted

Uniform Hash Functions

Modular Division

• Divide key X by some number M and use the remainder as hash address for x.
• Hash function: f(X) = X mod M
• Range of bucket addresses is from 0 to M - 1 where M is the number of buckets.
• The choice of a divisor (= M) is very important.

• Example:
  • f(x) = x % M where M (number of buckets) = 307

• 만약 M이 짝수인 경우, 짝수 key들은 짝수 bucket 들로, 홀수 key들은 홀수 bucket 들로 매핑이 되므로 균등한 분배가 아님. 예: M = 14인 경우
  • 20 % 14 = 6, 30 % 14 = 2, 8 % 14 = 8 (모두 짝수)
  • 15 % 14 = 1, 3 % 14 = 3, 23 %14 = 9 (모두 홀수)
  • 예: 주민번호 끝자리: 남(홀수), 여(짝수) 군인들인 경우
• 만약 M이 $2^k$ (예: 2, 4, 8, 16, . . .) 인 형태인 경우에도 역시 안 좋음.
• 즉 M이 짝수보다는 홀수가 무난. 이 경우 M을 prime number(소수)로 선택하는 것이 더욱 무난함.
• Example: n = 4,000 keys, 20% extra space per bucket;
  • Then, b = 5,000 buckets needed;
  • Finally, choose a prime number b = 5,003

Mid-Square

• Compute function f by squaring(제곱) the key, and then obtain the bucket address by using an appropriate number of bits from the middle(중간) of the square
• The number of bits used to obtain the bucket address depends on the table size. If we use r bits, then 2r buckets are necessary
  • Example 1: 94522 = 89340304; address: 3403
  • Example 2:

Folding Method

• Partition the key into several parts and add them. (각 part는 Hash table의 주소 size에 맞도록…)
  • Fold shift
  • Fold boundary

Rotation Method

• Rotate the last character to the front of the key
  • Useful when keys are assigned serially;
    • Example: 주민번호, 학번, 부품번호 등
  • Can be used by combination with Fold Shift
  • Example: when we use fold shift (Select 2 digits each)
    • we get 26 (16 + 00 + 10), 36, 46, 56, 66 instead of 62, 62, …..

Digit Extraction

• Use selected digits from the key
  • Example: 학번에서 홀수 자리만 선택; 혹은 다음과 같이 1st, 3rd, 4th 자리만 선택

• 379452 > 394
• 121267 > 112
• 378845 > 388
• 160252 > 102
• 045128 > 051

Collision Resolution (충돌 해결책)

• Collision 해결의 필요성
  • 좋은 hash function을 사용하고 Hash table의 size가 넉넉해도 피해갈 수 없는 현상이고 언젠가는 항상 Collision이 발생함; (거의 무한대의 용량의 hash table을 갖지 않는 한 . . .)
  • 따라서 Collision을 인정하고, 이로 인해 발생하는 성능 저하의 문제점들 (최악에는 O(n))을 효율적으로 줄이기 위한 해결책들이 필요.
  • Collision 발생 시 해당 bucket에 들어갈 수 없으면 (즉, overflow가 발생하여 homeless!), 다른 empty bucket을 제공하여야 함.
  • “Homeless” 가 된 key들에게 empty bucket들을 어떤 방법으로 찾아서 제공을 하느냐가 주 관건

Open Addressing (개방 주소법)

• 충돌 발생시 자기 자리가 아닌 다른 bucket으로 들어갈 수 있도록 허용
• 즉, 다른 key가 해시되어 들어가야 할 bucket 들까지도 개방함.
  • (1) Linear Probe (선형 탐사)
  • (2) Quadratic Probe (제곱 탐사)
  • (3) Double Hashing (이중 해싱)

(2) Separate Chaining (별도 체인)

• 자기 자리인 bucket으로만 들어가게 함
• 각 bucket은 이 위치에 충돌한 모든 key들을 하나의 linked list로 연결함.

Linear Probe (선형 탐사)

• Empty bucket을 찾을 때 까지 다음과 같은 순서로 bucket들을 탐사
  • (f(X) + i) mod b (단, i = 0, 1, 2, . . . and I ≤ b – 1)
    • 단, X: 탐색 key, b: hash table의 bucket의 총 개수
• 한 칸 씩 차례대로 이동하여 empty bucket을 탐사;
  • 만약 발견하면, 바로 이 곳에 X를 insert.
• 만약 맨 끝까지 가서도 (즉, i 값이 (b – 1) 일때) empty bucket이 없으면, 다시 처음 위치 (즉, i 값을 0으로 reset) 부터 시작해서 빈 곳을 탐사.

Linear Probe : 예

-Resolve collision by adding 1 repeatedly to current address.

• f(x) = X % b where b = 307

• Keys(X) : {acos, define, atoi, char, exp, ceil, cos, float, atol, floor, ctime}
• Hash table : b = 26 buckets, s = 1 slot
• Hash function f(X) : Get first letter of X and convert it into integer

Linear Probe : 성능 분석

• 앞의 예제에서 평균 bucket 비교 회수는 ;
  • 총 비교 회수/총 key의 개수 = 41/11 = 3.72 (per key)
• Linear Probe에서 평균 예상 비교 회수(Expected Average Number of Comparisons)은 다음과 같음. 단, Uniform Hash 함수를 사용했을 때.
  • (2 – α)/(2 – 2α) (By D. Knuth, Art of Computer Programming)
    • 단, α (loading factor) = n/(s*b)
• α 값에 따른 평균 비교 회수 비교
  • α = 0 일 때; 1번 (Safe! 항상 빈 bucket이 있음)
  • α = 0.5 일 때; 1.5번
  • α = 0.9 일 때; 5.5번
  • α = 0.95 일 때; 10.5번
  • α = 1.0 일 때; 무한대 (infinite loop에 빠짐)
• Linear Probe는 α 값이 증가됨(50% 초과)에 따라 급격히 성능이 저하됨.

• 앞의 예제에서, α = 11/26 = 0.42 이므로, 평균 비교 회수를 (2 – α)/(2 – 2α) = 1.36 으로 기대할 수 있음. 이 예제에서는 좋지 않은 Biased 된 Hash 함수를 사용했으므로 기대치에 훨씬 미치지 못했음.
• 참조: Hashing의 평균 시간 성능은 Input Size인 key의 개수(n)에 대한 수식 (즉, Big Oh Notation)이 아닌, Loading Factor α로 계산된 평균 비교회수로 평가됨. 즉 n의 size가 몇 개든지 이와 상관없음.