Hash

#include <iostream>
#include <algorithm>
#include <new>

#include "Profiler.h"

Profiler profiler("HashTables");
using namespace std;
	/*
		typedef struct Node
		{
			int value;
			struct Node* next;
		};

		void Push(Node* head, int value)
		{
			Node* current = head;
			while (current->next != NULL)
			{
				current = current->next;
			}
			current->next = (Node*)malloc(sizeof(Node));
			current->next->value = value;
			current->next->next = NULL;
		}

		int Search(Node* Table[], int key, int value)
		{
			Node* temp = Table[value / key];
			int k = 1;
			while (temp->value != value)
			{
				temp = temp->next;
			}
			return k;
		}

		void Insert(Node* Table[], int key, int value)
		{
			if (Table[value / key] != NULL)
			{
				Push(Table[value / key], value);
			}
			else
			{
				Table[value / key]->value = value;
				Table[value / key]->next = NULL;
			}
		}
	*/

void InsertArr(int Table[], int key, int value)
{
	int temp = value % key;
	if (Table[temp] == 0)
	{
		Table[temp] = value;
	}
	else
	{
		int i = 1;
		while (Table[(value + i*i) % key] != 0)
		{
			i++;
		}
		Table[(value + i * i) % key] = value;
	}
}
int SearchArr(int Table[], int key, int value, int* counter , int* max)
{
	int i = 0;
	if(Table[value % key] != value)
	{
		i++;
		while (Table[(value + i * i) % key] != value && (value + i * i) % key != value % key)
		{
			i++;
		}
	}
	if (i > *max)
	{
		*max = i;
	}
	counter = counter + i;
	if ((value + i * i) % key == value % key && i != 0)
		return -1;
	return (value + i * i) % key;
}

int main()
{
	int counterGasite = 0;
	int counterNegasite = 0;
	int max = 0;


	//Demo
	{
		//int hashTable[10] = { 0 };
		//int X[10] = { 1,2,3,4,5,6,7,8,10,15 };
		//for (int i = 0; i < 10; i++)
		//{
		//	InsertArr(hashTable, 10, X[i]);
		//}
		//cout << SearchArr(hashTable, 10, 8, &counterGasite, &max) << '\n';
		//cout << SearchArr(hashTable, 10, 15, &counterGasite, &max) << '\n';
		//cout << SearchArr(hashTable, 10, 9, &counterGasite, &max) << '\n';
		//cout << SearchArr(hashTable, 10, 16, &counterGasite, &max) << '\n';
	}

	int* X = new int[10000];
	int* hashTable = new int[10000];

	// 0.99
	{
		FillRandomArray(X, 9973, 10, 10000, true);
		for (int i = 0; i < 9973; i++)
		{
			InsertArr(hashTable, 9973, X[i]);
		}
		for (int i = 1; i <= 1500; i++)
		{
			SearchArr(hashTable, 10000, X[i], &counterGasite, &max);
		}
		for(int i = 10000 ; i <= 11500 ; i++)
		{
			SearchArr(hashTable, 10000, i, &counterNegasite, &max);
		}
		cout << counterGasite << ' ' << counterNegasite;
		cout << '\n' << max;
	}

	//0.95
	{
		//FillRandomArray(X, 9497, 10, 10000, true);
		//for (int i = 0; i < 9497; i++)
		//{
		//	InsertArr(hashTable, 9497, X[i]);
		//}
		//for (int i = 1; i <= 1500; i++)
		//{
		//	SearchArr(hashTable, 10000, X[i], &counterGasite, &max);
		//}
		//for (int i = 10000; i <= 11500; i++)
		//{
		//	SearchArr(hashTable, 10000, i, &counterNegasite, &max);
		//}
		//cout << counterGasite << ' ' << counterNegasite;
		//cout << '\n' << max;
	}

	//0.9
	{
		//FillRandomArray(X, 8999, 10, 10000, true);
		//for (int i = 0; i < 8999; i++)
		//{
		//	InsertArr(hashTable, 8999, X[i]);
		//}
		//for (int i = 1; i <= 1500; i++)
		//{
		//	SearchArr(hashTable, 10000, X[i], &counterGasite, &max);
		//}
		//for (int i = 10000; i <= 11500; i++)
		//{
		//	SearchArr(hashTable, 10000, i, &counterNegasite, &max);
		//}
		//cout << counterGasite << ' ' << counterNegasite;
		//cout << '\n' << max;
	}

	//0.85
	{
		//FillRandomArray(X, 8501, 10, 10000, true);
		//for (int i = 0; i < 8501; i++)
		//{
		//	InsertArr(hashTable, 8501, X[i]);
		//}
		//for (int i = 1; i <= 1500; i++)
		//{
		//	SearchArr(hashTable, 10000, X[i], &counterGasite, &max);
		//}
		//for (int i = 10000; i <= 11500; i++)
		//{
		//	SearchArr(hashTable, 10000, i, &counterNegasite, &max);
		//}
		//cout << counterGasite << ' ' << counterNegasite;
		//cout << '\n' << max;
	}

	//0.8
	{
		//FillRandomArray(X, 7993, 10, 10000, true);
		//for (int i = 0; i < 7993; i++)
		//{
		//	InsertArr(hashTable, 7993, X[i]);
		//}
		//for (int i = 1; i <= 1500; i++)
		//{
		//	SearchArr(hashTable, 10000, X[i], &counterGasite, &max);
		//}
		//for (int i = 10000; i <= 11500; i++)
		//{
		//	SearchArr(hashTable, 10000, i, &counterNegasite, &max);
		//}
		//cout << counterGasite << ' ' << counterNegasite;
		//cout << '\n' << max;
	}

}