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)
“He stood, a soldier, to the last right end,
A perfect patriot and a noble friend,
But most a virtuous son.
All offices were done
By him, so ample, full, and round
In weight in measure, number, sound,
As, though his age imperfect might appear,
His life was of humanity the sphere.”
—Ben Jonson (1572–1637)
“Our father has an even more important function than modeling manhood for us. He is also the authority to let us relax the requirements of the masculine model: if our father accepts us, then that declares us masculine enough to join the company of men. We, in effect, have our diploma in masculinity and can go on to develop other skills.”
—Frank Pittman (20th century)