알고리즘...98

해시 테이블 이차원 조사 구현

기존 구현에 추가로 충돌 해결용 함수만 구현한다.

 

이번에는 i를 순서대로 더하는 대신 i의 제곱값을 더하는 방식으로 빠르게 군집을 벗어나도록 만든다.

int HashTable_OpenAddressing_QuadraticProbing::GetProperHashIndex(int idx, int data)
{
	int properIdx{ idx };
	
	int i{ 1 };
	while (m_table[properIdx] != Empty && m_table[properIdx] != data)
	{
		properIdx = (idx + (i * i)) % Size();
		i++;
	}

	return properIdx;
}

 

main.cpp

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

int main()
{
	HashTable_OpenAddressing_QuadraticProbing 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_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

 

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

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