Hash and Equals
Explore how to implement hash and equality functions for C++ unordered containers. Understand the importance of distributing keys evenly among buckets to optimize lookup times, and how to maintain the contract between equals and hash for user-defined types.
We'll cover the following...
Hash functions
The hash value, which can be computed in constant time with respect to the size of the container, determines which bucket an element will be placed in. 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 of the keys in the bucket.
If two keys are equal, they are required to generate the same hash value. However, it's perfectly legal ...