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. Instead, the access time in the bucket is linear, meaning that the overall access time of a value depends on the number of collisions in the bucket.

The Hash Function

A hash function

• is available for the fundamental data types, such as booleans, integers, and floating points.
• is available for the data types std::string and std::wstring,
• creates a hash value of the pointer address for C string const char*
• can be defined for user-defined data types.

By applying the theory to user-defined data types, which we want to use as a key of an unordered associative container, our data type needs to fulfill two requirements:

1. It should have a hash function and
2. an equality function.

struct MyHash{
  std::size_t operator()(MyInt m) const{
  std::hash<int> hasVal;
  return hashVal(m.val); }
};