It is a useful data structure for representing static search sets . Static search sets occur frequently in software system applications. Typical static search sets include compiler reserved words, assembler instruction opcodes, and built-in shell interpreter commands. Search set members, called keywords , are inserted into the structure only once, usually during program initialization, and are not generally modified at run-time. Numerous static search structure implementations exist, e.g. , arrays, linked lists, binary search trees, digital search tries, and hash tables.
Different approaches offer trade-offs between space utilization and search time efficiency.
For example, an n element sorted array is space efficient, though the average-case time complexity for retrieval operations using binary search is proportional to log n . Conversely, hash table implementations often locate a table entry in constant time, but typically impose additional memory overhead and exhibit poor worst case performance. Minimal perfect hash functions provide an optimal solution for a particular class of static search sets. The actual memory allocated to store the keywords is precisely large enough for the keyword set, and no larger . For most applications it is far easier to generate perfect hash functions than minimal perfect hash functions.