#include <string>
#include <iostream>
#include <iomanip>
#include <unistd.h>

/* 
   the plan:
     array of 1000 ints, all set to zero: counts
     generate 1000000 random strings
     for each: calculate h = hash(s) % 1000
               add 1 to count[h]
     make sure all counts roughly the same
*/

const int array_size = 1000,
          num_experiments = 1000000;

int hash(string s)
{ int h=1;
  for (int i=0; i<s.length(); i+=1)
    h *= s[i];
  int r;
  if (h == -2147483648)
    r = 9864;
  else if (h < 0)
    r = -h;
  else
    r = h;
  if (r < 0)
    cout << "h = " << h << ",   r = " << r << "\n";
  return r; }

const string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-' ";

string random_string(int minlen, int maxlen)
{ int len = minlen + random() % (maxlen-minlen+1);
  string ans = "";
  for (int i=0; i<len; i+=1)
    ans += alphabet[random() % alphabet.length()];
  return ans; }

int scount[array_size];

void main()
{ srandomdev();
  for (int i=0; i<array_size; i+=1)
    scount[i]=0;
  for (int i=0; i<num_experiments; i+=1)
  { string r = random_string(3, 20);
    int h = hash(r);
    h %= array_size;
    scount[h] += 1; }
  for (int i=0; i<array_size; i+=1)
  { cout << setw(6) << i << "   " << scount[i] << "\n"; } }