[자료구조] 해싱(hashing)

---

Static Hashing

Definition

• 배열 안에 key를 저장하고 탐색하는 기법 - hash table
• key를 배열의 index로 mapping
  • 이를 bucket이라고 함
• 평균 성능: O(1)
  • 탐색, 삽입, 삭제

index	bucket
0	Korea
1	Japan
2	Qatar
3	Vietnam
4	China
5	Taiwan
6	Singapore
7	France

• Insert Thailand & Spain

index	bucket
0	Korea
1	Japan
2	Qatar
3	Vietnam
4	China
5	Taiwan	Thailand
6	Singapore	Spain
7	France

-> index 5, 6에서 collision 발생

• Insert SriLanka

index	bucket
0	Korea
1	Japan
2	Qatar
3	Vietnam
4	China
5	Taiwan	Thailand
6	Singapore	Spain	<- SriLanka
7	France

-> index 6에서 overflow 발생

Hash Table

• n개의 index
• index마다 k개의 bucket
  • 총 n * k 개의 key가 저장됨
• collision : 2개 이상의 key가 같은 index에 mapping 되는 것
• overflow: (k+1)개 이상의 key가 같은 index에 mapping 되는 것

Ultimate Objectives of Hashing

1. 최소한의 collision
2. 최소한의 overflow
3. 최소한의 hash table 크기

Two Key Elements in Hashing

1. Hash function 선정
2. Collision 해결법

Hash function

• E.g., "EACH" = (ASCII) 69 65 67 72
• E.g., "EACH" = (알파벳 순서) 5 1 3 8

-> 사용가능한 fucntion은 많다

4 Commonly used Hash funtions

1. Modulo Function

• H(key) = key % hash_table_size
• E.g., 375 % 101 = 72
• 모든 key가 hash table에 들어감
• hash_table_size를 소수로 정하는 것이 가장 효율적임

2. Digit Folding("hashing")

• key의 각 요소들의 조합을 더하는 방법
• E.g., key = 9010302051218, hash_table_size = 117
  • (9+0+1+0+3+0+2+0+5+1+2+1+8) % 117

3. Digit Analysis

• key의 일부 요소를 선택
• E.g., 4, 8, 10번째 열을 선택

Before	After
012-452-0236	426
012-153-0530	150
012-342-0935	395
012-752-1032	702
012-852-0470	840

4. Mid-Square Function

• key를 제곱하고, 결과를 이진수로 변환한 뒤 중간에서 k개의 bit를 선택
• E.g., key = 11 -> 제곱은 121 -> 111001₍₂₎
  • 1100을 선택
  • 선택되는 bit의 개수는 hash table size에 따름
  • 만약 k개의 bit가 선택되었으면, 값의 범위는 2^k

Collision Resolution

• 일반적으로, hash function은 collision을 방지할 수 없음
• 충돌하는 key는 어떻게든 저장되어야함
• 2가지 접근법
  • closed addressing(open hashing)
    • key는 linked list로 저장됨
  • open addressing(closed hashing)
    • 모든 key들은 linked list의 사용없이 hash table에 저장

Closed Addressing

• 빠른 접근이 가능하고 overflow가 없음
• 공간의 낭비가 심할 수 있음
• 현실적이지 않음

Open Addressing

• Linear Probing
  • 만약 collistion이 발생하면, 순차적으로 빈 bucket을 탐색하고 그 곳에 저장한다
• Quadratic Probing
  • 빈 bucket을 계산된 index로부터 k²(k=1, 2, 3, ...) 위치에서 찾는다
• Double Hashing
  • 두 개의 구분된 hash function을 사용
    • 한 가지는 index를 찾는데 사용
    • 다른 한 가지는 collistion이 발생한 key를 삽입할 index interval를 찾는데 사용
    • E.g., h1: key % 13, h2: 1 + key % 11
  • 두 번째 hash function은 반드시 0으로 계산되지 않아야 하고 첫번째 hash function과 같은 값이 나오면 안된다.

Open Addressing: Measures

• Loading density
  • α = # of buckets occupied / total # of buckets in the hash table
• AVG. # of key comparisons = (2-α) / (2-2α)
• Examples
  • for α = 0.2: (2-0.2) / (2-2*0.2) = 1.125
  • for α = 0.99: (2-0.99) / (2-2*0.99) = 50.5

Bloom Filter

Definition

• An application of hashing
• 큰 데이터셋에 새로운 데이터가 이미 존재하는지 여부를 작은 메모리를 사용하면서 빠르게 결정할 수 있음
  • keyword: small memory, doesn't not already exist, large dataset

2 Elements of the Bloom Filter

1. 0으로 초기화 되어있는 N개 bit의 배열
2. k개 hash function의 collection
   • 각각의 hash function은 bit array index에 key를 mapping 해야함

	prediction
GT		P	N
	P	TP	FN
	N	FP	TN

precision = TP / TP + FP
recall = TP / TP + FN

Algorithm

• Inserting new input data
  • input data에 k개의 hash function을 적용
  • hashing된 array의 값을 1로 설정
  • dataset에 이미 key가 있는지 확인
• Checking if the key is already in the dataset
  • input data에 k개의 hash function을 적용
  • 현재 bit array의 k개의 위치 확인
  • 적어도 하나가 0인 경우, key는 dataset에 없음
  • 아니라면, input data는 dataset에 있을 수도 있음
• Bloom Filter does not allow deletion

How to reduce the False Positives

• Two Ways
  • bit array를 더 크게 만든다
  • 다른 hash function을 더 사용한다