Hi. I am supposed to store a Student class in a hash table. The hash table is supposed to use the student number as the key. My professor already created the hash table code, and I am supposed to use it to create a main program to store student numbers in it. I am even having a problem creating a hash table object, which my prof refers to as an index.
Here is my professor's code for index.hpp
#ifndef INDEXCHT_HPP
#define INDEXCHT_HPP
// Index: Header File
template <class Etype, class Ktype>
// Index stores elements of Etype with keys of Ktype
// Assumptions: 1) Key values are unique
// 2) Etype is an object with methods Key and Hash
class Index
{
public:
enum KindOfEntry { active, empty, deleted };
// Constructor
//
// Input : None
// Purpose: To create an empty Index
// Output : None
Index ( );
// Copy constructor
//
// Input : None
// Purpose: To initialize Index to I
// Output : None
Index ( const Index & I );
// Destructor
//
// Input : None
// Purpose: To free memory of Index
// Output : None
~Index ( );
// Copy assignment
//
// Input : Index I
// Purpose: To assign I to current Index
// Output : Current Index
const Index & operator= ( const Index & I );
// Insert
//
// Input : Element E
// Purpose: To place E into the Index
// Assume : No duplicate keys are allowed
// Output : 1 if successful; 0 otherwise
int Insert ( const Etype & E );
// Update
//
// Input : Element E
// Purpose: To replace E in the Index
// Output : 1 if successful; 0 otherwise
int Update ( const Etype & E );
// Remove
//
// Input : Key K
// Purpose: To remove the element with key K from Index
// Output : 1 if successful; 0 otherwise
int Remove ( const Ktype & K );
// Retrieve
//
// Input : Key K
// Purpose: To return element E with key K from Index
// Output : Element E and 1 if successful; 0 otherwise
int Retrieve ( const Ktype & K, Etype & E ) const;
// Clear
//
// Input : None
// Purpose: To re-initialize Index to empty
// Output : None
void Clear ( );
private:
// DoubleArray
//
// Input : None
// Purpose: To double the maximum size of Index (to the nearest prime)
// Output : None
void DoubleArray ( );
// Prime
//
// Input : Integer N
// Purpose: To check if N is a prime number
// Output : 1 if N is prime; 0 otherwise
int Prime ( int N );
// NextPrime
//
// Input : Integer N
// Purpose: To find the next prime integer greater than N
// Output : The next prime integer greater than N
int NextPrime ( int N );
// FindPos
//
// Input : Key K
// Purpose: To find the location of the first empty hash entry or
// To find the location of the element with key K
// (whichever comes first)
// Output : The location
unsigned int FindPos ( const Ktype & K ) const;
// Data members
// Hash table entry
struct HashEntry
{
Etype Element;
KindOfEntry Info;
// HashEntry constructors
HashEntry ( ) : Info ( empty )
{ }
HashEntry ( const Etype & E, KindOfEntry T = active ) :
Element ( E ), Info ( T )
{ }
};
// Current and maximum size of Index
int CurrentSize, MaxSize;
// Dynamic array to store the elements of Index
HashEntry *Array;
};
#endif
And here is the index.cpp
#include "indexcht.hpp"
#include <iostream.h>
// Index: Implementation File ( Closed Hash Table )
// Notes: 1) Delete and new functions are assumed to take constant time.
//
// 2) Expected time complexity is based on linear probing
// (NOT quadratic probing as implemented).
//
// 3) Non-independence of probes (i.e. primary clustering)
// is assumed.
//
// 4) U is defined as the percentage of empty cells.
// L (Load factor) is defined as the percentage of non-empty cells.
//
// 5) The hash function is assumed to take constant time.
// Initial size of Index
static const int InitHTSize = 11; // Prime
// DoubleArray
//
// Time complexity: O(n)
template <class Etype, class Ktype>
void
Index<Etype,Ktype>::DoubleArray ( )
{
HashEntry *OldArray = Array;
int OldSize = MaxSize;
CurrentSize = 0;
MaxSize = NextPrime ( 2*MaxSize ); // Table size must be prime
Array = new HashEntry [MaxSize];
for ( int i=0; i<OldSize; i++ )
if ( OldArray[i].Info == active )
Insert ( OldArray[i].Element );
delete [] OldArray;
}
// Prime
//
// Time complexity: O(sqrt(n))
template <class Etype, class Ktype>
int
Index<Etype,Ktype>::Prime ( int N )
{
for ( int i=3; i*i <= N; i+=2 )
if ( N % i == 0 )
return 0;
return 1;
}
// NextPrime
//
// Expected time complexity: O(log n)
template <class Etype, class Ktype>
int
Index<Etype,Ktype>::NextPrime ( int N )
{
// Ensure N is odd
//if ( N % 2 == 0 )
N++;
//else
// N += 2;
for (; !Prime ( N ); N += 2 );
return N;
}
// FindPos
//
// Expected time complexity (with linear probing):
//
// (1 + (1/(U^2)))/2 if Element with K is NOT found
// (1 + (1/U))/2 if Element with K is found
template <class Etype, class Ktype>
unsigned int
Index<Etype,Ktype>::FindPos ( const Ktype & Key ) const
{
Etype E;
unsigned int i = 0;
unsigned int CurrentPos = E.Hash ( Key ) % MaxSize;
while ( Array[CurrentPos].Info != empty &&
Array[CurrentPos].Element.Key( ) != Key )
{
// Quadratic probing
CurrentPos += (2 * ++i) - 1; // Step size is the next odd number
if ( CurrentPos >= MaxSize ) // Wrap around
CurrentPos -= MaxSize;
}
return CurrentPos;
}
// Constructor
//
// Time complexity: O(1)
template <class Etype, class Ktype>
Index<Etype,Ktype>::Index ( ) : MaxSize ( InitHTSize ), CurrentSize ( 0 )
{
Array = new HashEntry [MaxSize];
}
// Copy constructor
//
// Time complexity: O(n)
template <class Etype, class Ktype>
Index<Etype,Ktype>::Index ( const Index<Etype,Ktype> & Rhs )
{
Array = NULL;
*this = Rhs;
}
// Destructor
//
// Time complexity: O(1)
template <class Etype, class Ktype>
Index<Etype,Ktype>::~Index ( )
{
delete [] Array;
}
// Copy assignment
//
// Time complexity: O(n)
template <class Etype, class Ktype>
const Index<Etype,Ktype> &
Index<Etype,Ktype>::operator= ( const Index<Etype,Ktype> & Rhs )
{
if ( this != &Rhs )
{
delete [] Array;
MaxSize = Rhs.MaxSize;
CurrentSize = Rhs.CurrentSize;
Array = new HashEntry [MaxSize];
for ( int i=0; i<MaxSize; i++ )
Array[i] = Rhs.Array[i];
}
return *this;
}
// Insert
//
// Amortized expected time complexity:
//
// (1 + (1/(U^2)))/2 if 1 is returned
// (1 + (1/U))/2 if 0 is returned
template <class Etype, class Ktype>
int
Index<Etype,Ktype>::Insert ( const Etype & Element )
{
unsigned int CurrentPos = FindPos ( Element.Key ( ) );
if ( Array[CurrentPos].Info == active )
return 0;
else
{
if ( Array[CurrentPos].Element != Element )
{
Array[CurrentPos] = HashEntry ( Element );
// U >= 0.5 (Table size must be at least half empty)
if ( ++CurrentSize > MaxSize/2 )
DoubleArray ( );
}
else
Array[CurrentPos].Info = active;
return 1;
}
}
// Update
//
// Expected time complexity:
//
// (1 + (1/(U^2)))/2 if 0 is returned
// (1 + (1/U))/2 if 1 is returned
template <class Etype, class Ktype>
int
Index<Etype,Ktype>::Update ( const Etype & Element )
{
unsigned int CurrentPos = FindPos ( Element.Key ( ) );
if ( Array[CurrentPos].Info == active )
{
Array[CurrentPos] = HashEntry ( Element );
return 1;
}
else
return 0;
}
// Remove
//
// Expected time complexity:
//
// (1 + (1/(U^2)))/2 if 0 is returned
// (1 + (1/U))/2 if 1 is returned
template <class Etype, class Ktype>
int
Index<Etype,Ktype>::Remove ( const Ktype & Key )
{
unsigned int CurrentPos = FindPos ( Key );
if ( Array[CurrentPos].Info == active )
{
Array[CurrentPos].Info = deleted;
return 1;
// Note that CurrentSize remains unchanged
}
else
return 0;
}
// Retrieve
//
// Expected time complexity:
//
// (1 + (1/(U^2)))/2 if 0 is returned
// (1 + (1/U))/2 if 1 is returned
template <class Etype, class Ktype>
int
Index<Etype,Ktype>::Retrieve ( const Ktype & Key, Etype & Element ) const
{
unsigned int CurrentPos = FindPos ( Key );
if ( Array[CurrentPos].Info == active )
{
Element = Array[CurrentPos].Element;
return 1;
}
else
return 0;
}
// Clear
//
// Time complexity: O(n)
template <class Etype, class Ktype>
void
Index<Etype,Ktype>::Clear ( )
{
CurrentSize = 0;
for ( int i=0; i<MaxSize; i++ )
Array[i].Info = empty;
}
I tried creating it like this:
Index <Student, Student.itsID> I;
But it gave me a error:
error C2143: syntax error : missing ',' before '.'
It is my understanding that it should be like this:
Index < class Etype, class Ktype>
in my notes the teacher referred to the class as the Etype and the student ID in the class as the Ktype. But in the code it is referring to the class, which student ID is not, it is a data member! I am confused.
Anybody understand hashing or my professor's code that can help me? I really appreciate it. Thanks in advance.
23-Jun-2004, 23:33
Meeting the local Iraqis by crystalattice
