摘自wikipedia的trie词条

在计算机科学中,trie,又称前缀树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

摘自wikipedia的Hash词条

散列函数(或散列算法,英语:Hash Function)是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。

用同样的字符串数组来各自构造一万以上元素的Hash和Trie

 1 # gem dependencies: algorithms, nokogiri
 2 %w[benchmark algorithms open-uri nokogiri].map &method(:require)
 3 
 4 string_array_for_insert = Nokogiri(open('http://www.douban.com').read).text.split("\n").map(&:strip).uniq
 5 string_array_for_insert = (string_array_for_insert*100).map {|i| i.split(//).shuffle.join }
 6 hash = string_array_for_insert.inject({}) {|h, i| h[i] = rand(100000); h }
 7 trie = Containers::Trie.new; string_array_for_insert.each {|i| trie[i] = rand(100000) }
 8 
 9 Benchmark.bm(8) do |x|
10   x.report("hash:") { string_array_for_insert.each {|i| hash[i] } }
11   x.report("trie:") { string_array_for_insert.each {|i| trie[i] } }
12 end
13 
14 =begin
15                user     system      total        real
16 hash:      0.010000   0.000000   0.010000 (  0.007240)
17 trie:      0.490000   0.010000   0.500000 (  0.503553)
18 =end

由以上判断,Hash算法的O(1)远比Trie的O(m)快 (m为键的最大长度),如非类搜索提示的字符串匹配等应用,一般的键值对采用Hash可以保证最快查找单个元素。