特性简介

哈希表系列数据结构主打键值对关系的建立，我非常喜欢把一切逻辑都抽象为键值关系，所以哈希表数据结构也是我很喜欢的。

-

哈希表的特性：哈希表是一种通过哈希函数将键（key）映射到表中一个位置来访问记录的方法，以支持快速插入和搜索。哈希表不保证键或值的连续性。

• 完美哈希表的特性：完美哈希表是一种哈希表，它可以在没有任何冲突的情况下将键映射到值。这意味着每个键都有一个唯一的哈希值，并且哈希函数能够直接定位到键对应的值，提供了更高效的查找性能。
• 最小完美哈希表的特性：最小完美哈希表是特别设计的完美哈希表，它能够在保证没有任何冲突的前提下，使用最小的空间来存储键到值的映射关系。这种哈希表特别适合于键的集合是静态且已知的场合。

让我们使用表的动态度和键值的连续性对选择那种哈希表结构进行评判，纯个人观点。

由于哈希表非常浪费内存空间，所以在高动态表删改的应用场景下，哈希表仍然是更好的选择。 可能有宝宝会疑惑了，这有什么推理关系吗？其实是有的，但我懒得解释了。

而在键值值连续性较弱的应用场景下，哈希表浪费大量内存空间，就有些不可接受了。

主题不是"最小完美哈希表"吗？

最小完美哈希表的应用场景非常狭窄甚至于单一，当且仅当表关系完全不动态时可以使用最小完美哈希表。但最小完美哈希表的优势也非常突出，首先是键和值的内存区域是紧凑的，不会产生浪费；其次是每个键值对的查找时间复杂度都是 O(1)。

剽窃谁的库

其一是gperf，这是 GNU 的完美哈希函数生成器，可以生成 PHF(完美哈希函数)和 MPHF(最小完美哈希函数)，关键这是 GNU 的程序库，所以长期来看是前景最好的。但是仅就当下来说，这个库一是效率极低，而且不支持建立大的映射表。

其二是CMPH，这是巴西哥们做的完美哈希函数生成器，支持多个算法。号称是建立大的哈希映射表的顶级方案(仅仅是号称)，而据网友测试，效率并非他论文里号称的那么高效(但好歹能生成)。 而据我自己测试下来，这个库属实是太难用了。一方面他做了一个框架，功能模块不能单独使用，一加就是四个算法。另一方面给出的源码中还有些许 bug，要小改几处才能正常测试。最后最重要的是，这几个哥们源码里面就没几处注释，改起来非常困难，要改动这个库需要整个理解。||对于我这样的改库爱好者太困难了，可能哥们也出于防备小人的考虑。||

其三是BobMPH需要梯子才能上，这是我给起的名字，因为作者老哥显然叫 Bob Jenkins，没具体了解过这是个谁。源码也没有以工程或者压缩包形式发布，在一个一个独立的网址里，应该是这哥们直接放在服务器上作为存档，windows 下下来还是花了一番功夫的。目前还没有细看过，有研究需求可以直接找我要源码。

另记

最初是需要优化一下一个业务逻辑的键值映射关系，目前是我自创的宏表翻译 switch 映射，但是这样导致 rom 消耗巨大。同时我非常厌恶查找时间的不确定性，基于这些需求找到了最小完美哈希表。

我花了好几天时间研究上述"其二 CMPH"的实现，在终于渐入佳境时被一个业务上的 bug 打断。回去修完 bug，突然意识到哈希表系的关系完全不符合我的需求，我希望键是 int 值而且更多、而值是触发函数而且较少，哈希表系天生是做不到的。当然也可以改库实现，但那已经不是哈希表了，何不找一个更合适的结构呢？

上面提到的 Bob Jenkins 与我的看法很像

同时这位老哥的主页也非常有意思，他提到了一个致富"小妙招"，只要实现10个点的年利，经过25年，就可以翻10倍耶Home page, Bob Jenkins (burtleburtle.net)，

看起来是资深程序员