-
해시 테이블 구현 및 테스트프로그래밍 기초/알고리즘 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 : EmptyNadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)
GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소
알고리즘 학습 및 예제 코드 작성을 위한 저장소. Contribute to NadanKim/Algorithm development by creating an account on GitHub.
github.com