「編譯時哈希表」用C

我執行在C的邏輯塊即是這樣的（傳譯員）：「編譯時哈希表」用C

if <input string> in <list of pre-defined constant strings> 
    do_a_predefined_action() 
else 
    do_something_else(<input string>)

我首先想到的是一個哈希表，但如果不變字符串在編譯時是已知的，在運行時必須手動初始化散列表似乎有點浪費。

其他想法我已經包括靜態初始化已知散列（ick ...）的散列表結構，然後像正常一樣簡單地使用它。另一個是嵌套的switch塊，它將提供O(log n)查找時間（不像散列表一樣快）。

實現查找預定義字符串集合的最佳方式是什麼？我還沒有看到什麼解決方案？優雅會比速度更受歡迎。

我只是在啓動時建立哈希表並完成它。之後，如果您認爲啓動時間因此無法接受，那麼您可以編寫某種預處理器來預先構建哈希表以供列入。 –

@ 500-InternalServerError：如果沒有更好的路線，這就是我打算去的路。我對我的代碼非常強迫，而且啓動事情似乎很難看。感謝您的輸入。 :-) –

您可以使用類似gperf或Bob Jenkin's Minimal Perfect Hash代碼來生成一個（可能是最小的）Perfect Hash Function，這將字符串映射到值，以後可以switch上。

2014-03-30 12:42:01 Hasturkun

如果輸入字符串不在字符串的常量列表中，這是如何工作的？你仍然需要檢查字節匹配情況，以防你有一個錯誤的命中。 –

@Anonymous：默認情況下gperf會在匹配後執行額外的'strcmp'來驗證。另一個不（但這不應該太難實施）。 – Hasturkun

我不會太擔心在程序啓動時初始化散列表的成本。這種過早優化的風險。這就是說，...

既然你知道所有的字符串，你可以看看爲這些字符串構造一個完美的散列。有許多工具可用於嘗試多種可能的哈希算法，並選擇最適合數據的哈希算法。這將導致靜態初始化路由。儘管你已經評論過這個策略的「ick」。如果速度問題非常重要，我鼓勵您重新考慮它。

其實我也認爲我的PostScript解釋的，其在啓動時初始化systemdict哈希表的情況下就此問題。要考慮的另一條路線是將表緩存在文件中。用於初始化的僞代碼將如下所示：

check for cached file 
if file exists, 
    load it. 
if file does not exist, 
    initialize table manually. 
    save table to file.

2014-03-30 12:43:20

雖然@Hasturkun先到那裏並回答了我的問題，但您的回答很有意義，我*過早地進行了優化。謝謝您的幫助！ –

回答