Rehashing requires recomputing the hash function for all items in the hash table. Read more.....

Question

Since computing the hash function is expensive, suppose

objects provide a hash member function of their own, and each object

stores the result in an additional data member the rst time the hash

function is computed for it. Show how such a scheme would apply for the

Employee class in the implementation below , and explain under

what circumstances the remembered hash value remains valid in each

Employee.

The implementation

// Example of an Employee class

class Employee

{

public:

const string & getName( ) const

{ return name; }

bool operator==( const Employee & rhs ) const

{ return getName( ) == rhs.getName( ); }

bool operator!=( const Employee & rhs ) const

{ return !( *this == rhs; }

// Additional public members not shown

private:

string name;

double salary;

int seniority;

// Additional private members not shown

};

template<>

class hash<Employee>

{

public:

size_t operator()( const Employee & item )

{

static hash<string> hf;

return hf( item.getName( ) );

}

};

Answer 1

How are the employee records stored... by employee id # or last name?

I would assign each employee an id# because two employees can have the same last name.

Set up the hash table based on most significant digits.

In each bin keep them SORTED, so that you can do binary search in each bin during the fetch.

using namespace std;

#include <iostream>

#include <stdlib.h>

#include <string.h>

#define MAX_BIN_SIZE (10000) //that's enough for 100,000 employees

class HashTable

{

private:

long hashTable[10][MAX_BIN_SIZE]; // 1st bin # 0-9999, 2nd bin 10000-19999, 3rd bin #20000-29999, etc

long binCounts[10];

//a simple division...NO BIG DEAL !!!! any extra processing not worth the trouble

// and SLOWS it done just as much

int hash(long iData) { return( iData/10000); }

int InsertionSort( long iData, int binNum)

{

int iReturn=0;

if (binCounts[binNum]>=MAX_BIN_SIZE)

{

iReturn=-1;

}

else

{

cout << "InsertionSort : bin # " << binNum << endl;

int n = binCounts[binNum];

long * A = hashTable[binNum];

if (n==0)

{

A[0]=iData;

}

else

{

int iIndexPos = n-1;

while (

(A[iIndexPos] > iData) && (iIndexPos>=0)

)

{

A[iIndexPos+1] = A[iIndexPos];

iIndexPos--;

}

A[iIndexPos+1] = iData;

cout << "Insertion sort: iIndexPos = " << iIndexPos << endl;

}

}

return(iReturn);

}

public:

HashTable()

{

memset(hashTable,0,10*MAX_BIN_SIZE);

memset(binCounts,0,10*sizeof(long));

}

int Insert( long iData)

{

int iReturn=0;

int binNum = hash(iData);

if (InsertionSort(iData,binNum)==0)

{

binCounts[binNum]++;

}

else

{

iReturn=-1;

}

return(iReturn);

}

int GetBinCount(int binNum)

{

int iReturn=-1;

if(

(binNum>-1) && (binNum<10)

)

{

iReturn = binCounts[binNum];

}

return(iReturn);

}

long IndexerGetIndexAt ( int binNum, int iIndexPos)

{

long lReturn = -1;

int n = GetBinCount(binNum);

if (n>=0)

{

if ((iIndexPos>=0) && (iIndexPos<n))

{

lReturn = hashTable[binNum][iIndexPos];

}

}

return(lReturn);

}

};

int main()

{

HashTable hashTable;

for (int iLoop=0; iLoop<10; iLoop++)

{

long longIntNum =(long) ((rand()*1.0f/RAND_MAX)*99999+1);

hashTable.Insert(longIntNum);

}

for (int binNum=0; binNum<10; binNum++)

{

int binCount = hashTable.GetBinCount(binNum);

cout << " bin # " << binNum << " has " << binCount << " records " << endl;

for (int jLoop=0; jLoop<binCount; jLoop++)

{

cout << hashTable.IndexerGetIndexAt(binNum,jLoop) << endl;

}

}

}