C中沒有線性搜索的快速dictonary

Question

如何在C中沒有線性搜索的情況下快速dictonary（String =>指針和Int =>指針）？我需要一些（或更多）代碼行，而不是庫，它必須可以在閉源軟件（LGPL，...）中使用。

Answer 1

使用Hash Table。散列表將具有恆定時間查找。 Here are some excerpts in C和an implementation in C (and Portuguese :)。

Answer 2

您需要實現Hash Table，它使用散列碼存儲對象。查找時間是不變的。

甲Binary Tree可以遍歷和的log（n）時間查找的元素。

Answer 3

Ternary Search Tree是出於這個使命。

Answer 4

如果你的字符串會很長，你不能認爲「哈希表」是恆定的時間！運行時間取決於字符串的長度！對於長字符串，這會導致問題。另外，你有碰撞問題，表太小或散列函數太差。

如果你想使用哈希，請看看karp-rabin。如果你想要一個算法依賴於你正在搜索的單詞的大小，請看看aho-corasick。