大数据季刊公司出品
校对：刘佳玮、lvy、钱天培
春招袭来啦！又要复试啦！
开发人员复试展现甚么最重要？彼时是你广博的计算机系统才智，和精明的小脑袋瓜。
假如你张法顺，上知广度自学， 历象会计，那短短的数半小时也绝不如你现场表演。因此，你很大得知悉复试官的拳法，脱口扔出三个应节的“冷科学知识”卖个调皮。
假如你此基础没用，四天前刚预备音频文件，那就更得预备三个的他的，不必错成脸也能充正中下怀疯子。
如前所述这三个市场需求，那时季刊菌就来给我们如是说四个讨喜的计算机系统程序。复试之中一提，那不过十分艾盖佩。
这四个计算机系统程序是。登登登等…
1. 戈德冷却系统（bloom filter）
2. 后缀树（prefix trie）
3. 马蹄形缓冲器（ring buffer）
先来说一下，为甚么挑了这四个计算机系统程序。
首先我觉得，你提到的计算机系统程序要稍微冷门一些，这样别人就会认为你了解很多不同类型的计算机系统程序。但它不能太冷门，以免你的复试官要求你真正解释实现细节或原理，那时你就game over了。最好是你提到的计算机系统程序有点冷门，但你的复试官听说过，对它有印象。
复试官都希望自己甚么都晓得，他们听说过这种计算机系统程序但又不太了解，当你向他们如是说时，他们就会觉得你懂得特别多。
除此之外，这些计算机系统程序还应该具有实际用例，以便在技术复试的时候，你能有机会展开如是说。它虽然稍微有点冷门但也不能太low，你假如只晓得一些菜鸡水平的计算机系统程序（比如双向链表），你的复试八成就凉了。
因此，这四个计算机系统程序就被完美选中啦！
戈德冷却系统
戈德冷却系统是集合的概率版本。检测集合是否包含某元素的时间复杂度为O(1)、空间复杂度为O(N)。Bloom冷却系统也可以检测出集合是否可能包含该元素，它的时间复杂度为O(1)，而空间复杂度只需要O(1)！
谁会真正使用戈德冷却系统？
Chrome需要在不牺牲速度或空间的情况下保护你免受访问垃圾邮件网站。
想象一下，假如每次你点击一个链接，Chrome都必须进行网络通话来检查它庞大的垃圾邮件URL数据库，然后才允许你访问这个页面，这会不会让你等疯掉。此外，设想一下，假如Chrome改善延迟的解决方案是在本地存储整个垃圾邮件URL列表，这根本是不可行的！
因此，chrome在本地存储了一个潜在垃圾邮件URL的戈德冷却系统，这既节省时间又节省空间，可以快速检查给定的URL是否为垃圾邮件。对于普通的URL，戈德冷却系统对“非垃圾邮件”的响应就足够判定了。假如一个URL被标记为“可能是垃圾邮件”，那么Google可以在跳转之前检查它真实数据库。事实证明，当你愿意牺牲绝对时，你可以做出伟大的事情！
戈德冷却系统的原理
戈德冷却系统的维基百科页用大量的术语描述了实现细节，因此在这里我会用简单的描述一下实现过程。假如你想要更精确的细节，你应该去看看维基百科。我会略过很多步骤，但我会让你有一个大致了解。
假如你想在Bloom冷却系统中插入一个元素，首先假设有N个不同的确定性哈希函数。当同一个元素输入不同哈希函数时，会得到不同的值（冲突是可以有的）。
使用每个哈希函数的输出作为数组的索引[注释1，注释2]，并对应每个索引i将数组[i]设置为true。插入元素就完成了！插入元素的时间复杂度是O(1)，因为对每个插入元素所做的唯一工作是运行恒定数量的哈希函数，并设置恒定数量的数组索引。
那该如何检查戈德冷却系统是否包含该元素？ 再次运行所有相同的哈希函数！
哈希函数是确定性的，因此相同的输入应返回相同的输出。因此相对应每个索引，检查戈德冷却系统的数组是否在该索引处设置为true即可。假如哈希函数输出的数组的每个单元都为真，那么可以很高的概率说这个元素已经插入到了戈德冷却系统中。这一方法总是存在误报的可能性。不过，戈德冷却系统的一大特色是永远不会出现漏报。
那么，你需要多少个哈希函数，又需要多大的数组呢？这你就得好好算一番了。维基百科对它们的解释更详细，你值得一读。
注释1：如何使用哈希函数的输出作为索引：设哈希函数输出整数值M，取长度N。N%M（N mod M）得到一个值Q，即0≤Q<M。这是一种取任意值并在一个范围内均匀分布的简便方法。假如你以前没有遇到过这个问题，那么应该阅读关于mod运算符的内容，绘制一些示例数组，并使用M的不同值进行实验，以了解N%M的效果。
注释2：实际上，你应该使用位数组而不是普通数组。数组的每个元素至少需要1个字节，而你只需要为“数组”的每个元素存储true / false。因此，你可以通过将其存储为位数组来节省空间，这是这个计算机系统程序的重点。假如你想要听起来很精明，那么位数组（也是位向量）也值得你在复试时提出。嗯，真正的复试专家建议总是在脚注中。
注释3：严格来说，假如你的所有哈希函数都在O（1）时间内运行，那么插入的复杂度才是O（1）。
后缀树（prefix trie）
后缀树是一种计算机系统程序，允许你通过其后缀快速查找字符串，还可以查找有公共后缀的字符串。
我对如是说这一计算机系统程序的第一条建议是，将它称为“后缀树”，而不仅仅是“树”。这样，你就让复试官晓得你是那种了解与后缀和后缀相关算法的人，并且你也希望对你的fancy计算机系统程序进行准确描述。后缀树也是一个非常有趣的话题，但实现细节十分残暴。这是为甚么我只是谈论后缀树，并且假装了解后缀树。
谁会真的用后缀树？
基因组学研究人员！
事实证明，现代基因组研究在很大程度上依赖于字符串算法和数据结构，因为你试图从组成基因组序列的数百万个核苷酸中探索奥秘。对于基因组数据，你经常需要对齐序列，找到差异或找到重复的模式。假如你想了解更多相关信息，可以先阅读生物信息学读物，然后参与“DNA测序算法”或“生物信息学算法”等课程。
假如你想要阅读一些真正有意思的读物，我强烈建议你读一读药物基因组学。随着基因组测序和字符串算法的进步，我们实际上可以预测使用个体的基因组，来确定它们是否具有对药物正确反应的正确基因。例如，假如他们的基因组缺少用于产生处理某种药物的酶的基因，那么药物可能会对他们产生副作用。假如我们晓得甚么基因是重要的，我们可以给他们一种不同的药物！
我承认，后缀树和基因组学之间的联系不太紧密。其实后缀树的最直接用法是用来查字典啦！但光这么讲不是忒无聊了点么。
后缀树的原理
想象一下，你有一棵树，每个节点都有一个包含26个子节点的数组，每个子节点对应一个英文字母。（假如要包含其他字符，可以将26更改为不同的值。）要在你的树中表示单词，你将从根节点开始，沿着路径向下走，并在每个节点添加一个字母。
因此，搜索单词需要O（N）的时间（其中N是单词的长度），假如单词的后缀不存在，则可以提前结束。假如我查询“zzzzzzzz”，树可以在“zz”之后结束查询。
马蹄形缓冲器区（ring buffer）
马蹄形缓冲器区是使用普通数组的一种非常好的方式，它主要被用于处理数据流。
谁会真的使用马蹄形缓冲器区？
说不定Netflix会用？
我用google搜索“netflix ring buffer”，发现了他们发布了一些开源环缓冲器区代码。但问题是，公司真的会用他们已经开源的代码嘛？
马蹄形缓冲器区的原理
好啦好啦。真的还有人在读这篇文章嘛。
假如你读到了这儿，说明你此基础很大还不错，那就直接去维基百科瞅一眼这个计算机系统程序吧，比前三个简单多了！
总结一下，那时季刊菌如是说了四个重要的计算机系统程序：戈德冷却系统（bloom filter），后缀树（prefix trie），马蹄形缓冲器（ring buffer）。
想当一个精明开发人员，这些结构你值得拥有！
相关报道：
http://blog.amynguyen.net/?p=853
实习/全职编辑记者招聘ing
加入我们，亲身体验一家专业科技媒体采写的每个细节，在最有前景的行业，和一群遍布全球最优秀的人一起“招聘”了解详情。简历请直接发送至[email protected]
志愿者如是说
“志愿者”加入我们
