[Data Structure] Hash Table (해시 테이블)

Hash Table

📢 특정 규칙을 가지고 데이터를 저장하는 방법

---

먼저 해시 테이블에는 Bucket Array와 Hash Function이라는 2가지 구성요소가 존재해요.

Bucket Array

• 아래 그림에서 배열의 각 칸을 Bucket이라고 해요.
• Bucket들이 모여있는 배열이어서 Bucket Array라고 부르는 거예요.
• 각 Bucket 안에는 (key, value) pair의 set이 들어있어요.
• 각 Bucket 내부는 중복된 value 값을 가질 수 없어요.
• key는 [0, N-1] 사이의 값을 가져요.

Hash Function

• 각각의 key를 [0, N-1] 사이의 값으로 바꿔주는 함수를 뜻해요.
• Hash Function을 h(x)라고 할 때 h(k)의 값을 Bucket Array의 Index값으로 사용해요.
• 2개 이상의 같은 Hash Value가 생기면 Collision이 일어나요.
• Collision을 최소화 하는 것이 좋은 Hash Function이에요.
• Hash Function은 2가지 과정을 거치는데
  1. key를 Hash Code로 바꾸고
  2. Hash Code를 [0, N-1]의 범위 안으로 바꾸는 과정을 가집니다.

---

⏰ 시간 복잡도

• 최악의 경우는 하나의 Bucket에 모든 데이터가 들어가 있을 수 있고 이런 경우에O(N)의 시간 복잡도를 가져요.
• 일반적으로는 O(1)의 시간 복잡도를 가져요.

---

Hash Codes

Integer Cast

• key값을 bit로 바꾸어 Integer 형에 맞게끔 재해석 하는 방법이에요.
• Integer 보다 작거나 같은 길이의 bit수를 가지는 자료형에 적합해요.

Component Sum

• key의 bit값을 정해진 부분만 더하는 방법이에요.
• Integer 보다 큰 길이의 bit수를 가지는 자료형에 적합해요.

Polynomial Hash Codes

• 순서가 중요한 경우에는 적합하지 않아요.
  (lotte, lotet, ltteo...를 다 다르게 하고 싶으면 적합하지 않아요.)
• 각 글자를 Xi라고 했을 때 아래의 수식을 ....
• a는 임의로 정하면 돼요. (주로 33, 37, 39, 41)

Cyclic Shift Hash Codes

• 각 key 값을 특정 bit만큼 shift 연산을 하여 더하는 방법이에요.

int hashCode(const char* p, int len) {	// hash a character array
	unsigned int h = 0;
    for (int i = 0; i < len; i++) {	
    	h = (h << 5) || (h >> 27);		// 5-bit cyclic shift
    	h += (unsigned int)p[i];		// add in next character
    }
    return hashCode(int(h));			// Assume that we have a hashCode function for an integer
}

Hashing Floating-Point Quantites

• Integer 형으로 변환은 Float 값을 손상시킬 수 있어서 이를 방지하고자 사용하는 방법이에요.

int hashCode(const float& x) {	// hash a float
	int len = sizeof(x);
    const char* p = reinterpret_cast<const char*>(&x);
    return hashCode(p, len);
}

Compression Functions

Division Method

• 아래 수식을 사용하는 방법이에요.

• N이 소수라면 Hash 값의 분포가 더 커지도록 도와줘요.
• 좋은 Hash Function은 충돌 확률이 1/N인 것을 보장해요.

MAD (Multiply, Add, Divide) Method

• 아래 수식을 사용하는 방법이에요.

• N은 소수이고, a와 b는 음이 아닌 정수예요. (a mod N != 0)

Collision-Handling Schemes

Separate Chaining

• List와 같은 또 다른 자료구조를 필요로 해요.

Load Factor

• 람다 = n/N 라고 표시를 해요.
• Load Factor가 < 0.5 라면 Open Addressing을 사용하고
  Load Factor가 < 0.9 라면 Separate Chaining을 사용해요.

Open Addressing

• 각 데이터를 바로 Bucket에 저장해요.
• 최대 하나의 Bucket에 하나의 데이터만 존재해요.

Linear Probing

• Bucket A[i] (i = h(k)이고) 가 존재한다면 A[(i+1) mod N]에 저장을 시도해요.
• 만약 A[(i+1) mod N]이 존재한다면 A[(i+2) mod N]에 저장을 시도해요.
• 이 작업을 빈 Bucket을 찾을 때까지 시도해요.

Quadratic Probing

• Bucket A[i] (i = h(k)) 가 이미 존재한다면, A[(i+f(j)) mod N] (f(j) = j^2) 에 저장을 시도해요.
• N이 소수가 아니라면 빈 Bucket을 못 찾을 수도 있어요.

Double Hashing

• 또 다른 Hash Function (h'(x)) 을 준비해요.
• A[i]가 안되면 A[(i+f(j)) mod N] (f(j) = jh'(k))를 시도해요.

Rehashing

• Load Factor가 임계값을 넘계되면 Table을 재설정해요.
• 재설정 후 원래 값들을 제자리에 넣어줍니다.

---

📋 예제

백준 15829 - Hashing

백준 15829 - 해답