Re: hash_map, keys and data structures
On Jul 2, 1:40 pm, Bharath <bharath...@gmail.com> wrote:
I recently used the hash_map class to create a dictionary of
some data. The template class takes the key, value, the class
which performs the compare function and a custom allocator and
so on.
Note that hash_map is a precuror to the unordered_map proposed
for the future standard, and that the unordered_map may have a
slightly different interface. (I believe that there are two
wide-spread interfaces to hash_map: one uses a single traits
class for both comparison and hashing, and the other has two
separate template parameters. The second solution is the one
adopted by the standard.)
I have read about hashing (years ago in college), never implemented
anything though.
My question here
1. Does hash_map offer just a data structure where the value/element
is stored against a key and the user/developer has to write the hash
function to generate the keys and store them using the above class.
Exactly. You have to provide the hash function, most of the
time. (At least in the standard, a few are provided for you:
std::string, std::type_info, etc.)
2. Does it also help with collision handling?
It handles collisions completely. You don't have to do
anything.
If the answer is no for above questions, then what about these?
1. Do I need to write the hash function for the element that I gives
me the key where I can store the element?
Unless the key type is one of the few which are directly
supported by the standard, you have to provide both a comparison
function and a hash function. In the standard version, the
comparison function defaults to std::is_equal<T> and the hash
function to std::hash<T>. std::is_equal uses the == operator,
if not redefined, and std::hash is only specified for a few
standard types.
2. Secondly how does hash_map internally store the data? Does
it use arrays or linked lists or something else?
Technically, it's up to the implementation, but some sort of
bucket based hash table is more or less required, since you have
functions returning information concerning the number of
buckets, etc.
--
James Kanze