Hash의 실전적 구현

생각보다 해시 자료구조는 다양하게 활용될 수 있다. O(1)이라는 표현이 매우 자극적이기도 하지만, 문제는 해시테이블에 저장하기까지가 시간을 상당히 잡아먹는다는 것이다. 당연하게도 트레이드오프가 존재한다.

우선 당연히 충돌은 발생할 것이므로 체이닝이 가능한 해시를 콤팩트하게 구현하는 방법에 대해 먼저 정리해보자.

#include <stdio.h>  
  
struct Node {  
	int index;  
	Node* next;  
}  
  
Node buf[100000];  
int bufCount;  
  
Node* chain[100000];  
  
Node* myAlloc(int index, Node* next) {  
	buf[bufCount].index = index;  
	buf[bufCount].next = next;  
	return &buf[bufCount++];  
}  
  
void addNode(int from, int index) {  
	chain[from] = myAlloc(index, chain[from]);  
}  
  
int hash(char* key) {  
	int sum = 0;  
	for (int i = 0; i < 3; i++) {  
		sum += (key[i] - ‘A’ + 1);  
	}  
	return sum;  
}  
  
void init(char* inputString) {  
	int hashCode = hash(inputString);  
  
	for (int x = 0; input[x + 2] != 0; x++) {  
		addNode(hashCode % 5, x);  
  
		if (input[x + 3] == 0) break;  
  
		hashCode += (input[x + 3] - ‘A’ + 1);  
		hashCode -= (input[x] - ‘A’ + 1);  
	}  
}  

입력받은 문자열의 sub string을 해시 테이블로 구성하는 예제이다.

체이닝은 구현하는 모습은 이전 글에서 소개했던 링크드리스트 구현방식과 동일하다. 해시 함수에서 호너의 메소드를 사용한 모습도 주목해보고, init 함수에서 최초 해시 테이블을 구성할때 슬라이딩 윈도우를 활용한 모습도 살펴보도록 하자.