hashing help

[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;

	};

	#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;
  }

[saiz66]

my post was too long so i had to reply to my own post:

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.

[Amit Sebiz]

Pass the type of itsID member of Student class
i.e. if in class Student you have declared itsID as

int itsID

Use

Index <Student, int> I;

[saiz66]

thanks a lot, it worked!

could you explain to me why it said Index < class Etype, class Ktype> why does it refer to Ktype as a class? is int a class?

[saiz66]

thanks a lot!

When I insert a Student S with age 4 and ID 5, and by the way I set the Student ID as the key.

Main Code:

int key =0, insertSuccess =0, retrieveSuccess;

Student S;
Student Answer;

Index<Student, int> I;

S.setAge(4);

S.setID(5);

insertSuccess = I.Insert(S);

cout << "Insert success = " << insertSuccess<< endl;

retrieveSuccess = I.Retrieve(5,Answer);

cout << "Retrieve success = " << retrieveSuccess<< endl;

cout << "Answer.ID = " << Answer.getID << endl;
cout << "Answer.Age = " << Answer.getAge << endl;

Student Class:

#ifndef STUDENT_HPP
#define STUDENT_HPP

class Student
{

private:

	// data members
	int itsID;
	int itsNumber;
	char itsName[20];
	int itsAge;
	char itsCollege;


public:
	// constructor
	Student ();

	// destructor
	~Student ();

	int Hash (int key);
	int Key () const;
	void setID (int id);
	int getID ();
	void setStudent(char name[]);
	int getStudent();

	void setNumber(int number);
	int getNumber();
	void setAge(int age);
	int getAge();
	void setCollege(char college);
	char getCollege();

	bool operator != (const Student &S) const
	{
		if (itsID != S.itsID)
			return true;
		else
			return false;
	}
};

#endif

#include "student.h"
#include <iostream.h>

Student::Student ()
{
}

// Student destructor
Student::~Student ()
{
}

int Student::Hash (int key)
{
	return key;
}

int Student::Key () const
{
	return itsID;
}


void Student::setID (int id)
{
	itsID = id;
}

int Student::getID ()
{
	return itsID;
}

void Student::setNumber(int number)
{
	itsNumber = number;
}

int Student::getNumber()
{
	return itsNumber;
}

void Student:: setAge(int age)
{
	itsAge = age;
}

int Student::getAge()
{
	return itsAge;
}

void Student::setCollege(char college)
{
	itsCollege = college;
}

char Student::getCollege()
{
	return itsCollege;
}

I think my insert works fine, but I could be wrong. I am trying to check if it inserted correctly and that is why I am trying to retrieve the Student class. When I try to retrieve it using a key that is not 5 it gives me 0 that it did not retrieve it, which should be correct because the key should be 5. Only when I put 5 in:

retrieveSuccess = I.Retrieve(5,Answer);

it gives me the answer 1 for retrieveSuccess that it retrieved that key since I set the ID to 5. Now the problem is that when I put the Student class into Answer, and I use Answer.getID and Answer.getAge it does not display the ID to 5 and Age to 4 but ID as 1 and Age as 1. Anybody can help me? Thanks in advance.