C++로 HashMap 직접 구현해보기 (Chaining + Rehash)

C++에서는 std::unordered_map이라는 해시 테이블을 제공한다.
하지만 실제로 해시 충돌이 어떻게 처리되는지, rehash는 언제 발생하는지,
load factor는 어떤 의미를 가지는지 구현하면서 이해하는 과정.
그래서 이번 글에서는 체이닝 방식을 사용하는 HashMap을 직접 구현하며 내부 동작을 정리해본다.

구현된 HashMap은 Separate Chaining(체이닝) 방식을 사용한다.
해시 충돌이 발생했을 때, 같은 버킷에 속한 요소들을 연결 리스트로 관리하는 방식이다.

전체 구조는 다음과 같다.

DD_HashMap
 ├─ vector<DD_HashBucket>
 │    ├─ dummy head node
 │    └─ linked list (DD_HashNode)
 └─ hash<Key> + modulo bucket size

구현의 핵심 요소는 아래 세 가지다.

1. 버킷 배열: std::vector<DD_HashBucket>
2. 충돌 처리 방식: 연결 리스트(Separate Chaining)
3. Rehash 조건: Load Factor(적재율)

 

1. 버킷 배열 (Bucket Array)

HashMap은 내부적으로 고정된 크기의 버킷 배열을 가진다.
각 Key는 해시 함수를 통해 하나의 버킷 인덱스로 매핑된다.

uint64_t GenerateHash(const Key& key, const std::vector<BucketType>& bucket)
{
    std::hash<Key> hasher;
    return hasher(key) % bucket.size();
}

 

• std::hash<Key>를 사용해 Key를 해시값으로 변환
• 현재 버킷 개수로 나머지 연산을 하여 인덱스를 결정
• Key 타입은 std::hash가 정의되어 있어야 한다

 

2. 해시 충돌 처리 – Separate Chaining

서로 다른 Key라도 같은 해시 값을 가질 수 있다.
이 문제를 **해시 충돌(Hash Collision)**이라고 한다.

이번 구현에서는 Separate Chaining 방식을 사용했다.
즉, 같은 버킷에 매핑되는 요소들은 연결 리스트로 관리된다.

DD_HashNode

template<typename Key, typename Value>
class DD_HashNode
{
    Key m_key;
    Value m_value;
    DD_HashNode* m_next;
};

 

각 노드는 Key / Value 쌍과 다음 노드를 가리키는 포인터를 가진다.

버켓에는 dummy head node가 있음, 노드는 항상 이 head 뒤에 추가된다.

 

3. Load Factor와 Rehash

HashMap의 성능은 Load Factor(적재율) 에 크게 영향을 받는다.

 

load factor = (현재 저장된 요소 수) / (버킷 개수)

Load Factor가 높아질수록:

• 한 버킷에 많은 노드가 몰림
• 연결 리스트 탐색 비용 증가
• 평균 시간 복잡도가 O(1)에서 멀어짐

Rehash 조건

 

constexpr float CHECK_MAXLOAD = 0.8f;

 

if (loadFactor >= CHECK_MAXLOAD) { Rehash(bucketSize * 2); }

Load Factor가 0.8 이상이 되면 Rehash를 수행하도록 구현했다.

---

Rehash 과정

Rehash는 다음 순서로 진행된다.

1. 기존보다 큰 버킷 배열 생성
2. 모든 기존 노드를 순회
3. 새로운 버킷 크기에 맞게 해시 값을 다시 계산
4. 노드를 새 버킷으로 이동
5. 기존 버킷과 swap

void Rehash(int32_t newSize)
{
    std::vector<BucketType> newBucket(newSize);

    for (int idx = 0; idx < m_bucket.size(); ++idx)
    {
        NodeType* currentNode = m_bucket[idx].GetHead();
        m_bucket[idx].SetHead(nullptr);

        while (currentNode)
        {
            NodeType* nextNode = currentNode->GetNext();
            currentNode->SetNext(nullptr);

            uint64_t newIdx = GenerateHash(currentNode->GetKey(), newBucket);
            newBucket[newIdx].AddNode(currentNode);

            currentNode = nextNode;
        }
    }
    m_bucket.swap(newBucket);
}

Rehash의 시간 복잡도는 O(n) 이지만,
자주 발생하지 않도록 설계되었기 때문에 전체 평균 성능에는 큰 영향을 주지 않을 것 같다.

---

시간 복잡도 정리

연산평균최악

Insert	O(1)	O(n)
Find	O(1)	O(n)
Delete	O(1)	O(n)
Rehash	O(n)	O(n)

---

마무리

이번 구현을 통해 단순히 unordered_map을 사용하는 것을 넘어,
해시 충돌 처리 방식, Load Factor의 의미, Rehash가 필요한 이유를
구현 관점에서 이해할 수 있었다.

표준 컨테이너는 대부분 이런 복잡한 과정을 내부에서 처리해주지만,
직접 구현해보면 자료구조의 특성과 한계를 훨씬 명확하게 체감할 수 있다.

다음에는 Open Addressing 방식이나
메모리 관리 개선(unique_ptr, allocator) 등을 적용해볼 예정이다.

전체 코드

#pragma once
#include <iostream>
#include <string>
#include <vector>

// --------------------------------------------------------------------------------------------
// DD_HashNode
// --------------------------------------------------------------------------------------------

template<typename Key, typename Value>
class DD_HashNode
{
public:
	void SetNext(DD_HashNode* node) { m_next = node; }
	void SetValue(const Value& value) { m_value = value; }

	DD_HashNode* GetNext() const { return m_next; }
	const Key& GetKey() const { return m_key; }
	Value& GetValue() { return m_value; }

public:
	DD_HashNode(const Key& key, const Value& value) : m_key(key), m_value(value), m_next(nullptr) {}
	DD_HashNode() : m_key(), m_value(), m_next(nullptr) {}

private:
	Key m_key{};
	Value m_value{};
	class DD_HashNode* m_next = nullptr;
};

// --------------------------------------------------------------------------------------------
// DD_HashBucket
// --------------------------------------------------------------------------------------------

template<typename Key, typename Value>
class DD_HashBucket
{
	using NodeType = DD_HashNode<Key, Value>;
public:
	void AddNode(NodeType* addingNode)
	{
		if (nullptr == addingNode)
			return;

		NodeType* movingNode = m_head->GetNext();
		m_head->SetNext(addingNode);
		addingNode->SetNext(movingNode);
		++m_size;
	}

	void DeleteNode(const Key& key)
	{
		NodeType* prev = m_head;
		NodeType* node = m_head->GetNext();

		while (node != nullptr)
		{
			if (node->GetKey() == key)
			{
				prev->SetNext(node->GetNext());
				delete node;
				--m_size;
				return;
			}
			prev = node;
			node = node->GetNext();
		}
	}

	NodeType* FindNode(const Key& key) const
	{
		NodeType* node = m_head->GetNext();
		while (node != nullptr)
		{
			if (node->GetKey() == key)
				return node;

			node = node->GetNext();
		}
		return nullptr;
	}

	void GetElements(std::vector<std::pair<Key, Value>>& outElements)
	{
		outElements.clear();
		outElements.reserve(m_size);

		NodeType* node = m_head->GetNext();
		while (node != nullptr)
		{
			outElements.emplace_back(node->GetKey(), node->GetValue());
			node = node->GetNext();
		}
	}

	void SetHead(NodeType* NewNode) { m_head = NewNode; }
	NodeType* GetHead() const { return m_head; }
	NodeType* GetNext() const { return m_head ? m_head->GetNext() : nullptr; }
	int32_t Size() const { return m_size; }

	void Print()
	{
		NodeType* node = m_head->GetNext();
		while (node != nullptr)
		{
			std::cout << node->GetValue() << " ";
			node = node->GetNext();
		}
	}
public:
	DD_HashBucket() : m_size(0), m_head(nullptr)
	{
		m_head = new NodeType();
	}

	~DD_HashBucket()
	{
		NodeType* node = m_head;
		while (node != nullptr)
		{
			NodeType* next = node->GetNext();
			delete node;
			node = next;
		}
	}
private:
	int32_t m_size = 0;
	NodeType* m_head = nullptr;
};

// --------------------------------------------------------------------------------------------
// DD_HashMap
// --------------------------------------------------------------------------------------------

constexpr int32_t BUCKET_SIZE = 16;
constexpr float CHECK_MAXLOAD = 0.8f;

template<typename Key, typename Value>
class DD_HashMap
{
	using BucketType = DD_HashBucket<Key, Value>;
	using NodeType = DD_HashNode<Key, Value>;
public:
	void Insert(const Key& key, const Value& val)
	{
		if (CheckLoadFactor())
		{
			size_t bucketSize = m_bucket.size();
			Rehash(bucketSize * 2);
		}
		Insert_Internal(key, val);
	}

	void Delete(const Key& key)
	{
		uint64_t idx = GenerateHash(key, m_bucket);
		m_bucket[idx].DeleteNode(key);
		m_size--;
	}

	Value& Find(const Key& key)
	{
		uint64_t idx = GenerateHash(key, m_bucket);
		NodeType* found = m_bucket[idx].FindNode(key);
		return found->GetValue();
	}

	Value& operator[](const Key& key)
	{
		Insert(key, Value{}); // try - emplace
		return Find(key);
	}

	void GetAllElements(std::vector<std::pair<Key, Value>>& outElements)
	{
		size_t bucketSize = m_bucket.size();

		outElements.clear();
		outElements.reserve(bucketSize);

		for (int idx = 0; idx < bucketSize; ++idx)
		{
			std::vector<std::pair<Key, Value>> bucketElements;
			m_bucket[idx].GetElements(bucketElements);
			outElements.insert(outElements.end(), bucketElements.begin(), bucketElements.end());
		}
	}

	void Print()
	{
		size_t bucketSize = m_bucket.size();
		for (int idx = 0; idx < bucketSize; ++idx)
		{
			std::cout << "[" << idx << "] ";
			m_bucket[idx].Print();
			std::cout << "\n";
		}
	}

	size_t Size() { return m_size; }

private:
	uint64_t GenerateHash(const Key& key, const std::vector<BucketType>& bucket)
	{
		std::hash<Key> hasher;
		uint64_t Hash = hasher(key) % bucket.size();
		return Hash;
	}

	bool CheckLoadFactor()
	{
		int32_t bucketSize = m_bucket.size();
		float loadFactor = (static_cast<float>(m_size) / static_cast<float>(bucketSize));
		//std::cout << "item size :" << m_size << ", bucket size :" << bucketSize << ", load factor :" << loadFactor << std::endl;
		return loadFactor >= CHECK_MAXLOAD;
	}

	void Rehash(int32_t newSize)
	{
		std::vector<BucketType> newBucket(newSize);
		for (int idx = 0; idx < m_bucket.size(); ++idx)
		{
			NodeType* currentNode = m_bucket[idx].GetHead();
			m_bucket[idx].SetHead(nullptr);
			while (currentNode)
			{
				NodeType* nextNode = currentNode->GetNext();
				currentNode->SetNext(nullptr);

				uint64_t newIdx = GenerateHash(currentNode->GetKey(), newBucket);
				newBucket[newIdx].AddNode(currentNode);

				currentNode = nextNode;
			}
		}
		m_bucket.swap(newBucket);
	}

	void Insert_Internal(const Key& key, const Value& val)
	{
		uint64_t idx = GenerateHash(key, m_bucket);
		if (NodeType* found = m_bucket[idx].FindNode(key))
		{
			return;
		}

		NodeType* newNode = new NodeType(key, val);
		m_bucket[idx].AddNode(newNode);
		m_size++;
	}

public:
	DD_HashMap() : m_bucket(BUCKET_SIZE), m_size(0) {}
	DD_HashMap(int32_t bucketSize) : m_bucket(bucketSize), m_size(0) {}
	~DD_HashMap() {}

private:
	std::vector<BucketType> m_bucket{};
	int32_t m_size = 0;
};