In article <3f********@10.10.0.241>, Brian Genisio wrote:
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,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/