Good Hash Implementation?

[Brian Genisio]

Hello all,

I need to use a hash table for quick lookup... What is the best way to
do it?

My current solution uses stl::map, where I essentially do the following
(not compilable code):

class MyObj;
struct MyObjList {
MyObj *object;
MyObjList *next;
}
stl::map<int, MyObjList*> objMap;
objMap[createHash(&Obj)]->obj = &Obj; // Storage
objMap[createHash(lookup_info)]; // lookup

Where createHash generates a non-unique integer, and I properly use the
list structure, to create a list of the objects with the same hash key.

While this method has _drastically_ reduced my lookup time, from a
standard scan (Comparison is expensive on this object), it feels clunky,
and there must be a better way to do this, aside from writing it
completely from scratch (STL MAP is probably better than I can do from
scratch, without a lot of work, I would immagine).

Any general ideas?

Thanks,
Brian

 

[Donovan Rebbechi]

Hello all,

I need to use a hash table for quick lookup... What is the best way to
do it?

My current solution uses stl::map, where I essentially do the following
(not compilable code):

class MyObj;
struct MyObjList {
MyObj *object;
MyObjList *next;
}
stl::map<int, MyObjList*> objMap;
objMap[createHash(&Obj)]->obj = &Obj; // Storage
objMap[createHash(lookup_info)]; // lookup

Where createHash generates a non-unique integer, and I properly use the
list structure, to create a list of the objects with the same hash key.

While this method has _drastically_ reduced my lookup time, from a
standard scan (Comparison is expensive on this object), it feels clunky,
and there must be a better way to do this, aside from writing it
completely from scratch (STL MAP is probably better than I can do from
scratch, without a lot of work, I would immagine).

Any general ideas?

The only thing you've gained from this hoop-jumping exercise is that your
table lookups now only involve integer comparisons. But you could also
achieve the same result like this:

#include <set>

struct MyObj {};

int createHash(MyObj* );

struct MyObjAndInt {
MyObj *object;
int hashcode;
MyObjAndInt(MyObj* x) : object(x), hashcode(createHash(x)) {}
};

struct cmpObjAndInt {
bool operator() (const MyObjAndInt& left, const MyObjAndInt& right)
{
return left.hashcode < right.hashcode;
}
};


std::multiset< MyObjAndInt, cmpObjAndInt > s;

If you want a real hash, there are several available that ship with various
versions of STL.

One way to implement a *real* hashtable from standard containers that is
quite promising (IMO) is that you store all the nodes in a linked list, and
then for the hashtable entries, you use list iterators. Among other things,
this gives you (unordered) bidirectional iteration.

sketch of this:

template <typename T, typename HashFunction>
class HashTable {
std::list<T> thelist;
// It might help to have a way to initialise entries of v to a "NULL" value,
// but I don't see a clean way to do this
std::vector< list<T>::iterator > v;
HashFunction f;

// operations are for the most part a combination of vector and list member functions


Cheers,

 

[John Carson]

Hello all,

I need to use a hash table for quick lookup... What is the best way to
do it?

My current solution uses stl::map, where I essentially do the
following (not compilable code):

class MyObj;
struct MyObjList {
MyObj *object;
MyObjList *next;
}
stl::map<int, MyObjList*> objMap;
objMap[createHash(&Obj)]->obj = &Obj; // Storage
objMap[createHash(lookup_info)]; // lookup

Where createHash generates a non-unique integer, and I properly use
the list structure, to create a list of the objects with the same
hash key.

While this method has _drastically_ reduced my lookup time, from a
standard scan (Comparison is expensive on this object), it feels
clunky, and there must be a better way to do this, aside from writing
it completely from scratch (STL MAP is probably better than I can do
from scratch, without a lot of work, I would immagine).

Any general ideas?

Thanks,
Brian

Like Donovan says, a lot of implementations of the C++ standard library
supply one as an extension. In particular, the implementation from
Dinkumware that ships with VC++ has hash table implementations.