알고리즘...99

해시 테이블 충돌 해결 더블 해싱 구현

충돌 해결 방법 중 개방주소 방법의 더블 해싱을 구현한다.

 

다른 부분은 상위 클래스에서 구현이 되어있으므로 충돌 해결 방법만 추가로 구현한다.

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

 

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

 

실행결과

------------------------------------------
- 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: 알고리즘 학습 및 예제 코드 작성을 위한 저장소