[C++] 해시(Hash) 자료구조란? (C++로 구현하기)

해시(Hash) 자료구조란?

해시는 너무도 유명한 자료구조이기 때문에,

컴퓨터를 공부하는 분들이라면 누구나 한번쯤은 들어보셨을 것입니다.

이 자료구조는 왜 그렇게 중요한 것일까요?

아래의 상황을 보겠습니다.

 

3명의 사람 (김연아, 손흥민, 서장훈) 이 위와 같이 부탁을 했습니다.

그리고 이러한 기능을 C++ 를 사용해서 구현해달라고 했습니다.

파이썬과 다르게, 기본적으로 C++ 에서는 이런 기능을 지원하지 않습니다.

어떻게 기능을 구현해야 가장 효율적이고, 빠른 자료구조가 될까요?

 

답은, 각각의 이름(텍스트)에 대해서, 유일한 Key 값을 가지게 하는 것입니다.

만들어진 Key 값을 이용해서 자료에 접근한다면 O(1) 시간만에 접근할 수 있습니다.

아래와 같이 말입니다.

 

 

 

 

해시(Hash)의 동작원리

해시에서 Key를 생성하기 위한 다양한 알고리즘이 존재합니다.

MD-5나 SHA이 그 유명한 해시 알고리즘 중 하나입니다.

우리는 학습을 목표로, 문자열을 통해서 간단한 해시를 만드는 방법을 알아보겠습니다.

 

'apple' 이라는 문자열이 주어졌다고 가정해보겠습니다.

우리는 Key를 만들기 위해서, 특정한 소수인 '5381' 을 이용해보겠습니다.

 

Key는 최대한 중첩되지않고, 고르게 만드는 것이 좋다고 알려져있습니다.

그렇게 만들기 위해서 아래와 같은 과정을 거칠 것입니다.

 

(1) Hash 값을 왼쪽으로 5번 비트연산시킨다.

(2) 원본 Hash 값을 더한다.

(3) 한 문자의 ASCII 값을 더한다.

(4) 위의 결과를 모든 문자에 대해서 반복한다.

(5) 최종 값이 해시테이블의 범위를 벗어나면, 나머지 연산을 취해준다.

 

Hash의 최대 테이블 크기를 '8191'로 가정해보겠습니다.

상세한 과정을 보이면 아래와 같습니다.

 

이러한 간단하면서도 일반적인 계산은

나름 분포도가 좋은 계산이 나오는 것으로 보여집니다.

 

 

 

해시(Hash)의 충돌

좋습니다. 위와 같이 Key를 만들었고,

만들어진 Key의 위치에 자료를 삽입할 수 있습니다.

 

그런데, 엄밀히 말하면 Key라는 것은

최대한 분포도가 넓게 만들긴 하지만,

언젠가는 다른 문자열에 대해서 동일한 Key값이 발생할 수 있습니다.

 

예를 들어서,

'이승우'와 '손연재'가 동일한 Key값을 가질 수 있다는 것입니다.

이렇게 서로 다른 원본에 대해서 동일한 Key 값을 가지게 되는 현상을

해시에서 '충돌'이 발생했다고 말합니다.

 

충돌을 해결하는 방법은 크게 다음과 같습니다.

 

(1) 충돌이 일어난 인덱스를 뛰어넘어서, 빈 공간이 있는지 탐색 후 삽입

     → 개방주소법 (Open addressing)

(2) 충돌이 일어난 지점을 사용하되, 연결 리스트로 묶는 방법

     → 체이닝 (Chaning)

 

개방주소법의 경우, 인덱스만 증가시켜주면 되므로 안정적인 방법입니다.

체이닝의 경우, 정해진 해시테이블 이외의 주소를 추가로 할당해서

확장해서 사용할 수 있다는 장점이 있습니다.

예시 코드에서는 개방주소법을 이용해서 구현하였습니다.

 

 

 

구현 (C++)

#include <iostream>

#define MAX_TABLE	8191
#define MAX_KEY		64

typedef long long ll;

using namespace std;

typedef struct Hash {
	char key[MAX_KEY + 1];
	int data;
} Hash;
Hash table[MAX_TABLE];

ll hashGen(char key[]) {
	ll h = 5381;
	while (*key != '\0')
		h = (((h << 5) + h) + *key++) % MAX_TABLE;
	return h;
}

int m_strcmp(const char* str1, const char* str2) {
	while (*str1 != '\0' || *str2 != '\0') {
		if (*str1 != *str2) return *str1 - *str2;
		str1++; str2++;
	}
	return 0;
}

void m_strcpy(char dsc[], char src[]) {
	while (*src != '\0')
		*(dsc++) = *(src++);
}

int hashDelete(char key[]) {
	ll h = hashGen(key);
	int cnt = MAX_TABLE;

	while (table[h].key[0] != 0 && cnt--) {
		if (!m_strcmp(table[h].key, key)) {
			table[h].key[0] = 0;
			table[h].data = 0;
			return 1;
		}
		h = (h + 1) % MAX_TABLE;
	}
	return 0;
}

int hashAdd(char key[], int data) {
	ll h = hashGen(key);
	int cnt = MAX_TABLE;

	while (table[h].key[0] != 0 && cnt--) {
		if (!m_strcmp(table[h].key, key)) {
			table[h].data = data;
			return 1;
		}
		else cout << "[충돌 발생]\n";
		h = (h + 1) % MAX_TABLE;
	}

	if (cnt == -1) return 0;
	m_strcpy(table[h].key, key);
	table[h].data = data;
	return 1;
}

int hashFind(char key[], int* data) {
	ll h = hashGen(key);
	int cnt = MAX_TABLE;

	while (table[h].key[0] != 0 && cnt--) {
		if (!m_strcmp(table[h].key, key)) {
			*data = table[h].data;
			return 1;
		}
		h = (h + 1) % MAX_TABLE;
	}
	return 0;
}

int main(void) {
	while (true) {
		char key[64];
		int data;
		char c;
		cout << "[명령]\n1. 삽입\n2. 찾기\n3. 삭제\n4. 테이블 조회\n5. 종료\n→ ";
		cin >> c;

		switch (c) {
		case '1':
			cout << "[Key, Data 입력] ";
			cin >> key >> data;
			if (hashAdd(key, data)) cout << "[성공] 입력 완료\n";
			else cout << "[실패] 해시가 가득 찼습니다.\n";
			cout << "-----------------------------\n";
			break;
		case '2':
			cout << "[Key 입력] ";
			cin >> key;
			if (hashFind(key, &data)) cout << "[성공] " << data << '\n';
			else cout << "[실패] 존재하지 않는 데이터입니다.\n";
			cout << "-----------------------------\n";
			break;
		case '3':
			cout << "[Key 입력] ";
			cin >> key;
			if (hashDelete(key)) cout << "[성공] 삭제되었습니다.\n";
			else cout << "[실패] 존재하지 않는 데이터입니다.\n";
			cout << "-----------------------------\n";
			break;
		case '4':
			for (int i = 0; i < MAX_TABLE; i++)
				cout << "[" << i << "] " << table[i].key << ", " << table[i].data << '\n';
			cout << "-----------------------------\n";
			break;
		case '5':
			return 0;
		default:
			cout << "잘못 입력하였습니다.\n";
			cout << "-----------------------------\n";
			continue;
		}
	}

	return 0;
}