## HashFunction
## DescriptionA Hash Function is a UnaryFunction that is used by HashedAssociativeContainer : it maps its argument to a result of type The performance of a HashedAssociativeContainer depends crucially on its hash function. It is important for a Hash Function to minimize collisions, where a collision is defined as two different arguments that hash to the same value. It is also important that the distribution of hash values be uniform; that is, the probability that a Hash Function returns any particular value of type ## Refinement of## Associated types
## Notation## Definitions## Valid expressionsNone, except for those described in the UnaryFunction requirements. ## Expression semantics## Complexity guarantees## Invariants
## Models## Notes[1] Note that both of these requirements make sense only in the context of some specific distribution of input values. To take a simple example, suppose that the values being hashed are the six strings "aardvark", "trombone", "history", "diamond", "forthright", and "solitude". In this case, one reasonable (and efficient) hash function would simply be the first character of each string. On the other hand, suppose that the values being hashed are "aaa0001", "aaa0010", "aaa0011", "aaa0100", "aaa0101", and "aaa0110". In that case, a different hash function would be more appropriate. This is why HashedAssociativeContainer are parameterized by the hash function : no one hash function is best for all applications. ## See also |