Menu
There is no hashtable in the standard C library because either: no-one has submitted a proposal to the working group; or. the working group has deemed it unnecessary.
A hash table is a data structure that you can use to store data in key-value format with direct access to its items in constant time. Hash tables are said to be associative, which means that for each key, data occurs at most once.
Generally you create an array called "buckets" that contain the key and value, with an optional pointer to create a linked list. When you access the hash table with a key, you process the key with a custom hash function which will return an integer.
Take an array and use the hash function to hash the 26 possible characters with indices of the array. Then iterate over S and increase the value of the current character of the string with the corresponding index for each character. The complexity of this hashing approach is O(N), where N is the size of the string.
If you're using C++11, you have access to the <unordered_map> and <unordered_set> headers. These provide classes std::unordered_map and std::unordered_set.
If you're using C++03 with TR1, you have access to the classes std::tr1::unordered_map and std::tr1::unordered_set, using the same headers (unless you're using GCC, in which case the headers are <tr1/unordered_map> and <tr1/unordered_set> instead).
In all cases, there are corresponding unordered_multimap and unordered_multiset types too.
If you don't already have unordered_map or unordered_set, they are part of boost.
Here's the documentation for both.
There is a hash_map object as many here have mentioned, but it is not part of the stl. It is a SGI extension, so if you were looking for something in the STL, I think you are out of luck.
std::tr1::unordered_map, in <unordered_map>
if you don't have tr1, get boost, and use
boost::unordered_map in <boost/unordered_map.hpp>
Visual Studio has the class stdext::hash_map in the header <hash_map>, and gcc has the class __gnu_cxx::hash_map in the same header.
See std::hash_map from SGI.
This is included in the STLPort distribution as well.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With