How to implement generic Map using a Hash Table

[jwelsh]

First let me just say that I'm a student seeking help on an assignment, but I am not asking for anyone to just hand me the answer. I am asking for help on understanding how to solve this problem. I'm stumped, and I don't quite understand it. I've done a ton of reading, searching, asking, and racking my brain, but I need someone to help me. Any input what so ever would greatly be appreciated. Thanks!

My assignment instructions:

Implement a generic Map that supports the insert and lookup operations. The implementation will store a hash table of pairs (key, definition). You will lookup a definition by providing a key. The following code provides the Map specification (minus some details).

template <typename HashedObj, typename Object>
class Pair
{
	HashedObj key;
	Object def;
	// Appropriate Constructors, etc.
};

template <typename HashedObj, typename Object>
class Dictionary
{
	public:
		Dictionary( void ) { }

		void insert( const HashedObj & key, const Object & definition );
		const Object & lookup( const HashedObj & key ) const;
		bool isEmpty() const;;
		void makeEmpty();

	private:
		HashTable<Pair<HashedObj,Object> > items;
};

I'm having a hard time understanding how to implement this. Here is what I have so far, and I'm not even sure if I'm on the right track or not.

My work thus far:

#include <iostream>
#include <string>
#include <vector>
#include <conio.h>

using namespace std;

template <typename HashedObj>
class HashTable
{
	public:
		explicit HashTable( int size = 101 )
		{
			makeEmpty( );
		}

		bool contains( const HashedObj & x ) const
		{
			return isActive( findPos( x ) );
		}

		void makeEmpty( )
		{
			currentSize = 0;

			for( int i = 0; i < array.size( ); i++ )
			{
				array[ i ].info = EMPTY;
			}
		}

		bool insert( const HashedObj & x )
		{
			// insert x as active
			int currentPos = findPos( x );

			if( isActive( currentPos ) )
			{
				return false;
			}

			array[ currentPos ] = HashEntry( x, ACTIVE );

			// rehash
			if(++currentSize > array.size( ) / 2 )
			{
				rehash( );
			}

			return true;
		}

		bool remove( const HashedObj & x )
		{
			int currentPos = findPos( x );

			if( !isActive( currentPos ) )
			{
				return false;
			}

			array[ currentPos ].info = DELETED;

			return true;
		}

		enum EntryType { ACTIVE, EMPTY, DELETED };

	private:
		struct HashEntry
		{
			HashedObj element;
			EntryType info;

			HashEntry( const HashedObj & e = HashedObj( ), EntryType i = EMPTY ): element( e ), info( i ) { }
		};

		vector<HashEntry> array;

		int currentSize;

		bool isActive( int currentPos ) const
		{
			return array[ currentPos ].info == ACTIVE;
		}

		int findPos( const HashedObj & x ) const
		{
			int offset = 1;
			int currentPos = myhash( x );

			while( array[ currentPos ].info != EMPTY && array[ currentPos ].element != x )
			{
				currentPos += offset; // Compute ith probe
				offset += 2;

				if( currentPos >= array.size( ) )
				{
					currentPos -= array.size( );
				}
			}

			return currentPos;
		}

		void rehash( )
		{
			vector<list<HashedObj> > oldLists = theLists;

			// create new double-sized, empty table
			theLists.resize( nextPrime( 2 * theLists.size( ) ) );

			for( int j = 0; j < theLists.size( ); j++ )
			{
				theLists[ j ].clear( );
			}

			// copy table over
			currentSize = 0;

			for( int i = 0; i < oldLists.size( ); j++ )
			{
				list<HashedObj>::iterator itr = oldLists[ i ].begin( );

				while( itr != oldLists[ i ].end( ) )
				{
					insert( *itr++ );
				}
			}
		}

		int myhash( const HashedObj & x ) const
		{
			int hashVal = hash( x );
			
			hashVal %= theLists.size( );

			if( hashVal< 0 )
			{
				hashVal += theLists.size( );
			}

			return hashVal;
		}
};

template <typename HashedObj, typename Object>
class Pair
{
	HashedObj key;
	Object def;

	public:
		Pair() {}
		~Pair() {}
};

template <typename HashedObj, typename Object>
class Dictionary
{
	public:
		Dictionary( void ) { }
		~Dictionary( ) { }

		void insert( const HashedObj & key, const Object & definition )
		{
			// ????
		}

		const Object & lookup( const HashedObj & key ) const 
		{
			// ??????
		}

		bool isEmpty() const 
		{ 
			// 
		}

		void makeEmpty() 
		{
			// 
		}

	private:
		HashTable<Pair<HashedObj,Object> > items;
};

// our pause function that allows us to view the results before closing the app
void pause() 
{
	printf("\n----------------------------------------------");
	printf("\nPress any key to exit...");
	_getch(); // waits for user to press any key
}

int main (void)
{
	Dictionary <std::string, std::string> dict;
	
	dict.insert("ex1", "example");
	dict.lookup("ex1");

	pause();

	return (0);
}

Any help or guidance on this would be greatly appreciated. Thanks!!!!!!

[abhimanipal]

What exactly do you mean by hashtable of pairs. Based on what I understood from your description, you need a generic implementation of maps. As I see that you have made efforts (also it may be the case that I have misunderstood your problem and the code is completely useless for you) I am giving out more code than I usually give .....
Hopefully this will solve your problem

template<class T1,class T2>
class Dict
{
      map<T1,T2> m1;
public:
      Dict()
      {}
      
      void insert(const T1& key,const T2& value)
      {
         m1[key]=value;      
      }
      
      T2 lookup(const T1&key)
      {
          return m1[key];
      }
      
};

[jwelsh]

abhimanipal, thanks for your reply!

What exactly do you mean by hashtable of pairs...

I was hoping someone else would know what that meant exactly. That was my assignment instruction, and my teacher wasn't of much help in clarifying it. I believe it means to store key/value pairs (like an associative array) in a hash table. I'm not familiar with hash tables yet, but from what I have read they store values in a somewhat random, yet balanced fashion?

Your example is much easier to follow and understand for me, and I wish that I could use it, but unfortunately I believe I have to follow the skeleton "Map specification" that the assignment instructs me to use (I posted the Map Specification in my first post). It uses a hash table instead of an associative array. I believe yours uses an associative array, right? Or is that a Map? I'm a little confused on the difference between a map and associative array.

Anyways, I really appreciate your help and if you or anyone can further help me understand how to solve this, I would greatly appreciate it. Thanks!

[abhimanipal]

In the skeleton that you have given the class Dictionary is similar to the class Dict ....But I do not understand why the class Pair is given.

According to me(Corrections are invited) there is no such thing as associative array in C++ . What you have are associative containers. There are 2 main types of associative containers
1. set/ multiset
2. map/ multimap (aka Hashmap )

[jwelsh]

Ok well that's good to know. My experience in programming in other languages is working against me. I guess the Pair class is for line 21 ( HashTable<Pair<HashedObj,Object> > items; ) in the Dictionary class. I'm guessing that is my hash table and it is using the Pair class as part of the template?

I will see if I can manage to implement your example, and I will let you know. Thanks!

[abhimanipal]

In line 21 you say

HashTable<Pair<HashedObj,Object> > items;

But HashTable in not C++ key word and nor have you defined it in your program

[jwelsh]

In line 21 you say

HashTable<Pair<HashedObj,Object> > items;

But HashTable in not C++ key word and nor have you defined it in your program

I believe it's actually the first class that I defined in my code from my first post (the second snippet of code). I'm not having any luck with this problem still. I don't know how to insert a pair (key, definition) into my hash table properly. Inside of my Dictionary class I have been trying something like this:

void insert( const HashedObj & key, const Object & definition )
{
    items.insert(Pair<HashedObj, Object>(key, definition));
}

But I am getting the following compile error:

Error 1 error C2661: 'Pair<HashedObj,Object>:: Pair' : no overloaded function takes 2 arguments

In the code above, items is an instance of my HashTable class, and I am trying to use the insert method of my HashTable class, which goes as follows:

bool insert( const HashedObj & x )
{
	// insert x as active
	int currentPos = findPos( x );

	if( isActive( currentPos ) )
	{
		return false;
	}

	array[ currentPos ] = HashEntry( x, ACTIVE );

	// rehash
	if(++currentSize > array.size( ) / 2 )
	{
		rehash( );
	}

	return true;
}

So to me it looks like I need to change my insert method to accept a Pair argument instead of a HashedObj, but then how do I hash it/add it to my table?

[jwelsh]

Ok, so I have made a little more progress, but I am currently getting the following error:

Error 6 error C2784: 'bool std::operator ==(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'Pair<HashedObj,Object>'

Can anyone tell me why I am getting the above error?

And here is my code thus far:

#include <iostream>
#include <string>
#include <vector>
#include <hash_map>
#include <list>
#include <algorithm>
#include <conio.h>

using namespace std;
using namespace stdext;

template <typename HashedObj>
class HashTable
{
	public:
		explicit HashTable( int size = 101 )
		{
			makeEmpty( );
		}

		bool contains( const HashedObj & x ) const
		{
			const list<HashedObj> & whichList = theLists[ myhash( x ) ];
			return find( whichList.begin( ), whichList.end( ), x ) != whichList.end( );
		}

		void makeEmpty( )
		{
			for( int i = 0; i < theLists.size( ); i++ )
			{
				theLists[ i ].clear( );
			}
		}

		bool insert( const HashedObj & x )
		{
			list<HashedObj> & whichList = theLists[ myhash( x ) ];

			if( find(whichList.begin( ), whichList.end( ), x ) != whichList.end( ) )
			{
				return false;
			}

			whichList.push_back( x );

			// rehash
			if( ++currentSize > theLists.size( ) )
			{
				rehash( );
			}

			return true;
		}

		bool remove( const HashedObj & x )
		{
			list<HashedObj> & whichList = theLists[ myhash( x ) ];
			list<HashedObj>::iterator itr = find( whichList.begin( ), whichList.end( ), x );

			if( itr == whichList.end( ) )
			{
				return false;
			}

			whichList.erase( itr );
			--currentSize;

			return true;
		}

	private:
		vector<list<HashedObj> > theLists;	// the array of lists
		int currentSize;

		void rehash( )
		{
			vector<list<HashedObj> > oldLists = theLists;

			// create new double-sized, empty table
			theLists.resize( nextPrime( 2 * theLists.size( ) ) );

			for( int j = 0; j < theLists.size( ); j++ )
			{
				theLists[ j ].clear( );
			}

			// copy table over
			currentSize = 0;

			for( int i = 0; i < oldLists.size( ); i++ )
			{
				list<HashedObj>::iterator itr = oldLists[ i ].begin( );

				while( itr != oldLists[ i ].end( ) )
				{
					insert( *itr++ );
				}
			}
		}

		int myhash( const HashedObj & x ) const
		{
			int hashVal = hash( x.getKey(), currentSize );
			
			hashVal %= theLists.size( );

			if( hashVal < 0 )
			{
				hashVal += theLists.size( );
			}

			return hashVal;
		}
};

bool isPrime(int x)
{
	int max = static_cast <int> (x); /* Cast it to remove warnings */

	if (x <= 0 || x == 1 || (x % 2 == 0 && x != 2))
	{
		return false;
	}
	
	for (int i = 3; i < max; i += 2)
	{
		if (x % i == 0)
		{
			return false;
		}
	}

	return true;
}

int nextPrime(int num)
{
	num++;

	while( !isPrime(num))
	{
		num++;
	}

	return num;
}

int hash( const string & key, int tableSize )
{
	int hashVal = 0;

	for( int i = 0; i < key.length( ); i++ )
	{
		hashVal = 37 * hashVal + key[ i ];
	}

	hashVal %= tableSize;

	if( hashVal = 0 )
	{
		hashVal += tableSize;
	}

	return hashVal;
}

template <typename HashedObj, typename Object>
class Pair
{
	public:
		Pair() { }
		~Pair() { }

		void create( string k, string d )
		{
			key = k;
			def = d;
		}

		const string & getKey() const
		{
			return key;
		}

	private:
		HashedObj key;
		Object def;
};

template <typename HashedObj, typename Object>
class Dictionary
{
	public:
		Dictionary( void ) { }
		~Dictionary( ) { }

		void insert( const HashedObj & key, const Object & definition )
		{
			// 
			Pair<string,string> p;
			p.create(key, definition);
			items.insert(p);
		}

		const Object & lookup( const HashedObj & key ) const 
		{
			// 
		}

		bool isEmpty() const 
		{ 
			// 
		}

		void makeEmpty() 
		{
			// 
		}

	private:
		HashTable<Pair<HashedObj,Object> > items;
};

// our pause function that allows us to view the results before closing the app
void pause() 
{
	printf("\n----------------------------------------------");
	printf("\nPress any key to exit...");
	_getch(); // waits for user to press any key
}

int main (void)
{
	Dictionary <string, string> dict;
	
	dict.insert("ex1", "example");
	//dict.lookup("ex1");

	pause();

	return (0);
}