HASH(해쉬)

##해시테이블의 장점

해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서입니다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 됩니다.

색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있습니다. 위 그림의 경우 해시함수에 ‘Lisa Smith’를 입력하면 02라는 색인이 생성됩니다.

해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적입니다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 O(1)  O(1) 을 지향합니다.

해시테이블을 다른 자료구조와 비교해보겠습니다. 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 O(nlogn) 입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 O(1) 이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵습니다.

해시는 보안 분야에서도 널리 사용된다고 합니다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문입니다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있습니다.

다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다고 합니다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠습니다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것입니다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어집니다.

/*
해쉬?
1)임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환하는것
2)즉시 위치를 참조 할수 있으므로 저장 및 탐색에 용이 O(1)
3) Key-Value의 형태
4)배열에 대한 크기를 고려할 수 없기 때문에 충돌 해법을 고려해야한다
*/
/*
#include<iostream>
#define MAX_HASH 10
#define HASH_KEY(key) key%MAX_HASH

using namespace std;

typedef struct Node
{
	int id;
}Node;

Node *hashTable[MAX_HASH];

int main()
{
	for (int i = 0; i < MAX_HASH; i++)
	{
		Node* node = (Node*)malloc(sizeof(Node));
		node->id = i;
		hashTable[i] = node;
	}
	return 0; 
}
*/
//하지만 이렇게만 하면 동일한 키값이 생기기 때문에 충돌이 발생
//chaing 방식을 이용하여 해결한다.
//hashTable[1]:(1)->(11)->(21)->(31)..

#include<iostream>
#define MAX_HASH 10
#define HASH_KEY(key) key%MAX_HASH //해쉬 테이블에서 key가 중복될경우 가르킬 다음노드 

using namespace std;

typedef struct Node
{
	int id;
	Node* hashNext; //해쉬테이블에서 키가 중복될 경우 가르킬 다음 노드
}Node;

Node *hashTable[MAX_HASH];

//추가
void AddHashData(int key, Node *node)
{
	int hash_key = HASH_KEY(key);
	if (hashTable[hash_key] == NULL)
	{
		hashTable[hash_key] = node; //데이터가 처음들어온것이므로 데이터저장
	}
	else
	{
		node->hashNext = hashTable[hash_key];//새로운 노드 링크필드에 ,테이블에 있는 노드 주소를 넣어 연결 
		hashTable[hash_key] = node;//해쉬 테이블에 새 노드 삽입
	}
}
//삭제
void DelHashData(int id)
{
	int hash_key = HASH_KEY(id);
	if (hashTable[hash_key] == NULL)return; //지울게 없다면

	Node *delNode = NULL;
	if (hashTable[hash_key]->id == id)
	{
		delNode = hashTable[hash_key];
		hashTable[hash_key] = hashTable[hash_key]->hashNext;
	}
	else
	{
		Node *node = hashTable[hash_key];
		Node *next = node->hashNext;
		while (next)
		{
			if (next->id == id)
			{
				node->hashNext = next->hashNext;//현재 노드를 (삭제하고 연결될) 그다음 노드의 주소와 연결
				delNode = next;
				break;
			}
			node = next;
			next = node->hashNext;
		}
	}
	free(delNode);
}
//데이터 탐색
Node* FindHashData(int id)
{
	int hash_key = HASH_KEY(id);
	if (hashTable[hash_key] == NULL)return NULL;
	if (hashTable[hash_key]->id == id)
	{
		return hashTable[hash_key];
	}
	else
	{
		Node* node = hashTable[hash_key];
		while (node->hashNext)
		{
			if (node->hashNext->id == id)
			{
				return node->hashNext;
			}
			node = node->hashNext;
		}
		return NULL;
	}
}
//테이블 출력
void printAllHashData()
{
	for (int i = 0; i < MAX_HASH; i++)
	{
		if (hashTable[i] != NULL)
		{
			Node *node = hashTable[i];
			while (node->hashNext)
			{
				cout << node->id << endl;
				node = node->hashNext;
			}
			cout << node->id << endl;
		}
		cout << endl;
	}
}
int main()
{
	int saveidx[101] = { 0, };
	for (int i = 0; i < 100; i++)
	{
		Node* node = (Node*)malloc(sizeof(Node));
		node->id = rand() % 1000;
		node->hashNext = NULL;
		AddHashData(node->id, node);
		saveidx[i] = node->id;
	}
	printAllHashData();
	for (int i = 0; i < 50; i++)
	{
		DelHashData(saveidx[i]);
	}
	printAllHashData();

	for (int i = 50; i < 100; i++)
	{
		DelHashData(saveidx[i]);
	}
	printAllHashData();
	return 0;
}