Hash Table Implementation in C++
 

Hi everybody. Does anyone have any sample hash table implementation for
separate chaining? I'm trying to implement it myself, but I'm stuck.
Thanks!

Re: Hash Table Implementation in C++
 

Diane wrote:
> Hi everybody. Does anyone have any sample hash table implementation for
> separate chaining? I'm trying to implement it myself, but I'm stuck.
> Thanks!
>

Why don't you show us what you currently have?

Re: Hash Table Implementation in C++
 

Please find below my code. I need an array of lists which are of type
Info. My problem is that I;m not quite sure if I should use an pointer
to a list ( see private member variable of class HashTable) or not. And
if i must use pointers, how should i modify my code? Thanks!

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>


using namespace std;



template <class Type>
struct Info
{
Info(const string& k, const Type& myData)
{
key = k;
data = myData;
occupied=false;
hasBeenOccupied = false;
}

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

// Overloaded operators
bool operator==(const Info& rhs) const
{ return getKey() == rhs.getKey(); }
bool operator!=(const Info& rhs) const
{ return !(*this == rhs); }

string key;
Type data;
bool occupied;
bool hasBeenOccupied;
};



template <class Info>
class HashTable
{
public:
// constructor and destructor
HashTable(int currentSize);
~HashTable();


// other functions
bool put(const Info& x); // enter data into table
void remove(const Info& x); // delete from table
bool isIn(const Info& x) const; // is key in table
bool isEmpty() const; // is table empty

int getTableSize() { return tableSize; }

// hash functions
int myhash(const Info& x, int tableSize) const;

private:
vector<std::list <Info> > myLists; // the array of lists
int tableSize;
int numberInTable; // number of items in table
};



// Class Implementation

template <class Info>
HashTable<Info>::HashTable(int currentSize)
{
numberInTable = 0;
tableSize = currentSize;

// myLists = new vector<std::list<Info> > [currentSize];

for (int i = 0; i < tableSize; i++)
{
myLists[i].clear();
}
}



template <class Info>
HashTable<Info>::~HashTable()
{}



// global main hash function
int hash(const string& key, int tableSize)
{
int index = 0;

for (int j = 0; j < key.length(); j++)
{
index += key[j];
}

return index % tableSize;
}



// my hash function takes an Info object as argument
template <class Info>
int HashTable<Info>::myhash(const Info& x, int tableSize) const
{
int index = hash(x.key, tableSize);

index %= myLists.size();

if (index < 0)
{
index += myLists.size();
}

return index;
}


// insert data into hash table
template <class Info>
bool HashTable<Info>::put(const Info& x)
{
int index = myhash(x, tableSize);

list<Info> & thelist = myLists[index];
if( find(thelist.begin(), thelist.end(), x) != thelist.end() )
{
return false;
}

thelist.push_back(x);


return true;

}

Re: Hash Table Implementation in C++
 

Why don't you use STL's hash_set or hash_map?

Regarding your question, if you use pointers to the list you'll save
few bytes, but you'll have to implement your own copy constructor,
assignment operator and destructor of the HashTable.
BTW, you don't need to "clear" the lists in the constructor, the lists
will start clean.

Yuval.

Re: Hash Table Implementation in C++
 

yuvalif@gmail.com wrote :
> Why don't you use STL's hash_set or hash_map?

Those are nonèstandard SGI extensions.

The standard one is unordered_map, but it is in TR1.
It's already available in namespace std::tr1 of some compilers.

[OT] Re: Hash Table Implementation in C++
 

"loufoque" <loufoque@remove.gmail.com> wrote in message
news:44324d92$0$9479$626a54ce@news.free.fr...
> yuvalif@gmail.com wrote :
>> Why don't you use STL's hash_set or hash_map?
>
> Those are nonhstandard SGI extensions.
>

(What's SGI? Silicon Graphics, Inc.? Standard Graphical Interface?)

-Howard

Re: [OT] Re: Hash Table Implementation in C++
 

>> yuvalif@gmail.com wrote :
>>> Why don't you use STL's hash_set or hash_map?

> "loufoque" <loufoque@remove.gmail.com> wrote in message
> news:44324d92$0$9479$626a54ce@news.free.fr...
>> Those are nonhstandard SGI extensions.

Howard <alicebt@hotmail.com> wrote:
> (What's SGI? Silicon Graphics, Inc.? Standard Graphical Interface?)

SGI is Silicon Graphics, Inc.

http://www.sgi.com/tech/stl/

--
Marcus Kwok

Re: Hash Table Implementation in C++
 

On 3 Apr 2006 16:06:56 -0700, "Diane" <froufrou_00@hotmail.com> wrote:
>Hi everybody. Does anyone have any sample hash table implementation for
>separate chaining? I'm trying to implement it myself, but I'm stuck.
>Thanks!

Try http://www.koders.com/

Good luck!
Roland Pibinger