在设计字典之类的东西时推荐的数据结构?

你可以考虑一下 Directed Acyclic Word graph

就时间而言,它就像一个trie,可能比hash更好。不知道你从哪里得到了哈希的O(logn)时间。对于合理的散列,它应该是O(n),其中n是正在搜索的单词的长度。

1. 在最坏的情况下,在trie中查找数据的速度更快, O(m) 时间,与一个不完美的哈希表相比。不完美的哈希表可能会有密钥冲突。密钥冲突是将不同密钥映射到哈希表中相同位置的哈希函数。在不完全哈希表中,最坏的查找速度是 O(N) 时间,但更典型的是 O(1) ,与 O(米) 计算散列所花的时间。
2. 在trie中不存在不同键的冲突。
4. 当一个trie中添加了更多的键时,不需要提供散列函数或更改散列函数。
5. trie可以按键提供条目的字母顺序。

1. 在某些情况下,尝试查找数据的速度可能比哈希表慢,特别是直接在硬盘驱动器或其他辅助存储设备上访问数据时,与主内存相比,随机访问时间较长。

如果缺点是你可以忍受的,我建议你还是用trie。

资料来源: Wikipedia: Trie#As a replacement of other data structures

我想这是个大问题,嗯?也许可以试试看布卢姆过滤器?

http://en.wikipedia.org/wiki/Bloom_filter