Feature Overview

Data structures in the hash table family are all about establishing key–value relationships. I love abstracting all logic into key–value relations, so I'm quite fond of hash-table data structures as well.

-

Hash tables: A hash table is a method of accessing records by mapping keys to a position in the table via a hash function, supporting fast insertion and lookup. Hash tables do not guarantee the continuity of keys or values.

• Perfect hash tables: A perfect hash table is a hash table that maps keys to values without any collisions. This means every key has a unique hash value, and the hash function can directly locate the value for a given key, providing more efficient lookup performance.
• Minimal perfect hash tables: A minimal perfect hash table is a specially designed perfect hash table that stores key-to-value mappings in minimal space while guaranteeing no collisions. It is especially suitable for scenarios where the key set is static and known in advance.

Let's evaluate which hash table structure to pick based on the table's dynamism and the continuity of keys and values. Purely personal opinion.

Since hash tables waste a lot of memory, they are still the better choice in application scenarios with highly dynamic tables that undergo frequent deletions and modifications. Some of you might be wondering: is there any logical reasoning behind this? There actually is, but I'm too lazy to explain.

In application scenarios where key–value continuity is weak, the large amount of memory wasted by hash tables becomes somewhat unacceptable.

Wait, isn't the topic "minimal perfect hash tables"?

Minimal perfect hash tables have extremely narrow, almost singular application scenarios: they can be used if and only if the table relationship is completely static. But their advantages are also very prominent. First, the memory areas for keys and values are compact, with no waste. Second, the lookup time complexity for every key–value pair is O(1).

Whose Library to Plagiarize

First is gperf, GNU's perfect hash function generator. It can generate PHFs (perfect hash functions) and MPHFs (minimal perfect hash functions). The key point is that it's a GNU library, so it has the best long-term prospects. But for now, this library is extremely inefficient and doesn't support building large mapping tables.

Second is CMPH, a perfect hash function generator made by some Brazilian guys, supporting multiple algorithms. It claims to be a top-tier solution for building large hash mapping tables (that's just a claim). According to netizens' tests, it's not as efficient as their paper claims (but at least it can generate). In my own testing, this library is honestly too hard to use. For one thing, it's built as a framework, so the functional modules can't be used independently — once you add it, you bring in four algorithms at once. For another, the provided source code still has some bugs, and you need to patch a few places before it can be tested properly. Last and most importantly, there are hardly any comments in these guys' source code, making changes very difficult — you need to understand the whole library before touching it.||For a library-tweaking enthusiast like me, that's too big a hurdle; maybe the guys were also guarding against shady characters.||

Third is BobMPH, which requires a ladder (VPN) to access. I gave it that name myself, because the author is clearly a guy named Bob Jenkins, though I've never looked into who he is. The source code isn't released as a project or an archive; it's scattered across individual web pages, probably just archived directly on his server. Downloading it on Windows took quite a bit of effort. I haven't studied it in detail yet; if you need it for research, just ask me for the source code.

A Side Note

It originally started with a need to optimize the key–value mapping in a piece of business logic. Currently, it's a switch mapping generated from a macro table of my own invention, but that consumes a huge amount of ROM. I also absolutely hate the uncertainty of lookup time. Driven by these needs, I found minimal perfect hash tables.

I spent several days studying the implementation of "Second, CMPH" above, and was finally getting into the groove when a business bug interrupted me. After I went back and fixed the bug, I suddenly realized that hash-table-family relations simply don't fit my needs. I want keys to be int values and more numerous, and values to be trigger functions and fewer — something the hash table family is inherently incapable of. Of course, I could modify a library to make it work, but then it wouldn't be a hash table anymore. Why not find a more suitable structure?

Bob Jenkins, mentioned above, shares a very similar view to mine

Also, this dude's homepage is quite interesting. He mentions a little "get-rich trick": as long as you achieve an annual return of 10 points, after 25 years, you can multiply it tenfold! Home page, Bob Jenkins (burtleburtle.net).

Looks like a seasoned programmer