哈希表查找 - 與完美哈希，在C

Question

我有一個C語言應用程序，我需要做表查找。

條目是字符串，全部在運行時開始已知。該表初始化一次，然後多次查找。表格可以更改，但基本上就好像應用程序重新開始。我認爲這意味着我可以使用完美哈希？可以花費一些時間進行散列表初始化，因爲它只發生一次。

將會有3到100,000個條目，每個條目都是唯一的，我估計80％的案例將少於100個條目。在這些情況下，簡單樸素的查找「足夠快」。 （==沒有人抱怨）

但是，在有10k +條目的情況下，樸素方法的查找速度是不可接受的。爲C中的字符串提供良好的基於​​散列表的查找性能的好方法是什麼？ 假設我沒有Boost/etc等第三方商業圖書館。我應該使用什麼散列算法？我該如何決定？

Answer 1

生成一個完美的散列並不是一個簡單的問題。有專門負責這項任務的圖書館。 在這種情況下，最流行的可能是CMPH。儘管如此，我還沒有使用它，所以無法幫助。 gperf是另一個工具，但它需要在編譯時知道字符串（你可以通過編譯.so和加載來解決它，但有點矯枉過正）。

但坦率地說，我會至少嘗試去二進制搜索。只需使用qsort對陣列進行排序，然後使用bsearch進行搜索（或滾動您自己的）。自C89以來，這兩者都是stdlib.h的一部分。

Answer 2

如果一個天真的（我認爲你的意思是線性的）方法對於100個條目是可以的（所以50個比較平均完成），那麼二進制搜索對於100,000個條目就足夠了（它最多需要17次比較）。

所以我不打擾哈希，但只是在啓動時（例如使用qsort）對二進制搜索進行排序（例如使用bsearch）來查找條目。

Answer 3

如果（最大）表的大小是已知的，則帶有鏈接的純哈希表很容易實現。大小開銷每個項目只有兩個整數。使用合理的散列函數平均只需要每個查詢1.5個探針，這對於100％加載的表來說是這樣。

構建一個完美的散列只有在你的數據沒有改變時纔是可行的。一旦它發生變化，你將不得不重新計算和重新組合，這比做一些額外的比較要昂貴得多。