#include <iostream>
#include <fstream>
#include <string>

const int init = 21512712, mult = 96169, emergency = 82631927;
const int tabsize = 100000;

int hash(string s)
{ int v = init;
  for (int i=0; i<s.length(); i+=1)
    v = v * mult + s[i];
  if (v < 0) v = -v;
  if (v < 0) v = emergency;
  return v % tabsize; }

string table[tabsize];
    // a string is an object, and it has a default consructor that
    // sets it to "", so this whole array is initialised even though
    // I haven't explicitly set any of its elements.

void main()
{ ifstream fin("/home/www/text/darwin/originofspecies");
  if (fin.fail())
  { cout << "Fail!\n";
    exit(1); }

  int skips = 0, words = 0;
  for (int i=1; true; i+=1)
  { string s;
    fin >> s;
    if (fin.fail())
    { cout << i << " read OK\n";
      break; }

    words += 1;
    int h = hash(s);
             // open hashing with linear probing
    while (table[h] != "" && table[h] != s)
    { h += 1;
      skips += 1;
      if (h == tabsize) h = 0; }
    table[h] = s; }

  cout << words << " words, " << skips << " skips, " << (double)skips/words << "\n";
  fin.close(); }