Site navigation

HashTable

Useful Tools and Components
#1

Here’s a hash table with linked lists to resolve collisions. It hasn’t been thoroughly tested but it appears to work correctly. Here’s an example of how to use it:

HashTable<Image*> table;
table.set(T("giraffe"),giraffeImg);
table.set(T("dog"),dogImg);
table.set(T("emu"),emuImg);

table[T("giraffe")]   >>   giraffeImg
table[T("dog")]       >>   dogImg
table[T("emu")]       >>   emuImg
table[T("moose")]     >>   0
#2

There is also an excellent one that comes with the standard_extension set. :slight_smile:

#3

Got a link? Is it written in JUCE?

#4

Don’t need a link, it comes with the compiler, it’s in the std set, or std_ext, depending on the compiler.

#5

hmm… didn’t know there was a hash table that came with c++. if i did, i probably wouldn’t have coded my own. :stuck_out_tongue:

#6

The one that comes with it is pretty powerful. It has a hashing function that provides for an extremely low chance of collisions. It has a specalized template for strings to help prevent collisions. When you define the class you can pass in your own hashing function in the template parameters if you have a more specialized needs, etc… It is immensly powerful.

The best documentation on the current stl and the stl_ext libraries is at http://www.sgi.com/tech/stl/table_of_contents.html and if you search for ‘hash’, you will find things from hash_set’s, hash_map’s, multi versions of each, and a generic ‘hash’ function which is used by the afore mentioned ones.

Also, if anyone reads this thread, you should take a look at the rope class, if you want a very fast string function to handle strings that can be arbitratilly large and still remain fast. It is unsuitable for anything short however. :slight_smile:

EDIT: Here is a code snippet of how to use the hash_map that comes with C++, with the key being a string, and the value being an int.

[code]eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};

int main()
{
hash_map<const char*, int, hash<const char*>, eqstr> months;

months[“january”] = 31;
months[“february”] = 28;
months[“march”] = 31;
months[“april”] = 30;
months[“may”] = 31;
months[“june”] = 30;
months[“july”] = 31;
months[“august”] = 31;
months[“september”] = 30;
months[“october”] = 31;
months[“november”] = 30;
months[“december”] = 31;

cout << "september -> " << months[“september”] << endl;
cout << "april -> " << months[“april”] << endl;
cout << "june -> " << months[“june”] << endl;
cout << "november -> " << months[“november”] << endl;
}[/code]

#7