特性簡介#
哈希表系列數據結構主打鍵值對關係的建立，我非常喜歡把一切邏輯都抽象為鍵值關係，所以哈希表數據結構也是我很喜歡的。
- 哈希表的特性：哈希表是一種通過哈希函數將鍵（key）映射到表中一個位置來訪問記錄的方法，以支持快速插入和搜索。哈希表不保證鍵或值的連續性。
- 完美哈希表的特性：完美哈希表是一種哈希表，它可以在沒有任何衝突的情況下將鍵映射到值。這意味著每個鍵都有一個唯一的哈希值，並且哈希函數能夠直接定位到鍵對應的值，提供了更高效的查找性能。
- 最小完美哈希表的特性：最小完美哈希表是特別設計的完美哈希表，它能夠在保證沒有任何衝突的前提下，使用最小的空間來存儲鍵到值的映射關係。這種哈希表特別適合於鍵的集合是靜態且已知的場合。
讓我們使用表的動態度和鍵值的連續性對選擇那種哈希表結構進行評判，純個人觀點。
由於哈希表非常浪費內存空間，所以在高動態表刪改的應用場景下，哈希表仍然是更好的選擇。
可能有寶寶會疑惑了，這有什麼推理關係嗎？其實是有的，但我懶得解釋了。
而在鍵值值連續性較弱的應用場景下，哈希表浪費大量內存空間，就有些不可接受了。
| 動態度低 | 動態度高 | |
|---|---|---|
| 鍵值連續性弱 | 完美哈希表 | 哈希表 |
| 鍵值連續性強 | 哈希表 (優)/ 完美哈希表 | 哈希表 |
主題不是 "最小完美哈希表" 嗎？
最小完美哈希表的應用場景非常狹窄甚至於單一，當且僅當表關係完全不動態時可以使用最小完美哈希表。但最小完美哈希表的優勢也非常突出，首先是鍵和值的內存區域是緊湊的，不會產生浪費；其次是每個鍵值對的查找時間複雜度都是 O (1)。
（a） 完美哈希函數。（b) 最小完美哈希函數。
剽竊誰的庫#
其一是gperf，這是 GNU 的完美哈希函數生成器，可以生成 PHF (完美哈希函數) 和 MPHF (最小完美哈希函數)，關鍵這是 GNU 的程序庫，所以長期來看是前景最好的。但是僅就當下來說，這個庫一是效率極低，而且不支持建立大的映射表。
其二是CMPH，這是巴西哥們做的完美哈希函數生成器，支持多個算法。號稱是建立大的哈希映射表的頂級方案 (僅僅是號稱)，而據網友測試，效率並非他論文裡號稱的那麼高效 (但好歹能生成)。
而據我自己測試下來，這個庫屬實是太難用了。一方面他做了一個框架，功能模塊不能單獨使用，一加就是四個算法。另一方面給出的源碼中還有些許 bug，要小改幾處才能正常測試。最後最重要的是，這幾個哥們源碼裡面就沒幾處註釋，改起來非常困難，要改動這個庫需要整個理解。|| 對於我這樣的改庫愛好者太困難了，可能哥們也出於防備小人的考慮。||
其三是BobMPH需要梯子才能上，這是我給起的名字，因為作者老哥顯然叫 Bob Jenkins，沒具體了解過這是個誰。源碼也沒有以工程或者壓縮包形式發布，在一個一個獨立的網址裡，應該是這哥們直接放在伺服器上作為存檔，windows 下下來還是花了一番功夫的。目前還沒有細看過，有研究需求可以直接找我要源碼。
另記#
最初是需要優化一下業務邏輯的鍵值映射關係，目前是我自創的宏表翻譯 switch 映射，但是這樣導致 rom 消耗巨大。同時我非常厭惡查找時間的不確定性，基於這些需求找到了最小完美哈希表。
我花了好幾天時間研究上述 **"其二 CMPH"** 的實現，在終於漸入佳境時被一個業務上的 bug 打斷。回去修完 bug，突然意識到哈希表系的關係完全不符合我的需求，我希望鍵是 int 值而且更多、而值是觸發函數而且較少，哈希表系天生是做不到的。當然也可以改庫實現，但那已經不是哈希表了，何不找一個更合適的結構呢？
上面提到的 Bob Jenkins 與我的看法很像
同時這位老哥的首頁也非常有意思Home page, Bob Jenkins (burtleburtle.net)，
看起來是資深程序員
此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://www.yono233.cn/posts/shoot/24_7_20_%E7%BB%9D%E5%AF%B9%E6%98%A0%E5%B0%84%E2%80%94%E2%80%94%E6%9C%80%E5%B0%8F%E5%AE%8C%E7%BE%8E%E5%93%88%E5%B8%8C%E8%A1%A8