[자료구조] C++ HashTable 구현

 

#pragma once

#include <string>
#include <iostream>

class HashNode
{
private:
	std::string m_Key;
	int m_Value;
	HashNode* m_Next;

public:
	HashNode() :
		m_Next(nullptr)
	{
	}

	HashNode(const std::string& key, int val) :
		m_Key(key),
		m_Value(val),
		m_Next(nullptr)
	{
	}

	HashNode* GetNext()
	{
		return m_Next;
	}

	void SetNext(HashNode* node)
	{
		m_Next = node;
	}

	const std::string& GetKey() const
	{
		return m_Key;
	}

	int GetValue() const
	{
		return m_Value;
	}
};

// 노드를 담을 Linked List 방식의 Bucket
class HashBucket
{
private:
	int m_Size;
	HashNode* m_Head;

public:
	HashBucket()	:
		m_Size(0),
		m_Head(nullptr)
	{
		m_Head = new HashNode;
	}

	~HashBucket()
	{
		HashNode* node = m_Head;
		HashNode* next = nullptr;

		while(node != nullptr)
		{
			next = node->GetNext();
			delete node;
			node = next;
		}
	}

public:
	bool IsEmpty() const
	{
		return m_Size == 0;
	}

	void Push(HashNode* val)
	{
		HashNode* node = m_Head;
		HashNode* next = m_Head->GetNext();

		node->SetNext(val);
		val->SetNext(next);

		++m_Size;
	}

	HashNode* FindNode(const std::string& key) const
	{
		HashNode* node = m_Head;

		while(node != nullptr)
		{
			if (key == node->GetKey())
				break;

			node = node->GetNext();
		}

		return node;
	}

	void DeleteNode(const std::string& key)
	{
		HashNode* node = m_Head;
		HashNode* prev = nullptr;

		while(node != nullptr)
		{
			if (node->GetKey() == key)
			{
				if (prev)
					prev->SetNext(node->GetNext());
				else
					m_Head->SetNext(node->GetNext());

				delete node;
				--m_Size;
				return;
			}

			prev = node;
			node = node->GetNext();
		}
	}

	void Display()
	{
		HashNode* node = m_Head->GetNext();
		while(nullptr != node)
		{
			std::cout << node->GetValue() << " ";
			node = node->GetNext();
		}
	}
};


class HashMap
{
private:
	int m_BucketSize;
	int m_Size;
	HashBucket* m_Bucket;

private:
	int MakeHash(const std::string& key);

public:
	HashMap();
	HashMap(int bucketSize);
	~HashMap();

public:
	void Insert(const std::string& key, int val);
	void Delete(const std::string& key);
	int Find(const std::string& key);
	int operator[] (const std::string& key);
	void Display();
};

 

#include <iostream>
#include "HashMap.h"

// 간단한 해쉬 함수
int HashMap::MakeHash(const std::string& key)
{
	int hash = 401;
	int c;

	for (int i = 0; i < key.length(); ++i)
	{
		hash = ((hash << 4) + static_cast<int>(key[i])) % m_BucketSize;
	}

	return hash;
}

HashMap::HashMap():
	m_BucketSize(16),
	m_Size(0)
{
	m_Bucket = new HashBucket[m_BucketSize];
}

HashMap::HashMap(int bucketSize):
	m_BucketSize(bucketSize),
	m_Size(0)
{
	m_Bucket = new HashBucket[m_BucketSize];
}

HashMap::~HashMap()
{
	delete[] m_Bucket;
}

void HashMap::Insert(const std::string& key, int val)
{
	int hash = MakeHash(key);

	// 키가 같은 노드가 있는지 찾는다.
	HashNode* overlap = m_Bucket[hash].FindNode(key);

	// 중복 허용 X
	if (nullptr != overlap)
		return;

	// Bucket에 넣는다.
	m_Bucket[hash].Push(new HashNode(key, val));
}

void HashMap::Delete(const std::string& key)
{
	int hash = MakeHash(key);

	m_Bucket[hash].DeleteNode(key);
}

int HashMap::Find(const std::string& key)
{
	int hash = MakeHash(key);

	HashNode* find = m_Bucket[hash].FindNode(key);

	if (nullptr == find)
		return -1;

	return find->GetValue();
}

int HashMap::operator[](const std::string& key)
{
	int hash = MakeHash(key);

	HashNode* find = m_Bucket[hash].FindNode(key);

	if (nullptr == find)
		return -1;

	return find->GetValue();

}

void HashMap::Display()
{
	for(int i = 0; i < m_BucketSize; ++i)
		m_Bucket[i].Display();

	std::cout << "\n";
}

Chaining 방식으로 구현했다.