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)
“Sinclair Lewis is the perfect example of the false sense of time of the newspaper world.... [ellipsis in source] He was always dominated by an artificial time when he wrote Main Street.... He did not create actual human beings at any time. That is what makes it newspaper. Sinclair Lewis is the typical newspaperman and everything he says is newspaper. The difference between a thinker and a newspaperman is that a thinker enters right into things, a newspaperman is superficial.”
—Gertrude Stein (1874–1946)
“Advocating the mere tolerance of difference between women is the grossest reformism. It is a total denial of the creative function of difference in our lives. Difference must be not merely tolerated, but seen as a fund of necessary polarities between which our creativity can spark like a dialectic.”
—Audre Lorde (1934–1992)