by rob-p | 2025-10-25 21:26:22+00:00
Your statement conveys a lack of knowledge of the main purpose of minimal perfect hash functions, as compared to generic/general hash tables (which are a more general, but therefore, in some cases, less efficient data structure). The main point of the MPHF is not to be order preserving, or to provide a prescribed function from the keys to [1...n]. Rather, it is to provide a collision free mapping between the set of keys and [1..n].

The fact that minimal perfect hashes do not reject alien keys is not an "academic" limitation, it is implicit in the definition of the problem being solved. In fact, the relevant space bounds cannot be satisfied if you either (1) must reject elements not in the key set at the time of construction or (2) require a prescribed order be assigned to the specific keys.

However, even given your misapprehensions about the purpose of minimal perfect hash functions, your statement about how they are not useful in practice is also simply false. You are describing uses for classical hash tables that store their key set explicitly and in their entirety. These serve an entirely different purpose in application to minimal perfect hash functions.

Minimal perfect hash functions are particularly useful when you know the key set ahead of time and are certain that only valid keys will be queried. In this case, the values can be stored in a flat array (in the order prescribed by the MPHF) and the cost of the hash itself is only ~2 bits/key. So the total storage is the minimal storage for the values + a small overhead to allow constant-time access to the value for a given key. If you need to reject alien keys, then you can of course store those as well. In that case, the MPHF costs the storage cost for the key set + value set + ~2 bits/key; still smaller than most existing dynamic hash tables.

In many cases, you don't need an ordering table. If you are allowed to permute the keys and all you require is O(1) access to the corresponding index for a key, then the additional ordering table is unnecessary overhead. On the other hand, if you need, for some reason, to remap the keys to be in a specific order, then this is easy simply by iterating over the keys and observing what indices they yield.

Many times, people wish to use MPHFs for non-static purposes (i.e. where the key set is not known at compile time). Consider e.g. in network mapping (https://dl.acm.org/doi/abs/10.1109/tnet.2018.2820067), or in taxonomic classification (https://academic.oup.com/bioinformatics/article/34/1/171/393...) or in k-mer indexing (https://academic.oup.com/bioinformatics/article/34/13/i169/5... or https://academic.oup.com/bioinformatics/article/38/Supplemen...). Moreover, MPHFs form the basis for near-optimal static filters, by storing fingerprints of the keys in the indexed spots (https://www.sciencedirect.com/science/article/pii/S0166218X1...).

Simply because a particular MPHF construction doesn't suit the problem you have in mind doesn't mean it's not useful or that it's "academic". MPHFs have plenty of uses, some without the need for a key routing or key-reordeing table. Other times, one needs the keys in a particular order and even then MPHFs are very useful because if the key set is static, the MPHF + the rerouting table is often still smaller than alternative dynamic hash table approaches while being similarly fast for query. They can be built in an parallel, external memory, and cache efficient manner.

The argument that MPHFs are "academic" and not useful because they don't adhere to constraints to which they are not intended to adhere is like arguing that a hammer is not useful because you cannot use it to tighten philips head screws.