• 0

[c++] Hashing Help


Question

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.

Link to comment
Share on other sites

5 answers to this question

Recommended Posts

  • 0

I think all you want to do is:

index I;

I.insert(Student);

That should insert the student then generate a key for that student.

Ummmm... I never implemented any kind of hash, nor do I want to, but I think thats right. Give it a whirl :blink:

By the way, your professor's commenting style is discusting! I got lost in the header file.

Link to comment
Share on other sites

  • 0

You want to put:

Index <Student, int> I; //Assuming Student is the type of class you want to insert

You are specifying TYPES, not what you want to insert.

Link to comment
Share on other sites

  • 0

thanks a lot! silly me!

ok, i am having a new problem. in the index's header file it says it needs a key, and a hash method in the class. I am not sure how to create them. Here is what I got in my Student class:

int Student::Hash (int key)

{

return key%101;

}

int Student::Key ()

{

return itsID;

}

I am getting this error:

error C2662: 'Key' : cannot convert 'this' pointer from 'const class Student' to 'class Student &'

it is pointing to this line of code in the insert function:

unsigned int CurrentPos = FindPos ( Element.Key ( ) );

And this is what is in my main:

Student S;

Index<Student, int> I;

S.setID(100);

I.Insert(S);

cout << "Any errors? \n";

Link to comment
Share on other sites

  • 0

Ok i fixed the above. But now I have a new problem.

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&lt;Student, int&gt; I;

S.setAge(4);

S.setID(5);

insertSuccess = I.Insert(S);

cout &lt;&lt; "Insert success = " &lt;&lt; insertSuccess&lt;&lt; endl;

retrieveSuccess = I.Retrieve(5,Answer);

cout &lt;&lt; "Retrieve success = " &lt;&lt; retrieveSuccess&lt;&lt; endl;

cout &lt;&lt; "Answer.ID = " &lt;&lt; Answer.getID &lt;&lt; endl;
cout &lt;&lt; "Answer.Age = " &lt;&lt; Answer.getAge &lt;&lt; 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 &amp;S) const
	{
 ?if (itsID != S.itsID)
 ?	return true;
 ?else
 ?	return false;
	}
};

#endif

#include "student.h"
#include &lt;iostream.h&gt;

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.

Link to comment
Share on other sites

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.