如何判断一个元素在亿级数据中是否存在？关于解决方案有一些不同的想法。先说明一下问题：现在数据量非常大，假设都是int类型。给定一个数字，确定数字是否在其中（尽可能高效）。题目要求文章给个思路：首先想到的是Hash算法，它的时间复杂度是O(1)，可以在常数时间内判断数据是否存在。文中给出的方法是直接使用Java集合对象HashSet（内部用HashMap实现）。文章给出的结论是加载数据太慢，直接讨论后一种方法——BloomFilter。***发现BloomFilter不可能***解决这个问题，有一个“误判”。总结题目要求：加载数据尽可能快查询速度尽可能快块数据判断不误判考虑到算法的复杂度，最好是O(1)在常数时间内完成查找，并且基于哈希算法。所以我的解决方案是使用Hash。现代CPU多流水线完成1000W周期非常快，所以理论上“加载数据”应该非常快。上文提到的加载数据慢，其实是因为HashSet的put方法中逻辑复杂——毕竟HashSet是一种通用的Hash算法。新思路是1000W条数据，我们可以用1000W个二进制位来表示，初始化为全0，如果某个数据存在，就置1。。Java中没有办法直接操作一个大的连续内存空间。我用一个int类型的数组来表示，每个数组元素可以表示32个元素。比如分别加载5、13、29（注意：字节顺序）。这些数据都小于32，放在第一个数组元素中即可。代码如下：1-100之间可以取1000W条数据，只需要100位；也可能在1-1000W之间取，此时需要1000W位。所以用单个变量boundOfData来表示数据的上限，需要的位数是boundOfData，每个int是32位，计算需要的数组个数是boundOfData/32然后向上取整。数据除以32的商为数组下标，余数为对应的位位置。比如10，应该在第一个数组元素的第10位，定位后通过位运算置1即可。判断的时候只要按照同样的算法定位数组位置，判断某位是否为1即可。我们来测试一下速度，分析一下某个执行结果的算法：加载数据部分是O(N)——也就是线性复杂度，这是无法避免的。查询部分是O(1)-常量。当然，这里不会出现“误判”，因为每个数据都会被准确地哈希。再看空间复杂度，1000W的数据需要312500个int类型的数据，也就是1.1M左右的内存空间。我试了1条数据，大概13秒；如果不使用随机数（直接下标），则约为200ms。总结其实很多时候，面试题不是考察你是否知道答案，而是为了解决问题。希望在信息爆炸的今天，我们能够静下心来分析一个问题，仔细思考它的答案。答案是什么？谁在乎，我们的思维过程是最有价值的部分。【本文为专栏作家“行森”原创文章，转载请联系作者获得授权】点此阅读更多本作者好文
