#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <math.h>
#include "MyTime.h"
#include "PerfectHash.h"
#include "LinearHash.h"
#include "QuadraticHash.h"
#include "DoubleHash.h"
#include "ListHash.h"
#define NUMWORDS 15338
#define TABLESIZE NUMWORDS
int key_String(char *string) {
/*
These are alternative key generators. They are very poor choices however, since they result
in statistical anomolies and cannot be analyzed outside of the scope of a particular
language and platform.
return abs((int)string);
return abs((int)(string)*strlen(string));
*/
// An excellent string key generator.
int h = 0;
int off = 0;
char *val = string;
int len = strlen(string);
// This did not create any duplicate keys
for (int i = len ; i > 0; i--)
h = (h * 37) + val[off++];
/* This resulted in duplicate keys!!!
if (len < 16) {
for (int i = len ; i > 0; i--) {
h = (h * 37) + val[off++];
}
} else {
// only sample some characters
int skip = len / 16;
for (int i = len ; i > 0; i -= skip, off += skip) {
h = (h * 39) + val[off];
}
}
*/
return abs(h);
}
//
// Select a particular type of hash table to test
//
HashTable * selectTable() {
char choice;
float sizeFactor;
cout << "CMSC441 Hash table test bed. Select hash table:" << endl;
cout << " 1] Linear Probing" << endl;
cout << " 2] Quadratic Probing" << endl;
cout << " 3] Double Hash" << endl;
cout << " 4] Chaining" << endl;
cout << " 5] Perfect Hashing " << endl;
cout << ">";
cin >> choice;
cout << " Table size factor: " << endl;
cout << ">";
cin >> sizeFactor;
int size = (int) TABLESIZE * sizeFactor;
switch(choice) {
case '1': return new LinearHash(size);
case '2': return new QuadraticHash(size);
case '3': return new DoubleHash(size);
case '4': return new ListHash(size);
case '5': return new PerfectHash(size);
default: return NULL;
}
}
//
// Load the test data set
//
int LoadTestSet(Object *&testSet, int *&keySet) {
// Open sample data file, allocate memory
ifstream dataset("hashkeys2.txt");
testSet = new Object[NUMWORDS];
keySet = new int [NUMWORDS];
char word[500];
int len,n = 0;
// Load all keys in data file
while (dataset.is_open() && !dataset.eof() && n<NUMWORDS) {
dataset.getline(word,sizeof(word)-1); // Read key
if ((len = strlen(word)) > 0) { // Valid key?
testSet[n] = (Object)new char[len+1]; // Copy into object array
strcpy((char *)testSet[n],word);
keySet[n] = key_String(word); // Compute its key
n++;
}
}
return n;
}
//
// Main test routine
//
int main() {
Object *testSet;
int *keySet;
HashTable *hash;
int testNum;
MyTime start, doneInsert, doneSearch;
// Select hash table
hash = selectTable();
if (hash==NULL) return 1;
// Load objects into array
cout << "Loading..." << endl;
testNum = LoadTestSet(testSet, keySet);
cout << "Loaded " << testNum << " hash objects"
<< endl;
start = GetMyTime();
// Add all objects
for (int n=0; n<testNum; n++) {
// cout << "Insert: n = " << n << endl;
hash->Insert(keySet[n], testSet[n]);
}
doneInsert = GetMyTime();
// Search for all objects
Object search;
for (n=0; n<testNum; n++) {
search = (char *)hash->Search(keySet[n]);
if (search==NULL) ;
// cout << "Failure on " << n << ": " << testSet[n] << " = " << keySet[n] << endl;
}
doneSearch = GetMyTime();
hash->PrintStats();
cout << "Insertion time: " << (double)(doneInsert - start) / GetMyAccuracy() << endl;
cout << "Search time: " << (double)(doneSearch - doneInsert) / GetMyAccuracy() << endl;
return 0;
}