布隆过滤器找到出现次数最多的数100亿个URL中重复的URL、搜索词汇的top k问题找到没出现的数找到出现两次的数和所有数的中位数一致性哈希算法
布隆过滤器特点：黑名单、爬虫等大数据查询类型，空间要求严格、但容忍一定的失误率。
例：100亿黑名单网页占用64B，查询指定URL是否在黑名单中，允许有0.01%下的失误，额外空间不能超过30GB。
解：
布隆过滤器需要一个长度为m的bit类型的数组（bitMap）。然后需要k个哈希函数。这k个哈希函数的输出域S均大于等于m。
之后将黑名单的URL经过这k个哈希函数计算哈希值，记为Hash1，Hash2, …。之后分别将哈希值对m取余，得到k个值域为[0,m)的值。然后在bitMap中分别将对应下标的位置设为1。
在查询的时候，同样将指定URL经过上述哈希函数计算出k个值，之后取余，判断bitMap中对应的位是否全为1，如果有一个不为1则代表URL肯定不在黑名单内，都为1则在黑名单内，但是会有有误判的情况。调整值域m和哈希函数数量k可以减少失误率。
如果想避免误判，可以使用白名单列表排除那些不在黑名单但会被误判的URL。
找到出现次数最多的数特点：寻找出现次数最多的数，内存有限，数据量大，但有足量储存空间或有足量机器支持。
例：只用2G内存寻找20亿个整数中出现次数最多的数。
解：将20亿个数的大文件用哈希函数分成16个小文件，或者分配到16台机器中。根据哈希函数的性质，同一个数一定会被映射到同一个区域中，故可以在每一小块中用哈希表找出这一块中出现最多的数，之后找出这16个中最多的一个即可。
100亿个URL中重复的URL、搜索词汇的top k问题例：搜索引擎的热搜列表实现。
解：利用哈希将URL拆分到其他机器或拆分为多个文件，之后对拆分的每个单元用哈希表找出重复的URL、以及用堆搜索top k，之后将所有的单元进行合并即可。
找到没出现的数例：在整个无符号整数范围中，只用1G内存找到40亿个无符号整数中没出现的数。
解：依旧使用bitMap，长度为int最大值。之后遍历所有整数，将整数对应下标的位置设为1。之后遍历bitMap，找到所有值为0的下标即可。
进阶：只用10MB的内存，找到一个没出现的数即可。
解：将整个整数域分为64个区间，用一个长度为64的整型数组来统计落在各个区间的数。因为只有40亿个数，不到int的最大值，故少于[int最大值] / 64 = 67108864 的区间一定会有没出现的数，在这个区间里就可以使用bitMap找到了。
找到出现两次的数和所有数的中位数例：使用1GB内存，找到40亿个无符号整数中所有出现两次的数。
解：
因为只需要找到出现两次的数，故可以使用2*[int最大值]的bitMap来记录。如果有一个数num出现1次则将bitMap[num * 2]和bitMap[num * 2 + 1]设置为01，两次则设置为10，三次以上设为11。之后两个两个位遍历bitMap，找到所有为10的位置即可推算出所有出现两次的数。
进阶：使用10M内存，找出这40亿个数的中位数。
解：将整个域分成多个区间，用数组统计每个区间中对应的数的数量。这样就能找到中位数所在的区间。之后在这个区间内统计中位数即可，根据内存大小可以选择直接查找或继续拆分。
总结：找出大数据中出现指定次数的数，且有固定的值域的时候，可以使用bitMap来统计，具体每个单元的大小基于指定出现的次数需要的二进制位数来选择，这样相比使用整形哈希表统计可以大大减小内存需求。
一致性哈希算法分布式数据缓存一般实现策略为：使用哈希函数将数据ID转换为一个key，如果有n台机器，可以计算key % n来将数据操作分配到指定机器上运行。
但这个方法的缺点是：增加或删除机器时，n发生变化，需要全部重新分配机器的负载，进行大规模的数据迁移操作。
解决方案：将哈希的结果域想象为一个环，每个机器利用机器ID计算出哈希值，当作其中的一个点。数据进来后，计算哈希值，找到第一个值比它大的机器，那这台机器就成为它的去向机器。这样，对机器的新增和删除只会影响到该机器哈希值左右的两个节点。不需要进行数据的全体迁移了。
但机器数过少或哈希后分布不均时，会导致负载不均衡。解决这个问题一致性哈希算法引入了虚拟节点机制，即对每台机器用不同的哈希函数计算出多个值，再分别映射到环中，节点数变多，平衡性就会变好。
