hash map

언어 차원에서 제공하는 알고리즘은 성능, 안정성 등에서 검증이 된 것입니다. 그렇지 않으면 해당 언어의 신뢰도에 치명적인 손상을 입힐 수 있기 때문입니다. 때문에 검증된 이론, 수학적으로 증명된 공식 등을 통해서 구현됩니다. 자료구조는 직접 개발하기 위해 공부한다기 보다는 간단한 기능을 직접 구현해보면서 개념과 기본적인 흐름을 파악하는 데 의의가 있는 것 같습니다.

 

해시맵은 데이터를 배열에 넣습니다. 그러므로 O(1)의 시간복잡도를 가지지만 데이터가 많아질수록 중복된 해시 코드를 얻게 될 확률이 올라갑니다. 그래서 C++ 표준 라이브러리인 std::unordered_map은 일정 수준 이상에서 std::map보다 성능이 안 나올 수 있습니다. 해시맵은 최악의 경우에는 O(n)까지 성능이 저하될 수 있습니다. 최근의 해시 알고리즘은 해시 코드가 균등하게 분포되는 경향을 가지고 있습니다.

 

충돌과 관련한 자세한 설명은 링크로 대신합니다.

 

간단히 만들어 본 해본 해시맵은 표준 라이브러리인 std::hash를 이용해 해시 코드를 얻었으며 충돌이 있을 경우 separate chaining 개념을 리스트로 구현했습니다. 데이터 삽입은 인덱스 연산자를 통하며 제거 함수가 하나 있습니다. 데이터의 삽입 삭제가 많을 경우 리스트가 유리하겠고 탐색이 잦은 경우 균형 이진 트리가 유리합니다. 자바의 경우 버킷의 사이즈가 6이하일 때는 리스트를, 8이상은 레드-블랙 트리로 전환합니다. 차이가 1이 아니라 2인 이유는 사이즈 하나 차이로 변환되는 오버헤드를 방지하기 위해서라고 합니다(출처). C++의 경우는 자료를 찾는데로 내용을 추가하겠습니다.

 

코드

// HashMap.h
#pragma once
#include <list>
#include <vector>

class HashMap
{
private:
	class Bucket
	{
		std::list<std::pair<int, int>> _datas;

	public:
		int& get_value(int key);
		std::pair<int, int>& get(int key);
		void remove(int key);
	};

private:
	std::vector<Bucket> _buckets;
	std::pair<int, int>& get(int key);

public:
	HashMap();
	HashMap(int size);

	int& operator[](int key);
	void remove(int key);

	size_t hash(int key);
	int get_index(size_t key, int size);
};

//HashMap.cpp
#include "HashMap.h"
#include <functional>

HashMap::HashMap()
	:_buckets(31) {}

HashMap::HashMap(int size)
	:_buckets(size) {}

std::pair<int, int>& HashMap::get(int key)
{
	int i = get_index(hash(key), _buckets.size());
	return _buckets[i].get(key);
}

int& HashMap::operator[](int key)
{
	int i = get_index(hash(key), _buckets.size());
	return _buckets[i].get_value(key);
}

void HashMap::remove(int key)
{
	int i = get_index(hash(key), _buckets.size());
	_buckets[i].remove(key);
}

size_t HashMap::hash(int key)
{
	std::hash<int> h;
	return h(key);
}

int HashMap::get_index(size_t key, int size)
{
	return key % size;
}

int& HashMap::Bucket::get_value(int key)
{
	for (auto iter = _datas.begin(); iter != _datas.end(); ++iter)
	{
		auto& [k, v] = *iter;
		if (key == k) return v;
	}
	_datas.push_back({ key, -1 });
	return _datas.back().second;
}

std::pair<int, int>& HashMap::Bucket::get(int key)
{
	for (auto iter = _datas.begin(); iter != _datas.end(); ++iter)
	{
		if (iter->first == key) return *iter;
	}
	_datas.push_back({ key, -1 });
	return _datas.back();
}

void HashMap::Bucket::remove(int key)
{
	_datas.remove_if([&](auto& pair) {
		auto& [k, v] = pair;
		return k == key;
		});
}

// main.cpp
#include <iostream>
#include "HashMap.h"
int main()
{
	HashMap hash_map;
	hash_map[12] = 34;
	hash_map[34] = 56;
	std::cout << hash_map[12] << std::endl;	
	hash_map[12] = 12;
	std::cout << hash_map[12] << std::endl;
	std::cout << hash_map[34] << std::endl;
	hash_map.remove(12);
	std::cout << hash_map[12] << std::endl;
}

위의 예제는 패스트캠퍼스 C++ 올인원 패키지 강의의 김대희 개발자의 예제 코드를 참고했습니다