Trie, Hash, MinADFA
Trie的搜索复杂度是 O(length(strkey)),Hash表,计算Hash的复杂度也是O(length(strkey)),但是,仔细分析一下:
- Trie因为每读一个字符,要做一次状态转移,就有一次(随机)访存操作,计算 strkey 的 Hash 不需要每个字符都随机访存,从这一点看,Hash胜出
- Hash 可能会有冲突,而 Trie 没有冲突,这一点,Trie 胜出
- 可以在 Trie 上应用 DFA Minimization 算法,生成一个 Minimum Acyclic DFA,再加一些额外算法,可以节省更多内存(有可能超过100倍),同时可以用 O(length(strkey)) 的时间复杂度把 strkey 映射到它在 MinADFA 中的字典序的序号。