프로그래밍 기초/알고리즘
해시 테이블 구현 및 테스트
niamdank
2022. 1. 7. 17:51
해시 테이블 구현
STL의 vector를 이용하여 해시 테이블을 구현한다.
해시 테이블 기본 클래스
해시 테이블 처리 중 충돌 처리에 따라 함수를 나누기 위해 기본 기능을 가진 클래스를 구현한다.
HashTable.h
#pragma once
#include "../Common.h"
#include <cmath>
#include <string>
using std::string;
/// <summary>
/// 해시 테이블에서 사용할 해시 함수
/// </summary>
enum class HashFunction
{
Division,
Multiplication,
};
/// <summary>
/// 해시 테이블의 구성 요소 테스트를 위한 베이스 클래스
/// </summary>
class HashTable
{
public:
HashTable(HashFunction hashFunction = HashFunction::Division) : m_hashFunction(hashFunction) { m_size = Default_Table_Size; };
virtual void Add(int data) = 0;
virtual void Remove(int data) = 0;
virtual bool Contains(int data) = 0;
virtual void Clear() = 0;
virtual void Resize();
virtual void PrintHashTable(string hashTableName = "HashTable");
private:
int GetHashIndexByDivision(int data);
int GetHashIndexByMultiplication(int data);
string GetHashFunctionString();
protected:
virtual int GetHashIndex(int data);
int GetHashIndex(int data, HashFunction hashFunction);
int Size() { return m_size; }
HashFunction CurrentHashFunction() { return m_hashFunction; }
private:
HashFunction m_hashFunction;
int m_size;
static const int Default_Table_Size{ 17 };
};
HashTable.cpp
#include "HashTable.h"
#pragma region Public Functions
/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void HashTable::PrintHashTable(string hashTableName)
{
std::cout << "------------------------------------------\n";
std::cout << "- Class Name : " << hashTableName << '\n';
std::cout << "- HashFuncion : " << GetHashFunctionString() << '\n';
std::cout << "------------------------------------------\n";
}
/// <summary>
/// 해시 테이블의 크기를 조정한다.
/// </summary>
void HashTable::Resize()
{
m_size *= 2;
}
#pragma endregion
#pragma region Private Functions
/// <summary>
/// 나누기 방법을 이용해 주어진 값의 해쉬 인덱스를 생성해 반환한다.
/// </summary>
/// <param name="data">인덱스를 찾을 데이터</param>
/// <returns>해쉬 테이블에서의 인덱스</returns>
int HashTable::GetHashIndexByDivision(int data)
{
return data % m_size;
}
/// <summary>
/// 곱하기 방법을 이용해 주어진 값의 해쉬 인덱스를 생성해 반환한다.
/// </summary>
/// <param name="data">인덱스를 찾을 데이터</param>
/// <returns>해쉬 테이블에서의 인덱스</returns>
int HashTable::GetHashIndexByMultiplication(int data)
{
static double multiplePrimeNumber = (std::sqrt(5) - 1.0) / 2.0;
return static_cast<int>(std::floor(std::fmod(data * multiplePrimeNumber, 1) * m_size));
}
/// <summary>
/// 현재 해쉬 함수를 string 으로 반환한다.
/// </summary>
/// <returns>해쉬 함수 string</returns>
std::string HashTable::GetHashFunctionString()
{
if (m_hashFunction == HashFunction::Multiplication)
{
return "Multiplication";
}
return "Division";
}
#pragma endregion
#pragma region Protected Functions
/// <summary>
/// 주어진 데이터를 이용하여 해쉬 인덱스를 생성해 반환한다.
/// </summary>
/// <param name="data">인덱스를 찾을 데이터</param>
/// <returns>해쉬 테이블에서의 인덱스</returns>
int HashTable::GetHashIndex(int data)
{
if (m_hashFunction == HashFunction::Multiplication)
{
return GetHashIndexByMultiplication(data);
}
return GetHashIndexByDivision(data);
}
/// <summary>
/// 주어진 데이터를 이용하여 해쉬 인덱스를 생성해 반환한다.
/// </summary>
/// <param name="data">인덱스를 찾을 데이터</param>
/// <param name="hashFunction">사용할 해쉬 함수</param>
/// <returns>해쉬 테이블에서의 인덱스</returns>
int HashTable::GetHashIndex(int data, HashFunction hashFunction)
{
if (hashFunction == HashFunction::Multiplication)
{
return GetHashIndexByMultiplication(data);
}
return GetHashIndexByDivision(data);
}
#pragma endregion
테스트를 위한 main 함수의 구성은 다음과 같다.
main.cpp
#include "Common.h"
#include "해시테이블/HashTable_OpenAddressing_DoubleHashing.h"
int main()
{
HashTable_OpenAddressing_DoubleHashing 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,
11, 21, 31, 41 ,51,
61, 71, 81, 91, 2
};
for (int i = 0; i < 33; i++)
{
hashTable.Add(arr[i]);
}
hashTable.PrintHashTable();
hashTable.Remove(16);
hashTable.Remove(27);
hashTable.Remove(47);
hashTable.PrintHashTable();
}
체이닝을 이용한 해시 테이블 구현
충돌 처리 중 체이닝을 이용하는 해시 테이블을 구현한다.
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(string hashTableName = "HashTable_Chaining") 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(string hashTableName)
{
HashTable::PrintHashTable(hashTableName);
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
실행결과
------------------------------------------
- Class Name : HashTable_Chaining
- HashFuncion : Division
------------------------------------------
Index 0 : 34 - 51
Index 1 : 1 - 18
Index 2 : 36 - 2
Index 3 : 3 - 20 - 71
Index 4 : 38 - 21
Index 5 : 5
Index 6 : 23 - 40 - 91
Index 7 : 7 - 41
Index 8 : 25
Index 9 : 9 - 43
Index 10 : 27 - 61
Index 11 : 45 - 11
Index 12 : 12 - 29
Index 13 : 47 - 81
Index 14 : 14 - 31
Index 15 : 32 - 49
Index 16 : 16
------------------------------------------
- Class Name : HashTable_Chaining
- HashFuncion : Division
------------------------------------------
Index 0 : 34 - 51
Index 1 : 1 - 18
Index 2 : 36 - 2
Index 3 : 3 - 20 - 71
Index 4 : 38 - 21
Index 5 : 5
Index 6 : 23 - 40 - 91
Index 7 : 7 - 41
Index 8 : 25
Index 9 : 9 - 43
Index 10 : 61
Index 11 : 45 - 11
Index 12 : 12 - 29
Index 13 : 81
Index 14 : 14 - 31
Index 15 : 32 - 49
Index 16 : Empty
개방 주소 방법을 이용한 해시 테이블 구현
충돌 처리 중 개방 주소 방법을 이용하여 해시 테이블을 구현한다.
- 개방주소 방법 해시 테이블의 기본 클래스
개방 주소 방법을 이용한 해시 테이블에서 충돌 처리 함수를 나누기 위한 클래스를 구현한다.
HashTable_OpenAddressing.h
#pragma once
#include "../Common.h"
#include "HashTable.h"
#include <vector>
#include <list>
using std::vector;
using std::list;
/// <summary>
/// 충돌 해결 방법 중 체이닝을 구현한 해시 테이블
/// </summary>
class HashTable_OpenAddressing : public HashTable
{
public:
HashTable_OpenAddressing(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 Resize() override;
virtual void PrintHashTable(string hashTableName = "HashTable_OpenAddressing") override;
private:
bool IsCollided(int idx);
bool NeedToResize();
void ResetTable();
int LimitCount() { return Size() * 3 / 4; }
protected:
virtual int GetHashIndex(int data) override;
virtual int GetProperHashIndex(int idx, int data) = 0;
protected:
vector<int> m_table;
int m_usedCount{ 0 };
static const int Empty{ INT_MAX };
static const int Deleted{ -INT_MAX };
};
HashTable_OpenAddressing.cpp
#include "HashTable_OpenAddressing.h"
#pragma region Public Functions
/// <summary>
/// 해시 함수를 결정하고 해시 테이블을 초기화한다.
/// </summary>
/// <param name="hashFunction">사용할 해시 함수</param>
HashTable_OpenAddressing::HashTable_OpenAddressing(HashFunction hashFunction)
: HashTable(hashFunction)
{
ResetTable();
}
/// <summary>
/// 데이터를 해시 테이블에 추가한다.
/// </summary>
/// <param name="data">추가할 데이터</param>
void HashTable_OpenAddressing::Add(int data)
{
if (Contains(data))
{
return;
}
int idx{ GetHashIndex(data) };
m_table[idx] = data;
m_usedCount++;
if (NeedToResize())
{
Resize();
}
}
/// <summary>
/// 데이터를 해시 테이블에서 제거한다.
/// </summary>
/// <param name="data">제거할 데이터</param>
void HashTable_OpenAddressing::Remove(int data)
{
if (!Contains(data))
{
return;
}
int idx{ GetHashIndex(data) };
m_table[idx] = Deleted;
}
/// <summary>
/// 주어진 값이 해시 테이블에 존재하는지 여부를 반환한다.
/// </summary>
/// <param name="data">찾을 데이터</param>
/// <returns>존재 여부</returns>
bool HashTable_OpenAddressing::Contains(int data)
{
int idx{ GetHashIndex(data) };
return m_table[idx] == data;
}
/// <summary>
/// 해시 테이블의 모든 데이터를 지운다.
/// </summary>
void HashTable_OpenAddressing::Clear()
{
m_table.clear();
}
/// <summary>
/// 해시 테이블의 크기를 조정하고 데이터를 다시 해싱한다.
/// </summary>
void HashTable_OpenAddressing::Resize()
{
vector<int> oldData;
oldData.reserve(Size());
for (int i = 0; i < Size(); i++)
{
if (m_table[i] != Empty && m_table[i] != Deleted)
{
oldData.emplace_back(m_table[i]);
}
}
HashTable::Resize();
ResetTable();
int oldDataCount = static_cast<int>(oldData.size());
for (int i = 0; i < oldDataCount; i++)
{
Add(oldData[i]);
}
m_usedCount = oldDataCount;
}
/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void HashTable_OpenAddressing::PrintHashTable(string hashTableName)
{
HashTable::PrintHashTable(hashTableName);
for (int i = 0, total = Size(); i < total; i++)
{
std::cout << " Index " << i << " : ";
if (m_table[i] == Deleted)
{
std::cout << "Deleted";
}
else if (m_table[i] == Empty)
{
std::cout << "Empty";
}
else
{
std::cout << m_table[i];
}
std::cout << '\n';
}
std::cout << '\n';
}
#pragma endregion
#pragma region Private Functions
/// <summary>
/// 주어진 인덱스에 값이 존재하여 충돌이 발생하는지 여부를 반환한다.
/// </summary>
/// <param name="idx">확인할 인덱스</param>
/// <returns>충돌 여부</returns>
bool HashTable_OpenAddressing::IsCollided(int idx)
{
return m_table[idx] != Empty;
}
/// <summary>
/// 리사이즈가 필요한지 여부를 반환한다.
/// </summary>
/// <returns>리사이즈 필요 여부</returns>
bool HashTable_OpenAddressing::NeedToResize()
{
return m_usedCount > LimitCount();
}
/// <summary>
/// 테이블을 초기화한다.
/// </summary>
void HashTable_OpenAddressing::ResetTable()
{
m_table.clear();
for (int i = 0, total = Size(); i < total; i++)
{
m_table.push_back(Empty);
}
}
#pragma endregion
#pragma region Protected Functions
/// <summary>
/// 개방 주소 방법을 통해 적절한 인덱스를 반환한다.
/// </summary>
/// <param name="data">인덱스를 찾을 데이터</param>
/// <returns>해쉬 테이블에서의 인덱스</returns>
int HashTable_OpenAddressing::GetHashIndex(int data)
{
int idx{ HashTable::GetHashIndex(data) };
if (IsCollided(idx))
{
idx = GetProperHashIndex(idx, data);
}
return idx;
}
#pragma endregion
- 선형 조사를 이용한 해시 테이블 구현
충돌 처리 중 선형 조사를 이용하는 해시 테이블을 구현한다.
HashTable_OpenAddressing_LinearProbing.h
#pragma once
#include "../Common.h"
#include "HashTable_OpenAddressing.h"
#include <vector>
#include <list>
using std::vector;
using std::list;
/// <summary>
/// 충돌 해결 방법 중 체이닝을 구현한 해시 테이블
/// </summary>
class HashTable_OpenAddressing_LinearProbing : public HashTable_OpenAddressing
{
public:
HashTable_OpenAddressing_LinearProbing(HashFunction hashFunction = HashFunction::Division) : HashTable_OpenAddressing(hashFunction) {};
virtual void PrintHashTable(string hashTableName = "HashTable_OpenAddressing_LinearProbing") override;
protected:
virtual int GetProperHashIndex(int idx, int data) override;
};
HashTable_OpenAddressing_LinearProbing.cpp
#include "HashTable_OpenAddressing_LinearProbing.h"
#pragma region Public Functions
/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void HashTable_OpenAddressing_LinearProbing::PrintHashTable(string hashTableName)
{
HashTable_OpenAddressing::PrintHashTable(hashTableName);
}
#pragma endregion
#pragma region Protected Functions
/// <summary>
/// 알고리즘에 맞게 충돌을 피한 인덱스를 반환한다.
/// </summary>
/// <param name="idx">충돌한 인덱스</param>
/// <param name="data">추가/검색하려는 데이터</param>
/// <returns>해당 데이터의 인덱스 위치</returns>
int HashTable_OpenAddressing_LinearProbing::GetProperHashIndex(int idx, int data)
{
int properIdx{ idx };
// 충돌이 난 위치에서부터 빈 공간을 검색한다.
for (int i = 0; i < Size(); i++)
{
properIdx = (idx + i) % Size();
if (m_table[properIdx] == Empty || m_table[properIdx] == data)
{
break;
}
}
return properIdx;
}
#pragma endregion
실행결과
------------------------------------------
- Class Name : HashTable_OpenAddressing_LinearProbing
- HashFuncion : Division
------------------------------------------
Index 0 : Empty
Index 1 : 1
Index 2 : 2
Index 3 : 3
Index 4 : 71
Index 5 : 5
Index 6 : Empty
Index 7 : 7
Index 8 : Empty
Index 9 : 9
Index 10 : Empty
Index 11 : 11
Index 12 : 12
Index 13 : 81
Index 14 : 14
Index 15 : Empty
Index 16 : 16
Index 17 : Empty
Index 18 : 18
Index 19 : Empty
Index 20 : 20
Index 21 : 21
Index 22 : Empty
Index 23 : 23
Index 24 : 91
Index 25 : 25
Index 26 : Empty
Index 27 : 27
Index 28 : Empty
Index 29 : 29
Index 30 : Empty
Index 31 : 31
Index 32 : 32
Index 33 : Empty
Index 34 : 34
Index 35 : Empty
Index 36 : 36
Index 37 : Empty
Index 38 : 38
Index 39 : Empty
Index 40 : 40
Index 41 : 41
Index 42 : Empty
Index 43 : 43
Index 44 : Empty
Index 45 : 45
Index 46 : Empty
Index 47 : 47
Index 48 : Empty
Index 49 : 49
Index 50 : Empty
Index 51 : 51
Index 52 : Empty
Index 53 : Empty
Index 54 : Empty
Index 55 : Empty
Index 56 : Empty
Index 57 : Empty
Index 58 : Empty
Index 59 : Empty
Index 60 : Empty
Index 61 : 61
Index 62 : Empty
Index 63 : Empty
Index 64 : Empty
Index 65 : Empty
Index 66 : Empty
Index 67 : Empty
------------------------------------------
- Class Name : HashTable_OpenAddressing_LinearProbing
- HashFuncion : Division
------------------------------------------
Index 0 : Empty
Index 1 : 1
Index 2 : 2
Index 3 : 3
Index 4 : 71
Index 5 : 5
Index 6 : Empty
Index 7 : 7
Index 8 : Empty
Index 9 : 9
Index 10 : Empty
Index 11 : 11
Index 12 : 12
Index 13 : 81
Index 14 : 14
Index 15 : Empty
Index 16 : Deleted
Index 17 : Empty
Index 18 : 18
Index 19 : Empty
Index 20 : 20
Index 21 : 21
Index 22 : Empty
Index 23 : 23
Index 24 : 91
Index 25 : 25
Index 26 : Empty
Index 27 : Deleted
Index 28 : Empty
Index 29 : 29
Index 30 : Empty
Index 31 : 31
Index 32 : 32
Index 33 : Empty
Index 34 : 34
Index 35 : Empty
Index 36 : 36
Index 37 : Empty
Index 38 : 38
Index 39 : Empty
Index 40 : 40
Index 41 : 41
Index 42 : Empty
Index 43 : 43
Index 44 : Empty
Index 45 : 45
Index 46 : Empty
Index 47 : Deleted
Index 48 : Empty
Index 49 : 49
Index 50 : Empty
Index 51 : 51
Index 52 : Empty
Index 53 : Empty
Index 54 : Empty
Index 55 : Empty
Index 56 : Empty
Index 57 : Empty
Index 58 : Empty
Index 59 : Empty
Index 60 : Empty
Index 61 : 61
Index 62 : Empty
Index 63 : Empty
Index 64 : Empty
Index 65 : Empty
Index 66 : Empty
Index 67 : Empty
- 이차원 조사를 이용한 해시 테이블 구현
충돌 처리 중 이차원 조사를 이용하는 해시 테이블을 구현한다.
HashTable_OpenAddressing_QuadraticProbing.h
#pragma once
#include "../Common.h"
#include "HashTable_OpenAddressing.h"
#include <vector>
#include <list>
using std::vector;
using std::list;
/// <summary>
/// 충돌 해결 방법 중 체이닝을 구현한 해시 테이블
/// </summary>
class HashTable_OpenAddressing_QuadraticProbing : public HashTable_OpenAddressing
{
public:
HashTable_OpenAddressing_QuadraticProbing(HashFunction hashFunction = HashFunction::Division) : HashTable_OpenAddressing(hashFunction) {};
virtual void PrintHashTable(string hashTableName = "HashTable_OpenAddressing_QuadraticProbing") override;
protected:
virtual int GetProperHashIndex(int idx, int data) override;
};
HashTable_OpenAddressing_QuadraticProbing.cpp
#include "HashTable_OpenAddressing_QuadraticProbing.h"
#pragma region Public Functions
/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void HashTable_OpenAddressing_QuadraticProbing::PrintHashTable(string hashTableName)
{
HashTable_OpenAddressing::PrintHashTable(hashTableName);
}
#pragma endregion
#pragma region Protected Functions
/// <summary>
/// 알고리즘에 맞게 충돌을 피한 인덱스를 반환한다.
/// </summary>
/// <param name="idx">충돌한 인덱스</param>
/// <param name="data">추가/검색하려는 데이터</param>
/// <returns>해당 데이터의 인덱스 위치</returns>
int HashTable_OpenAddressing_QuadraticProbing::GetProperHashIndex(int idx, int data)
{
int properIdx{ idx };
for (int i = 1; m_table[properIdx] != Empty && m_table[properIdx] != data; i++)
{
properIdx = (idx + (i * i)) % Size();
}
return properIdx;
}
#pragma endregion
실행결과
------------------------------------------
- Class Name : HashTable_OpenAddressing_QuadraticProbing
- HashFuncion : Division
------------------------------------------
Index 0 : Empty
Index 1 : 1
Index 2 : 2
Index 3 : 3
Index 4 : 71
Index 5 : 5
Index 6 : Empty
Index 7 : 7
Index 8 : Empty
Index 9 : 9
Index 10 : Empty
Index 11 : 11
Index 12 : 12
Index 13 : 81
Index 14 : 14
Index 15 : Empty
Index 16 : 16
Index 17 : Empty
Index 18 : 18
Index 19 : Empty
Index 20 : 20
Index 21 : 21
Index 22 : Empty
Index 23 : 23
Index 24 : 91
Index 25 : 25
Index 26 : Empty
Index 27 : 27
Index 28 : Empty
Index 29 : 29
Index 30 : Empty
Index 31 : 31
Index 32 : 32
Index 33 : Empty
Index 34 : 34
Index 35 : Empty
Index 36 : 36
Index 37 : Empty
Index 38 : 38
Index 39 : Empty
Index 40 : 40
Index 41 : 41
Index 42 : Empty
Index 43 : 43
Index 44 : Empty
Index 45 : 45
Index 46 : Empty
Index 47 : 47
Index 48 : Empty
Index 49 : 49
Index 50 : Empty
Index 51 : 51
Index 52 : Empty
Index 53 : Empty
Index 54 : Empty
Index 55 : Empty
Index 56 : Empty
Index 57 : Empty
Index 58 : Empty
Index 59 : Empty
Index 60 : Empty
Index 61 : 61
Index 62 : Empty
Index 63 : Empty
Index 64 : Empty
Index 65 : Empty
Index 66 : Empty
Index 67 : Empty
------------------------------------------
- Class Name : HashTable_OpenAddressing_QuadraticProbing
- HashFuncion : Division
------------------------------------------
Index 0 : Empty
Index 1 : 1
Index 2 : 2
Index 3 : 3
Index 4 : 71
Index 5 : 5
Index 6 : Empty
Index 7 : 7
Index 8 : Empty
Index 9 : 9
Index 10 : Empty
Index 11 : 11
Index 12 : 12
Index 13 : 81
Index 14 : 14
Index 15 : Empty
Index 16 : Deleted
Index 17 : Empty
Index 18 : 18
Index 19 : Empty
Index 20 : 20
Index 21 : 21
Index 22 : Empty
Index 23 : 23
Index 24 : 91
Index 25 : 25
Index 26 : Empty
Index 27 : Deleted
Index 28 : Empty
Index 29 : 29
Index 30 : Empty
Index 31 : 31
Index 32 : 32
Index 33 : Empty
Index 34 : 34
Index 35 : Empty
Index 36 : 36
Index 37 : Empty
Index 38 : 38
Index 39 : Empty
Index 40 : 40
Index 41 : 41
Index 42 : Empty
Index 43 : 43
Index 44 : Empty
Index 45 : 45
Index 46 : Empty
Index 47 : Deleted
Index 48 : Empty
Index 49 : 49
Index 50 : Empty
Index 51 : 51
Index 52 : Empty
Index 53 : Empty
Index 54 : Empty
Index 55 : Empty
Index 56 : Empty
Index 57 : Empty
Index 58 : Empty
Index 59 : Empty
Index 60 : Empty
Index 61 : 61
Index 62 : Empty
Index 63 : Empty
Index 64 : Empty
Index 65 : Empty
Index 66 : Empty
Index 67 : Empty
- 더블 해싱을 이용한 해시 테이블 구현
충돌 처리 중 더블 해싱을 이용하는 해시 테이블을 구현한다.
HashTable_OpenAddressing_DoubleHashing.h
#pragma once
#include "../Common.h"
#include "HashTable_OpenAddressing.h"
#include <vector>
#include <list>
using std::vector;
using std::list;
/// <summary>
/// 충돌 해결 방법 중 체이닝을 구현한 해시 테이블
/// </summary>
class HashTable_OpenAddressing_DoubleHashing : public HashTable_OpenAddressing
{
public:
HashTable_OpenAddressing_DoubleHashing(HashFunction hashFunction = HashFunction::Division) : HashTable_OpenAddressing(hashFunction) {};
virtual void PrintHashTable(string hashTableName = "HashTable_OpenAddressing_DoubleHashing") override;
protected:
virtual int GetProperHashIndex(int idx, int data) override;
};
HashTable_OpenAddressing_DoubleHashing.cpp
#include "HashTable_OpenAddressing_DoubleHashing.h"
#pragma region Public Functions
/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void HashTable_OpenAddressing_DoubleHashing::PrintHashTable(string hashTableName)
{
HashTable_OpenAddressing::PrintHashTable(hashTableName);
}
#pragma endregion
#pragma region Protected Functions
/// <summary>
/// 알고리즘에 맞게 충돌을 피한 인덱스를 반환한다.
/// </summary>
/// <param name="idx">충돌한 인덱스</param>
/// <param name="data">추가/검색하려는 데이터</param>
/// <returns>해당 데이터의 인덱스 위치</returns>
int HashTable_OpenAddressing_DoubleHashing::GetProperHashIndex(int idx, int data)
{
int jumpValue{ HashTable::GetHashIndex(data, HashFunction::Multiplication) };
if (CurrentHashFunction() == HashFunction::Multiplication)
{
jumpValue = HashTable::GetHashIndex(data, HashFunction::Division);
}
int properIdx{ idx };
for (int i = 1; m_table[properIdx] != Empty && m_table[properIdx] != data; i++)
{
properIdx = (idx + (i * jumpValue)) % Size();
}
return properIdx;
}
#pragma endregion
실행결과
------------------------------------------
- Class Name : HashTable_OpenAddressing_DoubleHashing
- HashFuncion : Division
------------------------------------------
Index 0 : Empty
Index 1 : 1
Index 2 : 2
Index 3 : 3
Index 4 : Empty
Index 5 : 5
Index 6 : Empty
Index 7 : 7
Index 8 : Empty
Index 9 : 9
Index 10 : Empty
Index 11 : 11
Index 12 : 12
Index 13 : 81
Index 14 : 14
Index 15 : Empty
Index 16 : 16
Index 17 : Empty
Index 18 : 18
Index 19 : Empty
Index 20 : 20
Index 21 : 21
Index 22 : Empty
Index 23 : 23
Index 24 : Empty
Index 25 : 25
Index 26 : Empty
Index 27 : 27
Index 28 : Empty
Index 29 : 29
Index 30 : Empty
Index 31 : 31
Index 32 : 32
Index 33 : Empty
Index 34 : 34
Index 35 : Empty
Index 36 : 36
Index 37 : Empty
Index 38 : 38
Index 39 : 91
Index 40 : 40
Index 41 : 41
Index 42 : Empty
Index 43 : 43
Index 44 : Empty
Index 45 : 45
Index 46 : Empty
Index 47 : 47
Index 48 : Empty
Index 49 : 49
Index 50 : Empty
Index 51 : 51
Index 52 : Empty
Index 53 : Empty
Index 54 : Empty
Index 55 : Empty
Index 56 : Empty
Index 57 : Empty
Index 58 : Empty
Index 59 : Empty
Index 60 : Empty
Index 61 : 61
Index 62 : 71
Index 63 : Empty
Index 64 : Empty
Index 65 : Empty
Index 66 : Empty
Index 67 : Empty
------------------------------------------
- Class Name : HashTable_OpenAddressing_DoubleHashing
- HashFuncion : Division
------------------------------------------
Index 0 : Empty
Index 1 : 1
Index 2 : 2
Index 3 : 3
Index 4 : Empty
Index 5 : 5
Index 6 : Empty
Index 7 : 7
Index 8 : Empty
Index 9 : 9
Index 10 : Empty
Index 11 : 11
Index 12 : 12
Index 13 : 81
Index 14 : 14
Index 15 : Empty
Index 16 : Deleted
Index 17 : Empty
Index 18 : 18
Index 19 : Empty
Index 20 : 20
Index 21 : 21
Index 22 : Empty
Index 23 : 23
Index 24 : Empty
Index 25 : 25
Index 26 : Empty
Index 27 : Deleted
Index 28 : Empty
Index 29 : 29
Index 30 : Empty
Index 31 : 31
Index 32 : 32
Index 33 : Empty
Index 34 : 34
Index 35 : Empty
Index 36 : 36
Index 37 : Empty
Index 38 : 38
Index 39 : 91
Index 40 : 40
Index 41 : 41
Index 42 : Empty
Index 43 : 43
Index 44 : Empty
Index 45 : 45
Index 46 : Empty
Index 47 : Deleted
Index 48 : Empty
Index 49 : 49
Index 50 : Empty
Index 51 : 51
Index 52 : Empty
Index 53 : Empty
Index 54 : Empty
Index 55 : Empty
Index 56 : Empty
Index 57 : Empty
Index 58 : Empty
Index 59 : Empty
Index 60 : Empty
Index 61 : 61
Index 62 : 71
Index 63 : Empty
Index 64 : Empty
Index 65 : Empty
Index 66 : Empty
Index 67 : Empty
NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)
GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소
알고리즘 학습 및 예제 코드 작성을 위한 저장소. Contribute to NadanKim/Algorithm development by creating an account on GitHub.
github.com