【有书共读】《算法与数据结构题目最优解》（在线编程题总结6）

       很多的代码面试题都给出了数十亿的数据量，或整数，或字符串，再给出1G甚至小到10M的内存空间，让在苛刻条件下完成搜索和遍历，并输出某些结果。这样的问题叫做大数据和空间限制问题。

此类问题一般都没有时间限制，因为时间和空间是相互制约和矛盾的，如果想要时间复杂度降低，很多情况下需要占用较大的内存空间，比如归并排序，而如果内存空间限制地非常小，则时间复杂度就会上升。

面对这样的问题，策略主要有Hash分流，大文件分解为小文件等等。下面具体分析：

       针对大数据量的过滤器，但布隆过滤器并非100%正确，需要允许出现很小概率的错误。 此时就使用Hash函数了，将所有的数据（比如上百亿的URL，垃圾邮件标题，爬虫网页判重等）经过Hash函数映射成分散、等长的整数或字符串上。Hash函数的结果一定是大于某一个m值的，而这个m值是一个数组的长度，数组中的每一个位置的参数可以是0或者1，假设有k个Hash函数，其结果都对m取余，则可得到余数一定在0~m-1上，即可把对应的位置标黑。这样一来，即可得到一个试纸，即该数组，里面的0或1标记了这个数据。比较两个数据，如果全部都一样，那么就可以肯定这两个数据相同，但有很小的概率错误，不过可以忽略不计，毕竟假阳对我们的影响并不大。如果试纸不一样，则数据本身一定不一样。

       在操作使用Hash构造的布隆过滤器时，涉及到选取多少个Hash函数，选哪些Hash函数，m值设多大，此时需要多大的内存空间。这些都是需要考虑的问题，有公式可解决这些问题！布隆过滤器详解，内含公式

       这个操作在外排算法中有涉及，但是那种操作是将数据直接拆分。而此处的以大化小，是采用Hash函数来处理的。也就是说，将大的数据量拆分为小的数据量，全然无序，但必须保证数据相同或者数据性质相同的数据要进入同一个小文件当中。

       在布隆过滤器里，就是使用bitmap来操作，只不过那个bitmap的长度并不长，而且其中的每一个数据都是0或1。
但是如果需要，我们可以构造大数据量长度的bitmap，其中的数据都是0或1，可以赋予0或1各种意义，一般来说，如果需要标志数据量的标记不局限与0或1，可以采用每两位标识一个数据，这样bitmap的长度就是整个数据量数量的2倍。

      如果单纯用取余的方法来给数据归类，则很容易造成当模改变时，要修改大量的数据；而当采用一致性Hash时，就不需要修改那么多数据。一致性Hash详解