正规的hash表是用一个hash算法将搜索范围缩小，然后在冲突链表中进行精确匹配，因此结果无疑是确定的。然而Bloom过滤算法并不维护冲突链表，它只是逐步用多个不同的hash算法将搜索范围一步步缩小，即使这个范围再小，也还是有冲突的可能，而这种可能就是误判。Bloom过滤算法在数据结构上设计地十分精巧，如果使用N个hash算法，那么只需维护一个N位的位图，为集合添加一个元素的时候，为该元素应用每一个hash算法计算N个范围从0到N-1的hash值Si，并在位图中置位Si为1。现在判断元素x是否在集合中，为x计算N个hash值Xi，将位图上位于Xi上的所有值做与运算，结果为0的话，说明元素x一定不在集合中，如果它在的话，一定在添加的时候会将所有相关位设置为1。
6.应用Bloom过滤器
我在上述2-5小节所描述的查找算法开始之前部署一个Bloom过滤器，是不是更好呢？如果这个Bloom算法设计地足够好，对于大多数情况，如果返回0，我就可以直接跳到创建操作的逻辑，省去了大量的遍历时间。如果返回1，那么仍然需要进行精确匹配，这相当于在我本来就觉得不好的算法基础上又平添了一个Bloom过滤，情形恶化了。但是这就是代价！这就是冒险！我可以将责任推到”这个Bloom算法设计地不够好“！另一方面，需要权衡计算N个hash的开销和计算1个hash加上遍历的开销哪个大，此时不应该简单分析时间复杂度，因为对于Bloom，如果N确定了，那么时间复杂度无疑是O(1)，难道一定比hash表的效率更好吗？事实上我们应该取加权统计值，而这个值依赖于严格的性能压力测试。
还是那句话，没有免费的午餐，要么使用硬件加速，此时你花费的是钱，要么设计一个良好的算法，此时你付出的冒险以及算法失败后的补偿！
7.分级hash查找
像MMU中的页表查找思想一样，也和BSD中的路由查找算法的思想一样，采用多层hash查找而不是单一hash加冲突链表遍历。
我以conntrack查找为例，我可以将conntrack简化为一个{IP1,IP2}对，第一个元素为键，第二个为值，这样就可以将conntrack的查找做成BSD系统的路由查找的样子，其中IP2可以被看成下一跳。或者别的......
我并不是说多级的hash算法要比单独的hash算法更高效，而是说多级的hash表可以在多个CPU核心分别计算，多级hash表可以将每一个hash计算视为一个维度，每一个CPU核心计算一个维度的hash值，定位该维度的坐标，反观单一hash表就不能利用多CPU核心优势，你必须先计算好hash值才能定位hash桶从而遍历冲突链表。在多CPU核心时代，传统的基于时间复杂度计算分析性能的方式可能已经过时。