[자료구조] 해시

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

해시(Hash)

배열의 데이터 삭제 방법

해시법

해시법은 기존 배열을 이용한 데이터 관리를 좀더 효율적으로 관리하기위해

임의의 길이(Prime Number)의 테이블을 이용하여 매핑하는 방법이다.

 

배열을 이용할때는 삭제하기 위해서는 시간복잡도가 O(n)만큼 들지만

해시법을 이용하면 O(1)만큼 들다.

 

---

 

해싱

HashMap()

1. key값을 임의의 수로 만들어주는 함수("GetKey()")를 이용하여 해시값을 구한다.
2. 해시값에 해당하는 주소가 가리키는 노드의 가장 끝단까지 이동한다.
3. 이동하면서 중복된 key값이 있는지 확인한다.
4. 가장 끝단에 노드를 만들어 Key, Daata값을 저장한다.

 

 

삭제

HashDelete()

1. "GetKey()"함수를 이용하여 해시값을 구한다.
2. 해시값에 해당하는 주소가 가리키는 노드부터 끝단까지 key값을 비교한다.
3. 일치한 값을 찾으면 이전 노드의 next에 찾은 노드의 next주소를 입력한다.
4. 찾은 노드를 삭제한다.

 

 

검색

HashFind()

1. "GetKey()"함수를 이용하여 해시값을 구한다.
2. 해시값에 해당하는 주소가 가리키는 노드부터 끝단까지 key값을 비교한다.
3. 일치하는 key값을 찾는다.

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>
#include <string.h>

#define HASH_SIZE 31 // 임의의 소수

typedef struct __Hash {
	struct __Hash* next;

	char key[32];
	char data[32];
} Hash;

struct __Hash* HashTable[HASH_SIZE];

void Init() {
	for (int i = 0; i < HASH_SIZE; i++) {
		HashTable[i] = malloc(sizeof(Hash));

		HashTable[i]->next = NULL;
	}
}

int GetKey(char *key) {
	// 각 문자를 정수로 변환하여 더한다.
	// HASH_SIZE로 나눈뒤 나머지를 출력한다.
	int c = 0;

	while (*key != '\0') {
		c += (int)(*key++);
	}

	return c % HASH_SIZE;
}

void HashMap(char* key, char* data) {
	Hash* tmp = HashTable[GetKey(key)];

	while (tmp->next != NULL) {
		// 가장 끝단의 노드로 이동
		if (strcmp(tmp->key, key) == 0) return 0; // 같은 key값이 있으면
		tmp = tmp->next;
	}

	Hash* h = malloc(sizeof(Hash));

	strcpy(h->key, key);
	strcpy(h->data, data);
	h->next = NULL;

	tmp->next = h; // 끝단의 노드의 next에 새로운 노드주소를 입력
}

void HashPrint() {
	Hash* h;

	for (int i = 0; i < HASH_SIZE; i++) {
		printf("[%2d] -> ", i);
		h = HashTable[i]->next;
		while (h != NULL) {
			printf("%s  ", h->data);
			h = h->next;
		}
		printf("\n");
	}
}

void HashFind(char* key) {
	Hash* h = HashTable[GetKey(key)]->next;

	while (h != NULL) {
		// 첫 노드부터 끝 노드까지 검색
		if (strcmp(h->key, key) == 0) {
			printf("Find Data -> [%2d] KEY : %s\tDATA : %s\n", GetKey(key), key, h->data);
			return 0;
		}
		h = h->next;
	}
	printf("No Data\n");
}

void HashDelete(char* key) {
	Hash* h_before = HashTable[GetKey(key)];
	Hash* h = HashTable[GetKey(key)]->next;

	while (h != NULL) {
		// 끝 노드까지 검색
		if (strcmp(h->key, key) == 0) {
			h_before->next = h->next;
			free(h);
			return 0;
		}
		h_before = h;
		h = h->next;
	}
	printf("No Data\n");
}

void clear() {
	Hash* h;

	for (int i = 0; i < HASH_SIZE; i++) {
		while (HashTable[i]->next != NULL) {
			h = HashTable[i]->next;
			HashTable[i]->next = h->next;
			free(h);
		}
		free(HashTable[i]);
	}
}

int main() {
	Init();

	HashMap("a", "aa");
	HashMap("b", "bb");
	HashMap("c", "cc");
	HashMap("d", "dd");
	HashMap("e", "ee");
	HashMap("f", "ff");
	HashMap("g", "gg");

	HashMap("aa", "11");
	HashMap("ab", "22");

	HashDelete("e");

	HashFind("ab0");
	HashFind("ab");

	HashPrint();

	clear();

	return 0;
}

#endif