#pragma warning(disable:4786)
#ifndef HashTable_H
#define HashTable_H
#include <string>
#include <vector>
using std::vector;
using std::string;
template <class Object>
class HashTable
{
public:
HashTable(double moc );
virtual int findPos( const Object & x );
void makeEmpty( );
void insert( const Object & x );
void remove( const Object & x );
Object * find( const Object & x );
int getSize() {
int size = 0;
for( int j = 0; j < array.size( ); j++ )
if (array[ j ].info == ACTIVE)
size++;
return size;
};
int getLookups(){
return lookups;
};
int getCapacity(){
return array.size();
};
double getLambda(){
return static_cast<double>(getSize())/static_cast<double>(getCapacity());
}
enum EntryType { ACTIVE, EMPTY, DELETED };
private:
struct HashEntry
{
Object element;
EntryType info;
HashEntry( const Object & e = Object( ), EntryType i = EMPTY )
: element( e ), info( i ) { }
};
int occupied;
bool isActive( int currentPos ) const;
void rehash( );
bool isPrime( int n ) const;
int nextPrime( int n ) const;
double maxOccupiedPercentage;
protected:
int lookups;
unsigned int hash( const string & key ) const;
vector<HashEntry> array;
};
template <class Object>
class LinearHashTable : public HashTable<Object> {
public:
LinearHashTable(double moc) : HashTable<Object>(moc) {};
virtual findPos( const Object & x )
{
int collisionNum = 0;
int currentPos = hash( x ) % array.size( );
lookups++;
while( array[ currentPos ].info != EMPTY &&
array[ currentPos ].element != x )
{
lookups++;
currentPos++;
if( currentPos >= array.size( ) )
currentPos -= array.size( );
}
return currentPos;
}
};
#include "HashTable.cpp"
#endif