算法有趣的地方在于，可以用不同的方式处理同一个问题，并且总有更好的方法。比如拼写检查。
拼写检查大体是这样的，给出一个字典文件，给出一个比对文件。比对文件里的单词，如果某个单词不在字典文件里的话，就认为拼写错误。要做的就是找出比对文件里所有拼写错误的单词。
暴力破解 (brute force)
最直观的方法，就讲文件里的单词一一同字典里的单词做比较，如果不在字典里，就输出。最简单，也最费时。
假设字典文件一共有 nd 个字符，用于比对的文件有 nt 字符，复杂度则为 O(nd * nt)。
我们看一下运行速度，测试用的字典里大约有 14 万个单词，用作比对的文件大约有 12 万个单词。 用时将近 3 分钟。显然速度太慢，需要优化。
单词查找树 (Trie)
我们知道，如果给出的单词以 a 开头，那么字典里以其他字母开头单词，就不需要我们做比较了。就好比二叉树查找，每次查找，总是可以丢掉不符合要求的那一半。 收到二叉树的启发，我们可以使用一种叫做 Trie 的多叉树来实现。
假设字典里有 ab, ac, c, d 这四个单词，生成的 trie 会是如下形状（t1、t2 只是表述，方便做讨论）：
root(t1)
/ \ \
a(t2) c(t3) d(t4)
/ \
b(t5) c(t6)
做检查的时候，需要从跟节点，一级一级的向下找。 假设我们查找"ad"，根节点的子节点 t2 的值就是 a，第一个字母匹配成功了。我们再匹配第二个字节 d，t2 的子树里，没有 d 这个字母，匹配失败。则 ad 为一个错误的拼写。 只有当我们匹配了单词的每一个字母，并且最后一个字母是结尾字母，那么这个单词才是在字典中存在的。
使用同样输入只花了不到 1.3 秒的时间，快了上百倍。
哈希表 (Hash Table)
拼写查找，要求的是插入和查找速度快，Hash Table 刚好符合要求。 同样的数据，只用了 0.14 秒，比 trie 的实现快了将近 10 倍。 具体实现
Bloom Filter
Hash Table 从速度上来说，已经是极限了，看起来是最适合的算法。但在某些场景下，依然有更好的方法 -- Bloom Filter！
Bloom Filter 相对于 Hash Table 来说，最大的优势就是，Bloom Filter 不需要存完整的 key (比如单词)，会更节约存储空间。 Bloom Filter 将一组 key（比如单词）通过多个哈希方程映射到一个数组内，并可以根据这个数组来判断这个单词是否已经被插入了。
算法的大体思路如下： 初始化一个 n 个 bit 的数组 arr，插入某个值时，我们通过哈希方程，得到对应的 index，将数组这个位置设为 1。 假设我们使用 2 个哈希方程 h1, h2，我们会得到两个 index（可能是 1 个），我们就将数组的这两个位置设为 1。
查找的时候，用所有的哈希方程，得到对应的 index，然后检查数组在这些位置上，是否均为 1，如果均为 1，则认为这个值被插入过。
伪代码如下：
require 'bitarray'
class BloomFilter
attr_accessor :arr
def initialize
self.arr = BitArray.new(n)
end
def insert(key)
arr[h1(key)] = 1
arr[h2(key)] = 1
end
def include?(key)
arr[h1(key)] == 1 && arr[h2(key)] = 1
end
# BloomFilter 会有多个哈希函数，2 个只是为了说明算法的工作原理。
def h1(key)
# xxx
end
def h2(key)
# xxx
end
end
Bloom Filter 虽然大大的节省了空间，但却有一定的概率出错 (false positive)，以为哈希方程有一定的概率会产生冲突 (collision)，既当查找时，一个值没有被插入，但却被误认为是插入过了。可以通过更长的数组和更多的哈希方程来解决这个问题。
Bloom Filter 还有一个弊端，就是不能做删除操作。不过可以通过给每一位加上个 counter 来解决，就是所谓的 Counting Bloom Filter，具体可以看这篇文章，这里就不详述了。
同样的输入，需要 0.11 秒。
执行速度对比
SpellChecker
user system total real
brute_force 162.660000 1.560000 164.220000 (168.961906)
by_trie 1.160000 0.100000 1.260000 ( 1.305419)
by_hash_table 0.140000 0.000000 0.140000 ( 0.145828)
by_bloom_filter 0.100000 0.010000 0.110000 ( 0.108583)
参考
叫作 Trie 的多叉树其实就是实现数据库索引用到的 B+ 树（多叉树），查询的时间复杂度是 O(log n)，它的优势是范围查询（比如楼上提到的拼写建议）。
为什么不用查找效率最好二叉树？因为在硬盘上顺序读比随机读快，并且 B+ 树深度比二叉树少的多，在查询的时候执行的顺序读比随机读多，所以 B+ 树更适合。
拼写检查的实际需求是 KV 查询，B+ 树并不合适。哈希表 (Hash Table) 的 KV 查询时间复杂度是 O(1) ，它才是最好的选择。
Bloom Filter 是在哈希表的基础上，压缩信息，加速查询。这种压缩是有损数据压缩，丢失了一些信息，所以带来了可能出错的问题。
hooopo
回复
嗯，都是类似的问题。bloom filter 还有一个经典的应用是过滤弱密码。bloom filter 可以把很多的数据都“存”在内心里，查起来快，redis 就 bloom filter 的插件。
alixiaomiao
回复
对 我理解错了 B 树也是多叉树 它更接近 B+ 树 B 树和 B+ 树，本质上都是一样的，只是 B+ 树所有的根节点和枝节点上只保存关键字索引和其子节点指针，所有的数据信息都被保存到了叶子节点，这样每个枝节点可以存储更多的数据，从而降低树的层级高度，并且所有的叶子节像是一个链表一样，指向右边的叶子节点，从而可以有效加快检索效率，如果需要遍历所有的数据，只需要遍历叶子节点链式结构即可，方便且高效。
- Trie 能给出拼写建议，类似搜索引擎上搜索词提示，当然也能检查词汇是否存在。很节约储存空间。
- HashTable 只能判断词汇是否存在，不能给出拼写建议
- 布隆过滤器用多个哈希函数将结果映射在 bitmap 上，用来判断词汇是否存在，不能给出拼写建议。节约空间，速度也快。
- B 树也能实现 trie 树的效果，且几乎没有差别（不限制子节点数量）。只不过 B 树为磁盘读取量身定做，可按操作系统页的大小来存数据，尽量减少磁盘 IO 次数，更加强大复杂。
拼写检查用 Trie 有好处，因为在你还没写完某个词汇时，就可能判断出这个词汇不存在，不用写完了才告诉你。
early
回复
我没想到 B 树要怎么做拼写检查。。。
B 树和 Trie 不一样的地方是，Trie 没有深度约束，B 树有。用 B 树的话，就要把 com(组件对象模型)，cool，computer 都存到叶子上。。。
B 树还有一个 order 的约束，在单词上，order 只能为 26，那就是 13 到 26，空间也会有大量的浪费。
像 com(组件对象模型)，computer 这种，在 B 树似乎要村两次？
lanzhiheng
回复
这篇文章写的不怎么样（好吧，我偷懒了，没有再改改。。。
Hash 是准确的，准确的代价就是需要更多的存储空间。存储空间的代价有两个，一个是存储空间本身，一个是要分几次才能拿到内存里。
BloomFilter 是一个不准的 hash table。
比如输入一个 key，经过 hash function，得到一个 index，将 arr 的 index 设置为 1，既 arr[index] = 1，
查找的时候，将输入通过 hash function 转化为数组的 index，如果 arr[indexe] 存在，就认为这个值插过了。
hash function 有一定的冲突的概率，比如 "abc" 和 "ccc" 通过 hash function 的到的 index 可能是一样的，就会误判。
伟大的计算机先哲，尼古拉斯赵四曾经说过，如果一次 hash 解决不了，就 hash 两次，所以 BloomFilter 一般会用多个 hash function。
yfractal
回复
不不不，我觉得写得很好，够简单。是我技术不到家 因为 BloomFilter 的概念我之前没接触过，所以以后需要另外花时间看看。 
yfractal
回复
把约束去掉，约束是根据场景人为加上去的。B 树也是一个多叉树，多叉树都能实现拼写检查，差别只是子节点的储存方式，Trie 是通过一个 hash 或数组来存，B 树根据范围条件来放（按某种顺序对字符排序），当然可能就不需要叶子了，但也会觉得就不是 B 树了。
所以认为 B 树不适合或不行，我也是认同的。
Bloom Filter 是 Probabilistic data structure。分清这个概念就更好理解了。既然是概率，那就不是确定的。要求概率模型做确定性的事物是在本质上无视它的属性。所以拿它来和 hash table 类比是不恰当的
fantasticfears
回复
不理解不恰当的地方， 这个是对拼写检查这个问题，提出了四种解决方案，然后并做比较，在实际应用中，也会在 bit map 和 bloom filter 之间做选择。 bloom filter 在拼写检查中，如果出现 false positive，结果就是一个错误（没在字典里）的拼写，认为是正确的，这个在拼写检查里，一般是可以接受的。
early
回复
我想了一下，还是说出我的想法吧。
数据结构是靠约束来定义的，如果约束不满足，就不能叫这个数据结构了。就好比偶数，能被 2 整除的数，是偶数。如果不能被 2 整除，就不是偶数。
yfractal
回复
BloomFilter 是一个不准的 hash table。
我要放到语境里说。这个讨论中和应用无关。你说它是一个不准的 hash table。那我们从定义开始看，Hash Table 是一个数据结构，用 hash function 定义一个 K,V 的结构。同时实现了 associative array abstract data type（ADT）。而 Bloom Filter 是一个概率数据结构。首先它没有实现和 hash table 一样的 ADT，你不能取回存的值。它实现的接口大概是给定一个值，能否确定它不在这个集合里面。或者可能在这个集合里面（这是概率论最基本的假设了，概率的基本是集合。所以说是概率数据结构）。然后它是有 false positive 的，这个你已经讲了。结合这两点，这是我前面讲“拿它来和 hash table 类比是不恰当的”。
当然做拼写检查，讲这些都是多话了。
fantasticfears
回复
你是想说，纯粹从算法比较的角度来讲，这两个算法有本质的区别，所以不能直接比较？
这篇文章是从具体问题出发，提出解决方案，并做比较。算法是为解决实际问题而存在的。