hash2

#include<iostream>
#include <chrono>
#include <thread>
#include <random>
#include <algorithm>
using namespace std;

int losowa_liczba(int min = 0, int max = std::numeric_limits<int>::max())
{
	static std::default_random_engine gen(std::random_device{}());
	static std::uniform_int_distribution<int> dist;
	return dist(gen, std::uniform_int_distribution<int>::param_type{ min, max });
}
int re = 0;
int rozmiar = 10000;
const int iloscLosowych = 1000000;

///*
int h(int x, int i, int T)
{

	int a;
	a = (x % T + i) % T;
	return a;

}
//*/
/*
int h(int x, int i, int T)
{

int a;
a = (((x%T) + i * ((((x / T) % (T / 2)) * 2) + 1))) % T;
return a;
}
*/
double wywF = 0;
bool hash_al_wstaw(int tab[], int x, int m)
{

	int k;
	for (int i = 0; i < m; i++)
	{
		k = h(x, i, m);

		wywF++;

		if (tab[k] == -1)
		{
			tab[k] = x;
			return true;
		}
	}
	return false;

}
double wywFsz = 0;
bool hash_al_szukaj(int tab[], int x, int m)
{
	int k;
	for (int i = 0; i < m; i++)
	{
		k = h(x, i, m);
		wywFsz++;

		if (tab[k] == x)
			return true;

		if (tab[k] == -1)
			return false;
	}
	return false;
}

void rest(int* &tab)
{
	int *tab3 = new int[2 * rozmiar];
	for (int i = 0;i < 2 * rozmiar;i++)
		tab3[i] = -1;
	for (int j = 0;j < rozmiar;j++)
	{
		if (tab[j] != -1)
			hash_al_wstaw(tab3, tab[j], 2 * rozmiar);
	}
	delete[] tab;
	tab = tab3;
	rozmiar=2*rozmiar;
	re++;
}


int main()
{
	std::default_random_engine gen(std::random_device{}());


	const int probka = 10000;
	int dopelnij = 90000;
	double czasWstaw = 0;
	double czasWyszuk = 0;




	int *tab = new int[rozmiar];
	for (int i = 0; i < rozmiar; i++)
		tab[i] = -1;


	int *tab2 = new int[iloscLosowych];
	for (int i = 0; i < iloscLosowych; i++)
		tab2[i] = losowa_liczba();



	for (int j = 0; j <100; j++)
	{


        /*
		for (int i = 0; i < dopelnij; i++)
		{
			if (j == 0)
				break;
			hash_al_wstaw(tab, losowa_liczba(), rozmiar);
		}
		*/

		wywF = 0;
		wywFsz = 0;
		czasWstaw = 0;
		czasWyszuk = 0;

		auto start = std::chrono::high_resolution_clock::now();

		for (int i = 0; i < probka; i++)
		{
			hash_al_wstaw(tab, tab2[i + j * probka], rozmiar);
		}

		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double, std::micro> duration = end - start;
		czasWstaw = duration.count();


		shuffle(tab2, tab2 + (j + 1)*probka, gen);

		start = std::chrono::high_resolution_clock::now();

		for (int i = 0; i < probka; i++)
		{
			if (!hash_al_szukaj(tab, tab2[i], rozmiar))
				cout << "brak elementu";
		}

		end = std::chrono::high_resolution_clock::now();
		duration = end - start;
		czasWyszuk = duration.count();



		cout << "Dla " << j*(rozmiar / iloscLosowych) << "%" << endl;
		cerr << "Srednio uplynelo: " << czasWstaw / probka << "s\n";
		cerr << "Srednia ilosc wywolan: " << wywF / probka << "\n";
		cerr << "Sredni czas wyszukiwania: " << czasWyszuk / probka << "s\n";
		cerr << "Srednia ilosc wywolan funkcji szukajacej: " << wywFsz / probka << "\n\n";
		cout<<"Liczba restrukturyzacji: "<<  re << "\n\n";
	}

	delete[] tab2;
	delete[] tab;

	system("pause");
	return 0;
}