A minimal perfect hash function is a perfect hash function that maps n keys to n consecutive integers—usually or . A more formal way of expressing this is: Let j and k be elements of some finite set K. F is a minimal perfect hash function iff F(j) =F(k) implies j=k and there exists an integer a such that the range of F is a..a+|K|−1. It has been proved that a general purpose minimal perfect hash scheme requires at least 1.44 bits/key. However the smallest currently use around 2.5 bits/key.
A minimal perfect hash function F is order preserving if keys are given in some order a1, a2, ..., and for any keys aj and ak, j<k implies F(aj)
A minimal perfect hash function F is monotone if it preserves the lexicographical order of the keys. Monotone minimal perfect hash functions can be represented in very little space.
Read more about this topic: Perfect Hash Function
Famous quotes containing the words minimal, perfect and/or function:
“For those parents from lower-class and minority communities ... [who] have had minimal experience in negotiating dominant, external institutions or have had negative and hostile contact with social service agencies, their initial approaches to the school are often overwhelming and difficult. Not only does the school feel like an alien environment with incomprehensible norms and structures, but the families often do not feel entitled to make demands or force disagreements.”
—Sara Lawrence Lightfoot (20th century)
“And then at last our bliss
Full and perfect is,
But now begins; for from this happy day
The old Dragon underground,
In straiter limits bound,
Not half so far casts his usurped sway,
And, wroth to see his kingdom fail,
Swinges the scaly horror of his folded tail.”
—John Milton (1608–1674)
“The uses of travel are occasional, and short; but the best fruit it finds, when it finds it, is conversation; and this is a main function of life.”
—Ralph Waldo Emerson (1803–1882)