C++ High Performance

Hash and equals

The hash value, which can be computed in constant time with respect to the size of the container, determines in which bucket an element will be placed. Since it's possible that more than one object will generate the same hash value and therefore end up in the same bucket, each key also needs to provide an equals function, which is used to compare the key we are looking for with all the keys in the bucket.

If two keys are equal, they are required to generate the same hash value. However, it's perfectly legal for two objects to return the same hash value while not being equal to each other.

A good hash function is quick to compute and will also distribute the keys evenly among the buckets in order to minimize the number of elements ...