The Hash Function
The reason for the constant access time of the unordered associative container is the hash function. The hash function maps the key to its value the so-called has value. A hash function is good if it produces as few collisions as possible and equally distributes the keys onto the buckets. Because the execution of the hash function takes a constant amount of time, the access of the elements is in the base case also constant.
The hash function
- is already defined for the built-in types like boolean, natural numbers and floating point numbers,
- is available for
- generates for a C string
const chara hash value of the pointer address,
- can be defined for user-defined data types.
For user-defined types which are used as a key for an unordered associative container, you have to keep two requirements to keep in mind. They need a hash function and have to be comparable to equal.