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.
Question
saiz66
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; }; #endifAnd 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.
Link to comment
Share on other sites
5 answers to this question
Recommended Posts