hash_map, keys and data structures

[Bharath]

Hello,

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.

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.
2. Does it also help with collision handling?

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?
2. Secondly how does hash_map internally store the data? Does it use
arrays or linked lists or something else?

Thanks,
-Bharath

 

[Öö Tiib]

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.

hash_map is not part of current standard. AFAIK in TR1 there is
unordered_map that is hash map. So something will be in next 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.
2. Does it also help with collision handling?

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?
2. Secondly how does hash_map internally store the data? Does it use
arrays or linked lists or something else?

Since it is non-standard implementation we are talking about you need
to read documentation of your implementation to get answers to your
quesstions. Also you likely have the implementation on your hard drive
so why you do not look yourself how it is implemented?

 

[James Kanze]

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.