// How easy is it to make a good hash function?

// If we are using chaining to resolve collisions, and the
//    table has H entries and we have inserted N random
//    things, then it is obvious that the average length
//    of one of the linked lists will be N/H.
// If we can estimate the amound of data N, perhaps we
//    could set H=N when creating the table, and we'd
//    expect everything to be fast. The average look-up
//    operation would have to search a linked list of
//    length one.
// Except there is more to it than that. An average of
//    1 can be achieved in many ways. 999 empty lists plus
//    one of length 1,000 has an average of 1, but is useless.
//    1,000 lists all of length exactly 1 would be perfect
//    but unrealistic to expect. A bad hash function would
//    fail to distribute records evenly and would result in
//    lots of empty lists and a few long ones, ruining the
//    search time.

// Experiment:
//    create a hash table of size 10,000 and insert 10,000
//    random strings. See how evenly distributed they are.

// First experimental hash function multiplies together
//    the ASCII codes of all the characters in a string.
//    is it good enough?

#include <string>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <stdio.h>

string alpha = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ";

string random_string()
{ int len = random()%15+6;
  string s="";
  for (int i=0; i<len; i+=1)
  { char c = alpha[random()%53];
    s+=c; }
  return s; }

const int hashsize = 10000;

// We are only simulating a hash table. The following array is
// just used to count the number of times each possible hash
// value comes up. That is of course what the length of the
// linked list would have been if it were a real hash table.

int counts[hashsize];

int hash(string s)
{ int h = 983475;
  for (int i=0; i<s.length(); i+=1)
    h *= s[i];
  if (h<0)
    h = -h;
  if (h % hashsize < 0)
  { cout << "ERROR!!! " << h << ", " << h % hashsize << "\n";
    printf("h = %X\n", h);
    return 1; }
  return h % hashsize; }

void main()
{ srandomdev();
  for (int i=0; i<hashsize; i+=1)
    counts[i]=0;
  for (int i=0; i<hashsize; i+=1)
  { string s = random_string();
    int p = hash(s);
    counts[p] += 1; }
  for (int i=0; i<hashsize; i+=1)
    cout << setw(6) << i << "  " << counts[i] << "\n"; }