Perfect Hash Function - Minimal Perfect Hash Function

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)ak). Order-preserving minimal perfect hash functions require necessarily Ω(n log n) bits to be represented.

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)

    “Among those few, out of the sun,
    The woodspurge flowered, three cups in one.

    From perfect grief there need not be
    Wisdom or even memory:
    One thing then learnt remains to me,—
    The woodspurge has a cup of three.”
    —Dante Gabriel Rossetti (1828–1882)

    “The fact remains that the human being in early childhood learns to consider one or the other aspect of bodily function as evil, shameful, or unsafe. There is not a culture which does not use a combination of these devils to develop, by way of counterpoint, its own style of faith, pride, certainty, and initiative.”
    —Erik H. Erikson (1904–1994)