LEDA also contains parameterized data types requiring a hash function and an equality test (operator==) for the actual type parameters. Examples are dictionaries implemented by hashing with chaining ( _dictionary<K,I,ch_hashing>) or hashing arrays (h_array<I,E>). Whenever a type T is used in such a context, e.g., in h_array<T,...>there must be defined
Hash maps the elements of type T to integers. It is not required that Hash is a perfect hash function, i.e., it has not to be injective. However, the performance of the underlying implementations very strongly depends on the ability of the function to keep different elements of T apart by assigning them different integers. Typically, a search operation in a hashing implementation takes time linear in the maximal size of any subset whose elements are assigned the same hash value. For each of the simple numerical data types char, short, int, long there is a predefined Hash function: the identity function.
We demonstrate the use of Hash and a data type based on hashing by extending the example from the previous section. Suppose we want to associate information with values of the pair class by using a hashing array h_array<pair,int> A. We first define a hash function that assigns each pair (x,y) the integral part of the first component x
int Hash(const pair& p) { return int(p.x); }
and then can use a hashing array with index type pair
h_array<pair, int> A;