해시맵 C++

 데이터 검색시 시간 복잡도가 상수라고 알려진 해시맵

---

 데이터를 저장하는 하나의 방법으로 <key, value>의 쌍을 이룬다. 특정 key를 기반으로 value를 저장했을때, 저장한 value를 찾기 위해서는 key를 기반으로 검색한다.

 

 해시맵을 알기 위해서는 해시함수를 필연적으로 알아야한다.

 

해시함수

 어떤 정보를 수학적인 연산처리에 의해 고유한 값을 만들어내는 함수다. 즉, A라는 값을 해시함수에 넣었을 때 1이란 값이 나오고 B라는 값을 해시함수에 넣었을 때 2란 값이 나오는 방식이다.

 

 위 예시에서 순차적으로 값을 내어주었기 때문에 혼동할 수 있는데, 해시함수는 아래의 조건을 만족해야 안정적인 함수이다.

• 눈사태효과를 가진다.[# 들어오는 값이 아주 조금만 변해도 완전히 다른 값이 산출된다.]
• 입력에는 하나의 출력만 존재한다.[# 입력과 출력의 값이 1:1 매칭이 된다.] 즉, 여러 입력이 하나의 출력으로 귀결되지 않는다.

 

 해시 함수는 굉장히 다양한 곳에서 사용되는데, 보안분야[# 단방향 암호화로 이용하는 경우도 많다]에서 이용하거나 파일의 무결성을 확인하는 용도로 사용하곤 한다.

 

---

해시맵

 해시맵은 <해시함수>의 특성을 이용해 만든 자료구조이다. <key, value>에서 고유한 key 값을 가지므로, key에 맞는 메모리 공간에 value를 입력하고 읽어들이는데 유용하다. 즉, 해시맵의 핵심은 해시함수라는 점이다.

 

해시맵 구현

 다음은 실제 해시맵의 작동 방식을 보기 위해 작성한 예제 코드이다.

# 해시맵 예제 코드

#include <stdio.h>

class hashMap {
	int* list;
	size_t capacity;

public:
	int GetHashValue(const char* key) {
		int value = 0;
		for (int i = 0; key[i]; ++i) {
			value += key[i];
		}
		return value % capacity;
	}

	void Input(const char* key, int value) {
		int index = GetHashValue(key);

		printf("---입력---\n");
		printf("  key: %s\n", key);
		printf("value: %d\n", value);
		printf("index: %d\n", index);
		printf("\n");

		list[index] = value;
	}

	int Output(const char* key) {
		int index = GetHashValue(key);
		int value = list[index];
		printf("---출력---\n");
		printf("  key: %s\n", key);
		printf("value: %d\n", value);
		printf("index: %d\n", index);
		printf("\n");
		return value;
	}

	void Print() {
		printf("해시맵 출력:\n\n");
		for (size_t i = 0; i < capacity; ++i) {
			printf("%3d: %3d%c", i, list[i], (i + 1) % 5 ? '\t' : '\n');
		}
		printf("\n\n");
	}

public:
	hashMap() : hashMap{10} {
	}

	hashMap(size_t capacity) : capacity{capacity}, list{nullptr} {
		list = new int[capacity] {};
	}

	~hashMap() {
		if (list) {
			delete[] list;
			list = nullptr;
		}
	}

};

int main() {
	hashMap hmap{};

	hmap.Print();

	hmap.Input("Hello world", 432);
	hmap.Input("world", 5);
	hmap.Input("programming", 1);

	hmap.Print();

	hmap.Output("world");

}

 참고: C++의 표준 입출력 라이브러리는 iostream이지만 예제이기도 하고 편의상 C 표준 입출력 라이브러리인 stdio.h를 사용했다.

 코드를 보면 내부 데이터는 배열로 관리가 되지만, 각 인덱스 요소에 접근할 때는 GetHashValue 메서드를 통해 이루어짐을 볼 수 있다. 

 

 

해시충돌

 좋은 해시함수는 입력과 출력의 값이 1:1 대응하도록 구성한다. 그러나 1:1로 대응시켜 메모리를 처리하려면 상당한 양의 메모리 소비가 발생할 수밖에 없다.

 

 예컨데 <해시맵 구현>에서 보인 코드에서 키값으로 world를 준 공간은 다른 키값으로도 접근이 가능하다. 예제에서 제공한 해시함수의 경우 전달받은 모든 문자열을 더한 값을 해시맵 공간(capacity)로 나눈 나머지로 출력을 하고 있다. 즉, 키값으로 world로 준 것과 world 문자열을 reverse한 dlrow로 준 것이나 동일한 공간을 가리킨다는 점이다. 때문에 적절한 해시함수를 구현하는 것이 해시맵의 중점이다.

 

 이런 식으로 동일 공간을 가리키게 되면 주로 알려진 대응책으로는 몇가지가 있다.

 

# 해시충돌을 관리하기 위해서는 key값이 저장되어야 한다.

 

공간 확장

 예제에서 제공하는 해시함수를 이용한경우 이 방식은 사용할 수 없다. 해시함수가 어떻게 되던 동일한 공간을 가리키기 때문이다.

 

 그러나 예제의 해시함수를 사용하지 않고 더 나은 해시함수를 사용한다면 이야기가 달라진다. world와 dlrow의 고유값이 다르다면, 예컨데 해시맵 공간의 크기와 world 키의 고유값은 20이고 dlrow는 40이라면 공간을 두 배 늘리는 것으로 다른 공간을 가리키도록 구현할 수 있다.

 

# 왜 예제의 해시함수로는 이 방식을 사용할 수 없는가

 예제의 해시함수는 첫 문자부터 마지막문자의 값을 모두 더한 합을 해시맵의 capacity값으로 나눈 나머지를 반환하도록 구현되어 있다.

1. 첫 문자부터 마지막 문자까지의 합을 구한다. 이 값을 plainValue라 가정한다.
2. plainValue의 값을 capacity로 나눈 나머지를 반환한다. 반환되는 값을 adjustValue라 가정한다.

이 경우 실제 메모리 접근에 영향을 주는 값은 plainValue이다. 그러나 예제로 제공하는 해시함수를 사용하면 world나, 이를 뒤집은 dlrow나 동일한 plainValue를 가지게 되므로 공간확장을 통해 충돌을 제어하는 방식은 유용하지 않다.

 이 방식의 최대 단점은 해시함수의 의존도가 상당히 높다는 점이다. 만일 해시충돌이 자주 일어나는 해시함수를 사용하는 경우, 해시충돌을 공간 확장으로 방어할수는 없다. 때문에 이 방식은 가급적 다른 방식을 사용하면서 보조하는 수준으로 생각해야한다.

 

체이닝(chaining)

 충돌이 일어났을 때 연결리스트(Linked List)를 이용하는 방식이다. 때문에 내부적으로 연결리스트 형식으로 값을 보관해야한다.

 

 이미지로 보게 되면 아래와 같다.

 충돌이 일어나면 동일 인덱스 상에 연결리스트를 구성해서 관리하는 방식이다. 이 방식으로 충돌 제어를 하게 되면 고정된 해시맵에서 무한정 데이터 첨삭이 가능하다.

 

 다만, 인덱스에 접근한 이후에는 연결리스트에서의 탐색으로 진행하므로 연결리스트 관리도 함께 해주는편이 성능 향상에 좋다.

 

재배치

 해시맵에 데이터를 넣을 때 처음 접근하는 인덱스에 이미 데이터가 존재해 충돌이 일어나게 되면, 연산을 거쳐 새로운 위치에 집어넣는 방식이다. 해당 방식은 공간의 크기는 조절하지 않으므로 만일 해시맵이 모두 찼다면 구현에 따라서 오류를 일으킬 수 있다. 때문에 <공간 확장>옵션과 함께 사용해야한다.

 

 "world"키를 기반으로 설명하면, 해당 키값을 예제 코드로 연산하게 되면[# capacity 12 기준] 2번 인덱스를 가리킨다. 그 다음 "dlrow" 키를 연산하면 동일하게 2번 인덱스를 가리키는데, 이미 해당 공간은 "world"가 가지고 있으므로 충돌이 일어난다.

 

 이 때 충돌이 일어나면 해당 인덱스에서 3을 더하는 것으로 충돌을 무마시킨다. 때문에 "dlrow"는 5번 인덱스를 가지게 된다.

 

# index