关于实战算法都需要了解哪些？一文带你详细了解，欢迎收藏！
▐ URL黑名单（布隆过滤器）
100亿黑名单URL，每个64B，问这个黑名单要怎么存？判断一个URL是否在黑名单中
散列表：
如果把黑名单看成一个集合，将其存在hashmap中，貌似太大了，需要640G，明显不科学。
布隆过滤器：
它实际上是一个很长的二进制矢量和一系列随机映射函数。
它可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。对于布隆过滤器而言，它的本质是一个位数组：位数组就是数组的每个元素都只占用1 bit，并且每个元素只能是0或者1。
在数组中的每一位都是二进制位。布隆过滤器除了一个位数组，还有K个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：
- 使用K个哈希函数对元素值进行K次计算，得到K个哈希值。
- 根据得到的哈希值，在位数组中把对应下标的值置为1。
▐ 词频统计（分文件）
2GB内存在20亿整数中找到出现次数最多的数
通常做法是使用哈希表对出现的每一个数做词频统计，哈希表的key是某个整数，value记录整数出现的次数。本题的数据量是20亿，有可能一个数出现20亿次，则为了避免溢出，哈希表的key是32位（4B）,value也是32位（4B），那么一条哈希表的记录就需要占用8B。
当哈希表记录数为2亿个时，需要16亿个字节数（8*2亿），需要至少1.6GB内存(16亿/2^30,1GB==2^30个字节==10亿)。则20亿个记录，至少需要16GB的内存，不符合题目要求。
解决办法是将20亿个数的大文件利用哈希函数分成16个小文件，根据哈希函数可以把20亿条数据均匀分布到16个文件上，同一种数不可能被哈希函数分到不同的小文件上，假设哈希函数够好。然后对每一个小文件用哈希函数来统计其中每种数出现的次数，这样我们就得到16个文件中出现次数最多的数，接着从16个数中选出次数最大的那个key即可。
▐ 未出现的数（bit数组）
- 40亿个非负整数中找到没有出现的数
对于原问题，如果使用哈希表来保存出现过的数，那么最坏情况下是40亿个数都不相同，那么哈希表则需要保存40亿条数据，一个32位整数需要4B，那么40亿*4B= 160亿个字节，一般大概10亿个字节的数据需要1G的空间，那么大概需要16G的空间，这不符合要求。
我们换一种方式，申请一个bit数组，数组大小为4294967295，大概为40亿bit，40亿/8=5亿字节，那么需要0.5G空间，bit数组的每个位置有两种状态0和1，那么怎么使用这个bit数组呢？呵呵，数组的长度刚好满足我们整数的个数范围，那么数组的每个下标值对应4294967295中的一个数，逐个遍历40亿个无符号数，例如，遇到20，则bitArray[20]=1；遇到666，则bitArray[666]=1,遍历完所有的数，将数组相应位置变为1。
- 40亿个非负整数中找到一个没有出现的数，内存限制10MB
10亿个字节的数据大概需要1GB空间处理，那么10MB内存换算过来就是可以处理1千万字节的数据，也就是8千万bit，对于40亿非负整数如果申请bit数组的话，40亿bit /0.8亿bit=50，那么这样最少也得分50块来处理，下面就以64块来进行分析解答吧。
- 总结一下进阶的解法
- 根据10MB的内存限制，确定统计区间的大小，就是第二次遍历时的bitArr大小。
- 利用区间计数的方式，找到那个计数不足的区间，这个区间上肯定有没出现的数。
- 对这个区间上的数做bit map映射，再遍历bit map，找到一个没出现的数即可。
- 自己的想法
如果只是找一个数，可以高位模运算，写到64个不同的文件，然后在最小的文件中通过bitArray一次处理掉。
- 40亿个无符号整数，1GB内存，找到所有出现两次的数
对于原问题，可以用bit map的方式来表示数出现的情况。具体地说，是申请一个长度为4294967295×2的bit类型的数组bitArr，用2个位置表示一个数出现的词频，1B占用8个bit，所以长度为4294967295×2的bit类型的数组占用1GB空间。怎么使用这个bitArr数组呢？遍历这40亿个无符号数，如果初次遇到num，就把bitArr[num2+1]和bitArr[num2]设置为01，如果第二次遇到num，就把bitArr[num2+1]和bitArr[num2]设置为10，如果第三次遇到num，就把bitArr[num2+1]和bitArr[num2]设置为11。以后再遇到num，发现此时bitArr[num2+1]和bitArr[num2]已经被设置为11，就不再做任何设置。遍历完成后，再依次遍历bitArr，如果发现bitArr[i2+1]和bitArr[i2]设置为10，那么i就是出现了两次的数。
▐ 重复URL（分机器）
- 找到100亿个URL中重复的URL
原问题的解法使用解决大数据问题的一种常规方法：把大文件通过哈希函数分配到机器，或者通过哈希函数把大文件拆成小文件。一直进行这种划分，直到划分的结果满足资源限制的要求。首先，你要向面试官询问在资源上的限制有哪些，包括内存、计算时间等要求。在明确了限制要求之后，可以将每条URL通过哈希函数分配到若干机器或者拆分成若干小文件，这里的“若干”由具体的资源限制来计算出精确的数量。
例如，将100亿字节的大文件通过哈希函数分配到100台机器上，然后每一台机器分别统计分给自己的URL中是否有重复的URL，同时哈希函数的性质决定了同一条URL不可能分给不同的机器；或者在单机上将大文件通过哈希函数拆成1000个小文件，对每一个小文件再利用哈希表遍历，找出重复的URL；或者在分给机器或拆完文件之后，进行排序，排序过后再看是否有重复的URL出现。总之，牢记一点，很多大数据问题都离不开分流，要么是哈希函数把大文件的内容分配给不同的机器，要么是哈希函数把大文件拆成小文件，然后处理每一个小数量的集合。
▐ TOPK搜索（小根堆）
- 海量搜索词汇，找到最热TOP100词汇的方法
最开始还是用哈希分流的思路来处理，把包含百亿数据量的词汇文件分流到不同的机器上，具体多少台机器由面试官规定或者由更多的限制来决定。对每一台机器来说，如果分到的数据量依然很大，比如，内存不够或其他问题，可以再用哈希函数把每台机器的分流文件拆成更小的文件处理。
处理每一个小文件的时候，哈希表统计每种词及其词频，哈希表记录建立完成后，再遍历哈希表，遍历哈希表的过程中使用大小为100的小根堆来选出每一个小文件的top100（整体未排序的top100）。每一个小文件都有自己词频的小根堆（整体未排序的top100），将小根堆里的词按照词频排序，就得到了每个小文件的排序后top100。然后把各个小文件排序后的top100进行外排序或者继续利用小根堆，就可以选出每台机器上的top100。不同机器之间的top100再进行外排序或者继续利用小根堆，最终求出整个百亿数据量中的top100。对于top K的问题，除哈希函数分流和用哈希表做词频统计之外，还经常用堆结构和外排序的手段进行处理。
