알고리즘...95

해시 테이블, 체이닝 처리 구현

HashTable_Chaining.h

#pragma once
#include "../Common.h"
#include "HashTable.h"
#include <vector>
#include <list>

using std::vector;
using std::list;

/// <summary>
/// 충돌 해결 방법 중 체이닝을 구현한 해시 테이블
/// </summary>
class HashTable_Chaining : public HashTable
{
public:
	HashTable_Chaining(HashFunction hashFunction = HashFunction::Division);

	virtual void Add(int data) override;
	virtual void Remove(int data) override;
	virtual bool Contains(int data) override;
	virtual void Clear() override;

	virtual void PrintHashTable() override;

private:
	vector<list<int>> m_table;
};

 

HashTable_Chaining.cpp

#include "HashTable_Chaining.h"

#pragma region Public Functions
/// <summary>
/// 해시 함수를 결정하고 해시 테이블을 초기화한다.
/// </summary>
/// <param name="hashFunction">사용할 해시 함수</param>
HashTable_Chaining::HashTable_Chaining(HashFunction hashFunction)
	: HashTable(hashFunction)
{
	for (int i = 0, total = Size(); i < total; i++)
	{
		m_table.push_back(list<int>());
	}
}

/// <summary>
/// 데이터를 해시 테이블에 추가한다.
/// </summary>
/// <param name="data">추가할 데이터</param>
void HashTable_Chaining::Add(int data)
{
	if (Contains(data))
	{
		return;
	}

	int idx{ GetHashIndex(data) };
	m_table[idx].push_back(data);
}

/// <summary>
/// 데이터를 해시 테이블에서 제거한다.
/// </summary>
/// <param name="data">제거할 데이터</param>
void HashTable_Chaining::Remove(int data)
{
	if (!Contains(data))
	{
		return;
	}

	int idx{ GetHashIndex(data) };
	m_table[idx].remove(data);
}

/// <summary>
/// 주어진 값이 해시 테이블에 존재하는지 여부를 반환한다.
/// </summary>
/// <param name="data">찾을 데이터</param>
/// <returns>존재 여부</returns>
bool HashTable_Chaining::Contains(int data)
{
	int idx{ GetHashIndex(data) };
	for (auto d = m_table[idx].cbegin(); d != m_table[idx].cend(); d++)
	{
		if (*d == data)
		{
			return true;
		}
	}
	return false;
}

/// <summary>
/// 해시 테이블의 모든 데이터를 지운다.
/// </summary>
void HashTable_Chaining::Clear()
{
	for (int i = 0, total = Size(); i < total; i++)
	{
		m_table[i].clear();
	}
}

/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void HashTable_Chaining::PrintHashTable()
{
	HashTable::PrintHashTable();

	for (int i = 0, total = Size(); i < total; i++)
	{
		std::cout << " Index " << i << " : ";
		if (m_table[i].size() > 0)
		{
			auto d = m_table[i].cbegin();
			while (true)
			{
				std::cout << *d;
				d++;

				if (d == m_table[i].cend())
				{
					break;
				}

				std::cout << " - ";
			}
		}
		else
		{
			std::cout << "EMPTY";
		}
		std::cout << '\n';
	}
	std::cout << '\n';
}
#pragma endregion

 

main.cpp

#include "Common.h"
#include "해시테이블/HashTable_Chaining.h"

int main()
{
	HashTable_Chaining hashTable;

	int arr[] = { 1, 3, 5, 7, 9,
		12, 14, 16, 18, 20,
		23, 25, 27, 29,
		32, 34, 36, 38,
		40, 43, 45, 47, 49 };

	for (int i = 0; i < 23; i++)
	{
		hashTable.Add(arr[i]);
	}

	hashTable.PrintHashTable();

	hashTable.Remove(16);
	hashTable.Remove(27);
	hashTable.Remove(47);

	hashTable.PrintHashTable();
}

 

실행결과

------------------------------------------
- Class Name  : class HashTable * __ptr64
- HashFuncion : Division
------------------------------------------
 Index 0 : 34
 Index 1 : 1 - 18
 Index 2 : 36
 Index 3 : 3 - 20
 Index 4 : 38
 Index 5 : 5
 Index 6 : 23 - 40
 Index 7 : 7
 Index 8 : 25
 Index 9 : 9 - 43
 Index 10 : 27
 Index 11 : 45
 Index 12 : 12 - 29
 Index 13 : 47
 Index 14 : 14
 Index 15 : 32 - 49
 Index 16 : 16

------------------------------------------
- Class Name  : class HashTable * __ptr64
- HashFuncion : Division
------------------------------------------
 Index 0 : 34
 Index 1 : 1 - 18
 Index 2 : 36
 Index 3 : 3 - 20
 Index 4 : 38
 Index 5 : 5
 Index 6 : 23 - 40
 Index 7 : 7
 Index 8 : 25
 Index 9 : 9 - 43
 Index 10 : EMPTY
 Index 11 : 45
 Index 12 : 12 - 29
 Index 13 : EMPTY
 Index 14 : 14
 Index 15 : 32 - 49
 Index 16 : EMPTY

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소