AISD_hashmap1

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

int h(int x, int i, int T)
{
  if (i == 0)
    return x % T;

  return (h(x, 0, T) + i) % T;
}


//~ int h1(int x, int T)
//~ {
  //~ return x % T;
//~ }

//~ int h2(int x, int T)
//~ {
  //~ return (((x/T) % (T/2)) * 2) + 1;
//~ }

//~ int h(int x, int i, int T)
//~ {
  //~ return (h1(x, T) + i*h2(x, T)) % T;
//~ }

bool hash_al_wstaw(int* A, int x, int T, int &wywolanie)
{
  for (int i = 0; i < T; i++)
  {
    wywolanie++;
    int k = h(x, i, T);
    if (A[k] == -1)
    {
      A[k] = x;
      return true;
    }
  }

  return false;
}

bool hash_al_szukaj(int *A, int x, int T, int &wywolanie)
{
  for(int i = 0; i < T; i++)
  {
    wywolanie++;
    int k = h(x, i, T);
    if (A[k] == x)
      return true;
    else if (A[k] == -1)
      return false;
  }

  return false;
}

int* hash_al_przep(int *A, int &T, int &wywolanie)
{
  T *= 2;

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

  for (int i = 0; i < T / 2; i++)
    if (A[i] != -1)
      hash_al_wstaw(B, A[i], T, wywolanie);

  delete[] A;

  return B;
}

int main()
{
  const int T = 1048576;
  int *tab_miesz = new int[T];

  for (int i = 0; i < T; i++)
    tab_miesz[i] = -1;

  const int length = 12000000;
  int *tab = new int [length];

  for (int i = 0; i < length; i++)
    tab[i] = i;

  std::random_shuffle(tab, tab + length);

  int wywolanie = 0;
  int procent10 = T / 10;
  int procent = 0;
  int zapelnienie = 0;
  int suma_wywolan = 0;
  double czas = 0;

  std::cerr << "\t \t ***Pomiar wypełniania tablicy*** \n \n";
  for (int i = 0; i < T * 0.9; i++)
  {
    hash_al_wstaw(tab_miesz, tab[i], T, wywolanie);

    if (i == procent)
    {
      wywolanie = 0;
      auto start = std::chrono::high_resolution_clock::now();

      for (;i < procent + 10000; i++)
        hash_al_wstaw(tab_miesz, tab[i], T, wywolanie);

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

      std::chrono::duration<double, std::micro> duration = end - start;

      std::cerr << zapelnienie << "% " << "Uplynelo: " << duration.count() << "us\n";
      std::cerr << zapelnienie << "% " << "Wywolania: " << wywolanie << "\n" << "\n";

      procent += procent10;
      zapelnienie += 10;
    }
  }

  wywolanie = 0;
  procent10 = T / 10;
  procent = T / 10;
  zapelnienie = 10;

  for (int i = 0; i < T; i++)
    tab_miesz[i] = -1;

  std::cerr << "\n \t \t ***Pomiar wyszukiwania w tablicy*** \n \n";
  for (int i = 0; i < T * 0.9; i++)
  {
    hash_al_wstaw(tab_miesz, tab[i], T, wywolanie);

    if (i == procent)
    {
      wywolanie = 0;
      auto start = std::chrono::high_resolution_clock::now();

      for (int j = 0 ; j < procent; j += procent / 10000)
        hash_al_szukaj(tab_miesz, tab[j], T, wywolanie);

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

      std::chrono::duration<double, std::micro> duration = end - start;

      std::cerr << zapelnienie << "% " << "Uplynelo: " << duration.count() << "us\n";
      std::cerr << zapelnienie << "% " << "Wywolania: " << wywolanie << "\n" << "\n";

      czas += duration.count();
      suma_wywolan += wywolanie;

      procent += procent10;
      zapelnienie += 10;
    }
  }
}