Associative Containers: The Hash Function
The hash function maps a potentially infinite number of keys onto a finite number of buckets. What is the strategy of the C++ runtime, and how can you tailor it to your needs? Let’s disucss these questions further.
We'll cover the following...
Which requirements must the key and the value of an unordered associative container fulfill?
The key must be
- comparable with the equality function,
- available as a hash value,
- copyable and moveable.
The value must be
- by default constructible,
- copyable and moveable.
A hash function is good if two factors are present: one, if the mapping from the keys to the values produces few collisions; two, if the hash values are uniformly distributed among the buckets. Since the execution time of the hash function is constant, the access time of the elements is also constant. ...