最近参加了一次面试，虽无笔试环节，几位考官却都在算法和思路题上大作文章，颇为受益

有这么几个问题印象深刻：

1. 自创数据结构存储一些字符串，如何快速匹配用户输入（包含或者相等）？
2. 若干memcached分布式的组成集群，有什么办法均匀的分布存储？
3. 爬虫的排重怎么快又省（布隆过滤器原理）？

这几个问题都涉及到了哈希函数，这位编程人民的老朋友。

哈希函数，是一个能将任意大小数据映射到固定尺寸表示法的函数。个人理解，就是数据特征码提取的算法。哈希函数能做什么？在实践中，我用它将看起来很像却不同的两个数据，变成不同的表示码，以区别，以查找。

上述三个问题，我的思路分别如下：

1，被查找的字符串数据都会存储到一颗 Binary Tree 中，树的时间复杂度是对数级别的 ( O(Log n))，不慢。在生成树结构时，并不存储实际的字符串，因为那对树结点的比较和查找没有意义，而是用哈希函数，将每一个字串哈希化成一颗Binary Tree，及一张Hash Table存储结点 [哈希码: 字符串表示]；每次要查找的字符串也将先哈希化，然后沿着树的路径进行结点的比较，在查找无法继续时，再用Hash Table判断是否包含，即：要查找的哈希码比上级节点大，比当前结点小——当然，这个问题其实我并没有想清楚，这个哈希函数怎么设计是个问题，因为哈希码和树的路径间并没有必然的联系，囧rz… [201408] 这个问题已经有了答案：Suffix Tree，一种算法非常复杂却能以线性时间来解决后缀匹配和匹配统计的树 🙂

2，通过哈希做分布式结点表示，一般会用到取模运算，但这么做弊端也很明显：如果结点数发生了变化（某台memcached服务当掉了），将出现大面积的缓存不命中而重置。对此，前辈们早有解决方案：一致性哈希，它的核心思想是：对于哈希算法而言，所有结点都将出现在 0~Max(Hashcode) 这个区间上，顺/逆时针方向排列分布式结点，我们可以通过算法规定按时针方向每个结点管辖一段哈希值，甚至插入虚拟的结点，以减小分布不均匀，再根据分布情况来指定虚拟结点与物理结点的关联关系——Perfectly，有兴趣还可以看看这个理论的 Paper

3，爬虫的排重一般都会用到 Bloom filter，一个典型的用时间换空间的解决方案：使用若干个哈希算法，将查询串压缩成若干位表示码，时间复杂度上由哈希表的 O(1) 上升到 O(log n)。但是在实际运用中，它的性能将不比哈希表差，毕竟内存富余了嘛。

关于哈希和算法，我的知识面相对浅薄，很多时候是人云亦云，这是个问题，既然我希望职业化的走这条程序员的路，还是有很多待提升空间的。so，接下来，需要花些时间，磕一磕Algorithms：

您的支持将鼓励我们继续创作！

微信支付

支付宝

用 [微信] 扫描二维码打赏

用 [支付宝] 扫描二维码打赏