t2hash.c compare 2 hashing methods

// avp/src/dispro/hash_misc/t2hash.c
// compare hashing step 1  with step hash * 2 + 1
// add av[1] (1000000) rand to htab[get_pow2size(av[1])],
// then search 2 * av[1] rand (from initial rand)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>

int
add1 (int ht[], int size, int key)
{
  int i = key % size;

  for (; ht[i] != -1; i = ++i % size)
    if (ht[i] == key)
      return 0;
  ht[i] = key;
  return 1;
}

int
add2 (int ht[], int size, int key)
{
  int i = key % size, step = (2 * i + 1) % size;

  for (; ht[i] != -1; i = (i + step) % size)
    if (ht[i] == key)
      return 0;
  ht[i] = key;
  return 1;
}

int
look1 (int ht[], int size, int key)
{
  int i = key % size;

  for (; ht[i] != -1; i = ++i % size)
    if (ht[i] == key)
      return 1;
 return 0;
}

int
look2 (int ht[], int size, int key)
{
  int i = key % size, step = (2 * i + 1) % size;

  for (; ht[i] != -1; i = (i + step) % size)
    if (ht[i] == key)
      return 1;
  return 0;
}

void
measure (int size, int *ht, int n, int (*add)(), int (*look)(), char *msg)
{
  int i, nn, k;

  puts(msg);
  clock_t start = clock();
  srand(0);
  for (k = i = 0; i < n; i++)
    k += add(ht, size, rand());
  printf("add %d (%f)  time %f sec\n",
     k, (double)k / size, (double)(clock() - start) / CLOCKS_PER_SEC);
  srand(0);
  for (nn = i = 0; i < 2 * n; i++)
    nn += look(ht, size, rand());


 printf("total time %f sec   search %d loops found %d (%f)\n",
    (double)(clock() - start) / CLOCKS_PER_SEC,
    2 * n, nn, (double)nn / (2 * n));
}

int
getsize (int n)
{
  int i = 1;

  while (i > 0 && i <= n)
    i <<= 1;

  return i > 0 ? i : INT_MAX;
}

int
main (int ac, char *av[])
{
  int n = atoi(av[1] ? av[1] : "1000000");
  if (n < 1)
    n = 1000000;

  int hsize = getsize(n),
    *ht = malloc(hsize * sizeof(int));

  printf("n = %d htsize = %d (%f)\n", n, hsize, (double)n / hsize);
  memset(ht, -1, hsize * sizeof(int));
  measure(hsize, ht, n, add1, look1, "step 1 hashing");
  memset(ht, -1, hsize * sizeof(int));
  measure(hsize, ht, n, add2, look2, "hash * 2 + 1 step hashing");

 return puts("End") == EOF;
}


/*
avp@avp-ubu1:hash_misc$ ./a.out 400000000
n = 400000000 htsize = 536870912 (0.745058)
step 1 hashing
add 364953976 (0.679780)  time 29.271316 sec
total time 102.030381 sec   search 800000000 loops found 467981948 (0.584977)
hash * 2 + 1 step hashing
add 364953976 (0.679780)  time 37.493039 sec
total time 129.154172 sec   search 800000000 loops found 467981948 (0.584977)
End
avp@avp-ubu1:hash_misc$ ./a.out 4000000
n = 4000000 htsize = 4194304 (0.953674)
step 1 hashing
add 3996283 (0.952788)  time 0.518494 sec
total time 7.049557 sec   search 8000000 loops found 4007329 (0.500916)
hash * 2 + 1 step hashing
add 3996283 (0.952788)  time 0.413647 sec
total time 2.192685 sec   search 8000000 loops found 4007329 (0.500916)
End
avp@avp-ubu1:hash_misc$ ./a.out 2500000
n = 2500000 htsize = 4194304 (0.596046)
step 1 hashing
add 2498560 (0.595703)  time 0.151391 sec
total time 0.512339 sec   search 5000000 loops found 2502925 (0.500585)
hash * 2 + 1 step hashing
add 2498560 (0.595703)  time 0.179143 sec
total time 0.611102 sec   search 5000000 loops found 2502925 (0.500585)
End
avp@avp-ubu1:hash_misc$ ./a.out
n = 1000000 htsize = 1048576 (0.953674)
step 1 hashing
add 999752 (0.953438)  time 0.123139 sec
total time 1.688386 sec   search 2000000 loops found 1000469 (0.500235)
hash * 2 + 1 step hashing
add 999752 (0.953438)  time 0.074876 sec
total time 0.407555 sec   search 2000000 loops found 1000469 (0.500235)
End
avp@avp-ubu1:hash_misc$ ./a.out 700000
n = 700000 htsize = 1048576 (0.667572)
step 1 hashing
add 699897 (0.667474)  time 0.034560 sec
total time 0.119492 sec   search 1400000 loops found 700246 (0.500176)
hash * 2 + 1 step hashing
add 699897 (0.667474)  time 0.032498 sec
total time 0.115200 sec   search 1400000 loops found 700246 (0.500176)
End
avp@avp-ubu1:hash_misc$ ./a.out 100000
n = 100000 htsize = 131072 (0.762939)
step 1 hashing
add 99997 (0.762917)  time 0.005376 sec
total time 0.020578 sec   search 200000 loops found 100007 (0.500035)
hash * 2 + 1 step hashing
add 99997 (0.762917)  time 0.004863 sec
total time 0.017239 sec   search 200000 loops found 100007 (0.500035)
End
avp@avp-ubu1:hash_misc$
*/