program

#include <chrono>
#include <thread>
#include <random>
#include <iostream>
#include <algorithm>

using namespace std;
double wywolan = 0;  //wstawianie
double wywolan1 = 0; //wyszukaj
double wywolanres = 0; //restrukuryzacja
int n = 10000;

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


struct tabhaszujaca {
    int* tab;
    int size;
    int writein; //wpisane
    int sizeall; //rozmiar całej tablicy
};




bool hash_al_wstaw(int x, tabhaszujaca& tablica)
{
    if ((double)tablica.writein / tablica.size > 0.6)         //   <0.6 ; 0,7 ; 0;8 ; 0.9>
    {
        wywolanres++; // ilośc wywołań restrukturyzacji
        tabhaszujaca nowa;
        nowa.size = tablica.size * 2;
        nowa.tab = new int[nowa.size];
        nowa.writein = 0; //alokacja nowych



        for (int i = 0; i < nowa.size; i++)
            nowa.tab[i] = -1;
        for (int j = 0; j < tablica.size; j++)
        {
            if (tablica.tab[j] != -1)
                hash_al_wstaw(tablica.tab[j], nowa);
        }



        delete[] tablica.tab; //zwolnienie pam
        tablica.size = nowa.size; //all
        tablica.tab = nowa.tab;
        tablica.writein = nowa.writein;
    }




    int k = 0;
    for (int i = 0; i<tablica.size; i++)
    {
        wywolan++;
        int N = tablica.size;


        int k = ((x%N)+i) % N;                           //Liniowe



        /*int h1 = x%N;
        int h2 = (((x / N) % (N / 2)) * 2) + 1;         //Podwójne
        k = (h1 + i*h2) % N;*/



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

///////////////////////////////////////////////



bool hash_al_szukaj(int x, tabhaszujaca& tablica)
{
    int k = 0;
    int N = tablica.size;


    for (int i = 0; i <N; i++)
    {
        wywolan1++;


        int k = ((x%N)+i) % N;                           //Liniowe



        /*int h1 = x%N;
        int h2 = (((x / N) % (N / 2)) * 2) + 1;         //Podwójne
        k = (h1 + i*h2) % N;*/



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



///////////////////-main-///////////////////////////////



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


    tab_miesz.size = 10000;
    tab_miesz.tab = new int[tab_miesz.size];
    tab_miesz.writein = 0;
    tab_miesz.sizeall = 10000;
    int *tab_random = new int[tab_miesz.size * 100];




    for (int i = 0; i < tab_miesz.size; i++)
    {
        tab_miesz.tab[i] = -1;
    }
    for (int j = 0; j < (tab_miesz.size * 100); j++)
    {
        tab_random[j] = losowa_liczba();
    }




    for (int k = 0; k < 100; k++)
    {
        wywolan1 = wywolan = 0;
        auto start = std::chrono::high_resolution_clock::now();


        for (int i = 0; i <tab_miesz.sizeall; i++)
        {
            hash_al_wstaw(tab_random[i + k*tab_miesz.sizeall], tab_miesz);
        }

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








        /*cerr << endl << " Dla " << k << "%" << "             Wstawianie " << (double)duration.count() / tab_miesz.sizeall << "us"
            << "       Srednia liczba wywolan: " << wywolan / tab_miesz.sizeall << endl;;*/



        ////////////////////

        if (k > 1)
        {
            shuffle(tab_random, tab_random + (1 + k)*tab_miesz.sizeall, gen);
        }

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

        for (int i = 0; i < tab_miesz.sizeall; i++)
        {
            hash_al_szukaj(tab_random[i], tab_miesz);
        }


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



        cerr << endl << " Dla      " << k << "     %" << "     Wstawianie              " << (double)duration.count() / tab_miesz.sizeall << "              us"
            << "       Srednia liczba wywolan:               " << wywolan / tab_miesz.sizeall << "                      Szukanie                            " << (double)duration.count() / tab_miesz.sizeall << "               us"
            << "       Srednia liczba wywolan:               " << wywolan1 / tab_miesz.sizeall
            << "                                 Restrukturyzacje:             " << wywolanres;


        /*cerr << " Dla " << k << "%" << "             Szukanie " << (double)duration.count() / tab_miesz.sizeall << "us"
            << "       Srednia liczba wywolan: " << wywolan1 / tab_miesz.sizeall << endl << endl << endl
            << "Restrukturyzacje: " << wywolanres << endl << "----------------------------------------------------------------" << endl << endl << endl;
            */

    }


    ////////////////////////////////////////

    system("pause");
    return 0;
}