如果你基础不行，三天前刚准备转码，那就更得准备几个的小把戏，不用打肿脸也能充一回胖子。

基于这两个需求，今天小职就来给大家介绍三个讨巧的数据结构。面试当中一提，那可是相当撑场面。

1、布隆过滤器（bloom filter）

2、前缀树（prefix trie）

3、环形缓冲（ring buffer）

布隆过滤器

隆过滤器是集合的概率版本。检测集合是否包含某元素的时间复杂度为O(1)、空间复杂度为O(N)。Bloom过滤器也可以检测出集合是否可能包含该元素，它的时间复杂度为O(1)，而空间复杂度只需要O(1)！

谁会真正使用布隆过滤器？

Chrome需要在不牺牲速度或空间的情况下保护你免受访问垃圾邮件网站。

想象一下，如果每次你点击一个链接，Chrome都必须进行网络通话来检查它庞大的垃圾邮件URL数据库，然后才允许你访问这个页面，这会不会让你等疯掉。此外，设想一下，如果Chrome改善延迟的解决方案是在本地存储整个垃圾邮件URL列表，这根本就是不可行的！

所以，chrome在本地存储了一个潜在垃圾邮件URL的布隆过滤器，这既节省时间又节省空间，可以快速检查给定的URL是否为垃圾邮件。对于普通的URL，布隆过滤器对“非垃圾邮件”的响应就足够判定了。如果一个URL被标记为“可能是垃圾邮件”，那么Google可以在跳转之前检查它真实数据库。事实证明，当你愿意牺牲绝对时，你可以做出伟大的事情！

布隆过滤器的原理

布隆过滤器的维基百科页用大量的术语描述了实现细节，所以在这里我会用简单的描述一下实现过程。如果你想要更精确的细节，你应该去看看维基百科。我会略过很多步骤，但我会让你有一个大致了解。

如果你想在Bloom过滤器中插入一个元素，首先假设有N个不同的确定性哈希函数。当同一个元素输入不同哈希函数时，会得到不同的值（冲突是可以有的）。

使用每个哈希函数的输出作为数组的索引]，并对应每个索引i将数组[i]设置为true。插入元素就完成了！插入元素的时间复杂度是O(1)，因为对每个插入元素所做的唯一工作是运行恒定数量的哈希函数，并设置恒定数量的数组索引。

那该如何检查布隆过滤器是否包含该元素？再次运行所有相同的哈希函数！

哈希函数是确定性的，因此相同的输入应返回相同的输出。所以相对应每个索引，检查布隆过滤器的数组是否在该索引处设置为true即可。如果哈希函数输出的数组的每个单元都为真，那么可以很高的概率说这个元素已经插入到了布隆过滤器中。这一方法总是存在误报的可能性。不过，布隆过滤器的一大特色是永远不会出现漏报。

那么，你需要多少个哈希函数，又需要多大的数组呢？这你就得好好算一番了。维基百科对它们的解释更详细，你值得一读。

前缀树（prefix trie）

前缀树是一种数据结构，允许你通过其前缀快速查找字符串，还可以查找有公共前缀的字符串。

谁会真的用前缀树？

基因组学研究人员！

事实证明，现代基因组研究在很大程度上依赖于字符串算法和数据结构，因为你试图从组成基因组序列的数百万个核苷酸中探索奥秘。对于基因组数据，你经常需要对齐序列，找到差异或找到重复的模式。如果你想了解更多相关信息，可以先阅读生物信息学读物，然后参与“DNA测序算法”或“生物信息学算法”等课程。

前缀树的原理

想象一下，你有一棵树，每个节点都有一个包含26个子节点的数组，每个子节点对应一个英文字母。（如果要包含其他字符，可以将26更改为不同的值。）要在你的树中表示单词，你将从根节点开始，沿着路径向下走，并在每个节点添加一个字母。

环形缓冲区（ring buffer）

环形缓冲区是使用普通数组的一种非常好的方式，它主要被用于处理数据流。

谁会真的使用环形缓冲区？

说不定Netflix会用？

我用google搜索“netflix ring buffer”，发现了他们发布了一些开源环缓冲区代码。但问题是，公司真的会用他们已经开源的代码嘛？

环形缓冲区的原理

如果你读到了这儿，说明你基础一定还不错，那就直接去维基百科瞅一眼这个数据结构吧，比前两个简单多了！

一个聪明的程序员不仅需要学富五车，也需要灵动机智的脑袋，这些“冷知识“能帮助你在面试时获得不错的反馈。