// Monday's hash table experiment was continued. I have
// only included in this file the functions and other
// things that were changed or added.

#include <math.h>

// The found out that Tuesday's hash function was terrible.
// Just multiplying together ascii codes results in a huge
// majority of even numbers. We also found out how to deal
// with the tricky value that is 80000000 in hexadecimal.

int hash(string s)
{ unsigned int h = 983475;
  for (int i=0; i<s.length(); i+=1)
    h = h * 97 + s[i];
  return h % hashsize; }

// The Poisson distribution tells us how many clash linked-lists
// of each size we would get with a theoretically perfect hash
// function. Comparing this calculation to observed results
// shows that our new hash function is just about the best
// it is possible to be.

double poisson(int n, int h, int v)
{ double lam = n/(double)h, fact=1.0;
  double r = exp(-lam)*pow(lam, v);
  for (int i=1; i<=v; i+=1)
    fact *= i;
  return r/fact*h; }

const int hashsize = 100000;

// We also experimented with varying the "fullness" (N/H) of
// the table to see how the distribution changes.

const int N = 3*hashsize/4;

void main()
{ srandomdev();
  for (int i=0; i<hashsize; i+=1)
    counts[i]=0;
  for (int i=0; i<N; i+=1)
  { string s = random_string();
    int p = hash(s);
    counts[p] += 1; }
  int summary[hashsize];
  for (int i=0; i<hashsize; i+=1)
    summary[i] = 0;
  for (int i=0; i<hashsize; i+=1)
    summary[counts[i]] += 1;
  int last_non_zero = 0;
  for (int i=0; i<hashsize; i+=1)
    if (summary[i]!=0)
      last_non_zero = i;
  for (int i=0; i<=last_non_zero; i+=1)
    printf("%8d linked lists has length %3d, expected %.0f\n", 
           summary[i], i, poisson(N, hashsize, i)); }