알고리즘...97

선형 조사 알고리즘 구현

먼저, 개방 주소 방법에서는 개수가 무한히 증가될 수 없으므로 일정 수준보다 값이 많이 들어가면 개수를 늘리는 처리를 추가한다.

int LimitCount() { return Size() * 3 / 4; }

bool HashTable_OpenAddressing::NeedToResize()
{
	return m_usedCount >= LimitCount();
}

 

이후 테이블의 Resize를 처리하는 함수를 추가한다.

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;
}

 

충돌이 난 인덱스를 넣어서 적절하게 비어있는 위치의 인덱스를 반환하는 함수를 만든다.

int HashTable_OpenAddressing_LinearProbing::GetProperHashIndex(int idx, int data)
{
	int properIdx{ -1 };
	// 충돌이 난 다음 위치에서 부터 빈 공간을 검색한다.
	for (int i = idx + 1; i < Size(); i++)
	{
		if (m_table[i] == Empty || m_table[i] == data)
		{
			properIdx = i;
			break;
		}
	}

	// 끝까지 갔는데 빈 공간이 없으면 맨 위에서부터 탐색한다.
	if (properIdx == -1)
	{
		for (int i = 0; i < idx; i++)
		{
			if (m_table[i] == Empty || m_table[i] == data)
			{
				properIdx = i;
				break;
			}
		}
	}

	return properIdx;
}

 

main.cpp

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

int main()
{
	HashTable_OpenAddressing_LinearProbing 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();
}

 

실행결과

------------------------------------------
- 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

 

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

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