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:
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.
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.