[rob-p]

Uhh, there is nothing at all "academic" about pthash, (or phast, or ptrhash), apart from the fact that they also described their ideas in papers. All of those tools work on massive sets of data, support massively parallel construction, and support external memory construction. They are all well-engineered libraries and not "academic" in any derogatory sense.

[rurban]

They are academic, as they are not practical. Most of the algos produce random graphs, ie random indices. The given index has nothing to do with the keys.

They give the hash sizes without the needed ordering tables, they don't even produce those seperate tables. Because academic competition. So in reality you'd need O(2n) more time and O(n) space. Without random key access it gets slow. Then there are no checks for false-positives. You'd need fast random access to the keys then. Then they could not compile to static sourcecode.

All this is pure fantasy for real products. gperf, nbperf are practical. They store the keys, and give a proper search function. They produce C code. pthash, ptrhash, cmph not. It's complicated because the keys can be in a file, a stream, a database, with just linear access or random access. I'm adding options to either store the ordering table, or emit an ordered keys file. And I compile to C or C++ code. And I allow several hash algos, not just random seeds. Jenkins hash is mostly good, but there are better, depending on the keys.

[rob-p]

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.

[rurban]

See, your academic defense lacks any practicalism. I know how academics define it, that's why you barely cannot them use as is.

With some algos you can export the ordering tables trivially, but nobody does. Because someone else's problem.

[Algofish]

What exactly would be “practical” about exporting an ordering table when your application doesn’t need it? That’s the whole point of minimal perfect hashing — to provide a compact, collision-free mapping from a known key set to [1..n], without extra structures unless they’re required.

If you do need to preserve key order, that’s a different problem entirely — and one that’s already well-studied. You’d use an order-preserving MPHF (OMPHF), not a standard MPHF. There’s a large body of literature on this (e.g. “Order Preserving Minimal Perfect Hashing” – VTechWorks, ).

You seem to conflate the two problems — building an efficient MPHF versus building an OMPHF. Both are useful, but for different goals. Dismissing something as “academic” because it solves a different problem efficiently isn’t a fair critique — it’s misunderstanding what it’s optimizing for. It’s like saying “Bloom filters aren’t practical because they don’t store the original data.”