The Hash Function

The reason for the constant access time of an unordered associative container is the hash function. The hash function maps the key to its value (its hash 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, accessing the elements in the base case is also constant.

The hash function #

• is already defined for the built-in types like boolean, natural numbers, and floating point numbers.

• is available for std::string and std::wstring.

• generates, for a C string, const char a 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, we have to keep two requirements in mind: They need a hash function and an equality operator to be defined in order for them to be compared.