08-03-2008, 06:00 AM
I have heard a lot of talk about hashtables from time to time. They are supposed to be very cool ways of storing data where the index you use to look up the data is somehow the data itself.
But hashtables are not part of the C++ standard template library... I think. So does anyone have any tips on how to write a hashtable?
08-03-2008, 07:01 AM
I made a C hash table out of structs, so I can't see C++ being at all difficult. Wiki up a hashtable datastructure and follow the algorithms it uses. Search the net for hashing algorithms as well (double hashing and linear probing for example); the algorithms will really determine how optimized you're lookups and insertions will be O(1) Versus O(n). You may even be able to search a C++ hash table, chances are someone has already written the class you need.
This is one of the things that I really love about Perl and PHP, perl has built in hashtables and PHP uses hash maps instead of arrays.
Hashmaps IMO are among the easiest datastructures to program. Hope that gives you a bit of an idea!