일지
알고리즘...96
niamdank
2021. 12. 30. 18:42
해시 테이블 충돌 처리 구현 진행
개방주소 방법 구현을 위한 베이스 클래스 제작
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) : HashTable(hashFunction) {}
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;
protected:
virtual int GetHashIndex(int data);
virtual int GetProperHashIndex(int idx, int data) = 0;
private:
vector<int> m_table;
static const int Deleted_Data = -INT_MAX;
};
HashTable_OpenAddressing.cpp
#include "HashTable_OpenAddressing.h"
#pragma region Public Functions
/// <summary>
/// 데이터를 해시 테이블에 추가한다.
/// </summary>
/// <param name="data">추가할 데이터</param>
void HashTable_OpenAddressing::Add(int data)
{
if (Contains(data))
{
return;
}
int idx{ GetHashIndex(data) };
m_table[idx] = data;
}
/// <summary>
/// 데이터를 해시 테이블에서 제거한다.
/// </summary>
/// <param name="data">제거할 데이터</param>
void HashTable_OpenAddressing::Remove(int data)
{
if (!Contains(data))
{
return;
}
int idx{ GetHashIndex(data) };
m_table[idx] = Deleted_Data;
}
/// <summary>
/// 주어진 값이 해시 테이블에 존재하는지 여부를 반환한다.
/// </summary>
/// <param name="data">찾을 데이터</param>
/// <returns>존재 여부</returns>
bool HashTable_OpenAddressing::Contains(int data)
{
int idx{ GetHashIndex(data) };
return m_table[idx] == data || m_table[idx] == Deleted_Data;
}
/// <summary>
/// 해시 테이블의 모든 데이터를 지운다.
/// </summary>
void HashTable_OpenAddressing::Clear()
{
m_table.clear();
}
/// <summary>
/// 해시 테이블의 현 상태를 출력한다.
/// </summary>
void HashTable_OpenAddressing::PrintHashTable()
{
HashTable::PrintHashTable();
for (int i = 0, total = Size(); i < total; i++)
{
std::cout << " Index " << i << " : ";
if (m_table.size() > 0)
{
auto d = m_table.cbegin();
while (true)
{
if (*d == Deleted_Data)
{
std::cout << "Deleted";
}
else
{
std::cout << *d;
}
d++;
if (d == m_table.cend())
{
break;
}
std::cout << " - ";
}
}
else
{
std::cout << "EMPTY";
}
std::cout << '\n';
}
std::cout << '\n';
}
#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 (Contains(data))
{
idx = GetProperHashIndex(idx, data);
}
return idx;
}
#pragma endregion
NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)
GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소
알고리즘 학습 및 예제 코드 작성을 위한 저장소. Contribute to NadanKim/Algorithm development by creating an account on GitHub.
github.com