// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition (C++)" by Clifford A. Shaffer.
// Source code Copyright (C) 2007-2011 by Clifford A. Shaffer.
#include "book.h"
int main(int argc, char** argv)
{
if (argc != 3) {
cout << "Usage: hashsim <#_of_records> <#_of_iterations>\n";
return -1;
}
int recs = atoi(argv[1]);
int iterations = atoi(argv[2]);
srand(1);
int hashtable[2*recs]; // This is the pseudo hash table, twice the # of records
// Data collecting variables
int maxlen = 0; // Maximum length of any chain, ever
int avglen = 0; // Average for the maximum (per iteration) chain length
int minslots = (2*recs); // Minimum slots used by any interation
int avgslots = 0; // Average number of slots used per iteration
for(int i=0; i (2*recs)) cout << "ERROR\n";
hashtable[homeslot]++; // Imagine that we are inserting here, bump the count
}
// Update the statistics
for (j=0; j<(2*recs); j++) {
if (hashtable[j] > maxlen) maxlen = hashtable[j]; // longest chain ever
if (hashtable[j] > len) len = hashtable[j]; // longest chain this iteration
if (hashtable[j] > 0) slots++; // Something hit this slot
}
if (slots < minslots) minslots = slots;
avglen += len;
avgslots += slots;
}
// Calculate the final statistics
cout << "For " << iterations << " iterations on " << recs << " records\n";
cout << "The longest chain ever generated was " << maxlen << endl;
cout << "The average length for the maximum chain was "
<< ((double)avglen)/((double)iterations) << endl;
cout << "The minimum number of slots ever used was " << minslots << endl;
cout << "The average number of slots used was "
<< ((double)avgslots)/((double)iterations) << endl;
return 0;
}