统计单词的访问频度，我觉得散列表比Trie树快啊

cdsfiui

Trie树的介绍一般都会带一句说：寻找热门查询，300万个查询字符串中统计最热门的10个查询，可以用trie树

但是我感觉，用散列表，类似C++的unordered_map，每个单词进来，计算一次散列值，value+1就行了。
如果用trie树实现，那么每次查找都要经过若干个节点的跳转和比较，这个比计算一次hash要重多了。

为什么说，“”寻找热门查询，300万个查询字符串中统计最热门的10个查询”这样的问题更适合于用trie树呢？
求解释。

bruceteen

为什么总有人觉得hash快？遇到 hash冲突、二次冲突（取决于实现）、容量不足 等问题时特别耗时。
而 trie 嘛，我觉得缺点也大，第一它限定了字符（如果只考虑26个字母还行，如果是unicode，那只能分解成字节考虑了），第二是效率，它内存结构松散（类似于list），内存页面切换比较耗时。
以上皆废话，你为什么不写两段代码实际测量一下耗时？

lxyscls

回复 1# cdsfiui

Trie比Hash更节约内存，但是如果都是要查找Top10，我觉得不额外维护个Heap貌似都不会快，Hash和Trie都没有Rank的概念
@windoze 猫大来答一发

shang2010

hash本质是一个内存池，大数组

windoze

Hash和Trie没有顺序啊？你要找top 10的话它们能帮你干什么呢？你总归得有一个ordered数据结构才能找top N不是，要不然你得把所有entry都遍历一遍才知道哪个是top。
对于找top N这种活，heap貌似是最省的，如果你真的特别在乎log N的话试试斐波那契堆吧。
再说你可以一边heap一边hash/trie，这两个东西又不会打架。

cokeboL

关键不是这个。
关键是输入不是单个key，比如关键字 "abc"，但输入的是 "xxabcde"，trie包含了从"xxabcde"中找出abc的过程，map没有这个过程

cokeboL

常见的场景是敏感词过滤，用trie是为了找出一个字符串中的所有敏感词