#include "LinearHash.h"
#include <assert.h>
#include <memory.h>
#include <iostream.h>
#define EMPTY_KEY (-1)
//
// Constructor requires size of table
//
LinearHash::LinearHash(int size) {
iSteps = sSteps = collisions = insertions = searches = 0;
// Allocate table data
N = size;
keys = new Key[N]; memset(keys,EMPTY_KEY,sizeof(Key)*N);
data = new Object[N]; memset(data, 0,sizeof(Object)*N);
}
//
// Generic hash function for linear hashing H(key,index,c) = (k + ci) mod N.
//
#define c ((N/3)+1)
int LinearHash::H(Key key, int index) {
return abs(key + c*index) % N;
};
//
// Return the element with the specified key
//
Object LinearHash::Search(Key key) {
searches++;
int pos;
for (int i=0; i < N; i++) {
sSteps++;
pos = H(key,i);
if (keys[pos] == key) {
#ifdef HASH_DEBUG
cout << "Found (" << key << "," << data[pos] << ") at " << pos << endl;
#endif
return data[pos];
}
if (keys[pos] == EMPTY_KEY)
break;
}
#ifdef HASH_DEBUG
cout << "Lost " << key << endl;
#endif
return NULL;
}
//
// Insert an untyped element into the hash table
//
void LinearHash::Insert(Key key, Object obj) {
insertions++;
for (int i=0; i<N; i++) {
iSteps++;
int pos = H(key,i);
if (keys[pos] == -1) {
#ifdef HASH_DEBUG
cout << "Inserted (" << key << "," << data << ") at " << pos << endl;
#endif
keys[pos] = key;
data[pos] = obj;
if (i>0)
collisions++;
return;
}
}
}
//
// Print statistical information on hash table run
//
void LinearHash::PrintStats() {
cout << "Statistics for class LinearHash(" << N << "): " << endl;
cout << " insertions: " << insertions
<< ", collisions = " << collisions << "(" << collisions*100/insertions << "%)"
<< ", iSteps = " << iSteps << "(average = " << (float)iSteps/collisions << ")" << endl
<< " searches = " << searches
<< ", sSteps = " << sSteps << "(average = " << (float)sSteps/searches << ")"
<< endl;
}