소소한팁 - 긴 문자열을 해시 테이블로 관리

문자열을 숫자로 변경하기이용하여 3글자 이상 15글자 이하(‘\0’ 포함)의 문자열을 해시로 관리할 수 있습니다. 앞의 3글자를 숫자로 변경해서 해시값으로 사용하고 나머지 11글자를 숫자로 변경해서 관리하면 가능합니다. 문자가 모두 소문자(a-z)로 이루어진 경우에만 가능합니다.

앞 3글자를 숫자로 변경했을 때 11111 11111 11111까지 표현 가능한 경우의 수는 총 32767 이기 때문에 해시테이블의 크기를 32768로 잡고 같은 해시가 충돌나는 경우 Linked List 로 관리하면 됩니다.

문자열 복사 함수

void mstrcpy(char dst[], const char src[]) {
	int c = 0;
	while ((dst[c] = src[c]) != 0) ++c;
}

해시 함수 및 숫자로 변환 함수

typedef unsigned long long LL;

// 해시 인덱스 계산
int str_to_hash(const char* str) {
	int ret = 0;
	for (int i = 0; i < 3; i++) {
		ret <<= 5;
		ret += ((str[i] - 'a') + 1);
	}
	return ret;
}

// 나머지 글자 숫자로 변경
LL str_to_id(const char* str) {
	LL ret = 0;
	for (int i = 3; str[i] != 0; i++) {
		ret <<= 5;
		ret += ((str[i] - 'a') + 1);
	}
	return ret;
}

해시 노드

// 노드 정의
struct Node {
	char str[15];
	LL id;
	int hash;
	Node* prev;
	Node* next;
};

// 노드 배열 준비
int node_arr_idx = 0;
Node node_arr[MAX_NODE];

// 노드 생성
Node* get_node(const char* str) {
	Node* node = &node_arr[node_arr_idx++];
	mstrcpy(node->str, str);
	return node;
}

// 해시 배열 준비
Node* node_hash[MAX_HASH];

해시 테이블 함수

// 해시에 추가
void add_to_hash(Node* node) {
	node->next = node_hash[node->hash];
	if (node->next != 0) {
		node->next->prev = node;
	}

	node_hash[node->hash] = node;
	node->prev = 0;
}

// 해시에서 제거
void del_to_hash(Node* node) {
	if (node->next != 0) {
		node->next->prev = node->prev;
	}
	if (node->prev != 0) {
		node->prev->next = node->next;
	}
	if (node->prev == 0) {
		node_hash[node->hash] = node->next;
	}
}

// 해시에서 검색
Node* find_node(const char* str) {
	int hash = str_to_hash(str);
	LL id = str_to_id(str);

	Node* cur = node_hash[hash];
	for (; cur != 0; cur = cur->next) {
		if (cur->id == id) {
			return cur;
		}
	}
	return 0;
}

// 해시 정보 출력
void print_hash_info(int hash) {
	Node* node = node_hash[hash];
	Node* cur = node_hash[hash];
	for (; cur != 0; cur = cur->next) {
		printf("%s ->", cur->str);
	}
	printf("Empty\n");
}

테스트

int main() {

	// 노드 생성
	Node* n1 = get_node("hello");
	n1->id = str_to_id(n1->str);
	n1->hash = str_to_hash(n1->str);

	// 노드 추가
	add_to_hash(n1);
	print_hash_info(n1->hash);

	// 노드 생성
	Node* n2 = get_node("helkkk");
	n2->id = str_to_id(n2->str);
	n2->hash = str_to_hash(n2->str);

	// 노드 추가
	add_to_hash(n2);
	print_hash_info(n2->hash);

	// 노드 검색
	Node* n3 = find_node("helkkk");
	
	// 노드 삭제
	del_to_hash(n3);
	print_hash_info(n3->hash);

	// 노드 검색
	Node* n4 = find_node("hello");
	del_to_hash(n4);

	// 노드 삭제
	del_to_hash(n3);
	print_hash_info(n3->hash);

	return 0;
}

출력

hello ->Empty
helkkk ->hello ->Empty
helkkk ->Empty
Empty