Bloom-Filter的应用1、key-value加快查询一般key-value存储系统的values存在硬盘，查询就是件费时的事。将Storage的数据都插入Filter，在Filter中查询都不存在时，那就不需要去Storage查询了。当FalsePosition出现时，只是会导致一次多余的Storage查询。由于Bloom-Filter所用的空间非常小，所有BF可以常驻内存。这样子的话，对于大部分不存在的元素，我们只需要访问内存中的Bloom-Filter就可以判断出来了，只有一小部分，我们需要访问在硬盘上的key-value数据库，从而大大地提高了效率。
一个办法就是记录下那些发垃圾邮件的email地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。
如果用哈希表，每存储一亿个email地址，就需要1.6GB的内存（用哈希表实现的具体办法是将每一个email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有50%，因此一个email地址需要占用十六个字节。一亿个地址大约要1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百GB的内存。
而BloomFilter只需要哈希表1/8到1/4的大小就能解决同样的问题。
BloomFilter决不会漏掉任何一个在黑名单中的可疑地址。而至于误判问题，常见的补救办法是在建立一个小的白名单，存储那些可能被误判的邮件地址。
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把一个对象的关键字，通过散列算法，映射到一个固定长度的数组中。当我们想要找到对应的对象时，只需要根据它的关键字在散列表中查找（再计算一次散列值）。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。输入叫做关键字，输出叫做散列值或者哈希地址（仅仅是在散列表中的地址）。但通常需要总数据量可以放入内存。散列表是具有固定大小的数组，其中，表长(即数组的大小)应该为质数。冲突：两个不同的输入计算出了相同的散列值。散列函数一般应具备以下几个特点：运算简单；函数的值域必须在散列表内；尽可能减少冲突；不同输入获得的散列值尽量均匀分散。
常用的散列函数：
Hash处理冲突方法：
这种方法如何查找元素x：比如我们采用线性探测法，地址增量f(i)=2。其实就是按照计算hash位置的方法进行查找。首先计算hash(x)，如果这里有元素且不为x，则尝试hash(x)+2；如果这里有元素且不为x，则尝试hash(x)+2+2，一直到查找到的位置为null或者等于元素x。
Hash的应用1、哈希对于检测数据对象（例如消息）中的修改很有用。好的哈希算法使得构造两个相互独立且具有相同哈希的输入不能通过计算方法实现。典型的哈希算法包括MD5和SHA-1。2、海量日志数据分析，比如提取出某日访问百度次数最多的那个IP。
位图的应用1、判断集合中是否存在重复：比如：若集合大小为N，首先扫描一遍集合，找到集合中的最大元素max，然后创建一个长度为max+1的bit数组。接着再次扫描原集合，每遇到一个元素，就将新数组中下标为元素值的位置为1，比如，如果遇到元素5，则将新数组的第6个元素置为1，如此下去，当下次再遇到元素5想置位时，发现新数组的第6个元素已经被置为1了，则这个元素一定重复了。该算法的最坏运算次数2N，但如果能够事先知道集合的最大元素值，则运算次数N。
2、判断集合中某个元素是否存在:比如：给你一个文件，里面包含40亿个非负整数，写一个算法找出该文件中不包含的一个整数，假设你有1GB内存可用。如果你只有10MB的内存呢？32位无符号整数的范围是0~4294967295(即2x2147483647+1)，因此可以申请一个长度为4294967295的bit数组bitArr，bitArr的每个位置只可以表示0或者1。8个bit为1B，所以长度为4294967295的数组占用内存：40*10^8bit=0.5GB=500MB。然后遍历这40亿个无符号数，例如，遇到7000，就把bitArr[7000]置为1。遍历数字完成后，遍历bitArr，哪个位置的值为0，哪个数就不在这40亿个数内。
现在我们来看如果内存要求是10MB呢？我们可以将所有04294967295的数据平均分成64个区间，每个区间保存67108864个数，比如：第0区间[067108863]，第1区间[67108864134217727]，第i区间为[67108864*i67108864(i+1)-1]...,实际上我们并不保存这些数，而是给每一个区间设置一个计数器。这样每读入一个数，我们就在它所在的区间对应的计数器加1。处理结束之后，我们找到一个区间，它的计数器值小于区间大小(67108864)，说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理这个区间即可。接下来我们就可以用BitMap算法了。申请长度为67108864的bitArr，记为bitArr[0..67108863]，我们再遍历一遍数据，把落在这个区间的数对应的位置1(当然数据要经过处理，即落在区间i的数num，则bitArr[num-67108864i]=1)。最后我们找到这个区间中第一个为0的位，其对应的数就是一个没有出现在该文件中的数。
再比如：2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。将bit-map扩展一下，用2bit表示一个数即可，00表示未出现，01表示出现一次，10表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是00，则将其置为01；如果是01，将其置为10；如果是10，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。
双层桶划分不是一种数据结构，而是一种算法设计思想，类似于分治思想。面对大量的数据我们无法处理的时候，可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，最后在一个可以接受的范围内进行操作。可以通过多次缩小，双层只是一个形式，分治才是其根本（只是“只分不治”）。常规方法：把大文件通过哈希函数分配到不同的机器，或者通过哈希函数把大文件拆成小文件，一直进行这种划分，直到划分的结果满足资源限制的要求(即分流)。适用范围：第k大，中位数，不重复或重复的数字
一般来说，应该在这些列上创建索引：
配置缓存可以有效的降低数据库查询读取次数，从而缓解数据库服务器压力。
对海量数据进行分区，以降低需要处理的数据规模。比如，针对按年存取的数据，可以按年进行分区。
分表包括两种方式：横向分表和纵向分表，其中，横向分表比较有使用意义，故名思议，横向切表就是指把记录分到不同的表中，而每条记录仍旧是完整的（纵向切表后每条记录是不完整的），例如原始表中有100条记录，我要切成2个表，那么最简单也是最常用的方法就是ID取摸切表法，本例中，就把ID为1,3,5,7。。。的记录存在一个表中，ID为2,4,6,8,。。。的记录存在另一张表中。虽然横向切表可以减少查询强度，但是它也破坏了原始表的完整性，如果该表的统计操作比较多，那么就不适合横向切表。横向切表有个非常典型的用法，就是每个用户的用户数据一般都比较庞大，但是每个用户数据之间的关系不大，因此这里很适合横向切表。最后，要记住一句话就是：分表会造成查询的负担，因此在数据库设计之初，要想好是否真的适合切表的优化。
对海量数据进行分批处理，再对处理后的数据进行合并操作，分而治之。
磁盘存取臂的来回移动使得非顺序磁盘存取变成了最慢的操作，尽量保证存取数据的有序性，保证数据良好的局部性。
倒排索引（英语：Invertedindex），也常被称为反向索引、置入档案或反向档案，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是目前搜索引擎公司对搜索引擎最常用的存储方式。
有两种不同的反向索引形式：
当待排序的对象数目特别多时，在内存中不能一次处理，必须把它们以文件的形式存放于外存，排序时再把他们一部分一部分的调入内存进行处理，这种方式就是外排序法。基本原理及要点：外部排序的两个独立阶段：1）首先按内存大小，将外存上含n个记录的文件分成若干长度为L的子文件或段。依次将子文件读入内存并利用有效的内部排序对他们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些子文件为归并段。2）对这些归并段进行逐趟归并，使归并段逐渐由小到大，最后在外存上形成整个文件的单一归并段，也就完成了文件的外排序。适用范围：大数据的排序，去重
一个典型实现：假设文件被分成L段子文件，需要将所有数据从大到小进行排序（即先将最大的输出，再输出第二大的，直到所有元素的顺序被获得）。（1）依次读入每个文件块，在内存中对当前文件块进行排序（应用恰当的内排序算法），并将排序后的结果直接写入外存文件（分别写到不同的子文件）。此时，每块文件相当于一个由大到小排列的有序队列。（2）接下来进行多路归并排序，在内存中建立一个L个元素的大顶堆（注意这里的要求不仅仅是要获得topK，还要按照从大到小的排序输出，所以没使用小顶堆），建堆的过程就是把L块文件中每个文件的队列头（每个文件的最大值）依次加入到堆里，并调整成大顶堆。（3）弹出堆顶元素，如果堆顶元素来自第i块（怎么知道堆顶元素来自哪一块？可以在内存中建立一个hashMap，以第几个子文件为key，以最近一个加入的元素为value，每次新加入元素则更新value），则从第i块文件中补充一个元素到大顶堆，并调整大顶堆结构。弹出的元素暂存至临时数组。（4）当临时数组存满时，将数组写至磁盘，并清空数组内容。（5）重复过程（3）、（4），直至所有文件块读取完毕。
适用范围：数据量大，重复多，但是数据种类小可以放入内存
实现代码，大量递归的应用：
MapReduce实例：上千万或亿数据，统计其中出现次数最多的前N个数据。讲解：首先可以根据数据值或者把数据hash后的值，按照范围划分到不同的子机器，最好让数据划分后可以一次性读入内存，这样不同的子机器负责处理各自的数值范围。得到结果后，各个子机器只需拿出各自的出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据。
适用范围：数据量很大(通常大于1TB)
海量数据中找出出现频度最高的前K的数或者字符串，或者海量数据中找出最大的前K个数。
针对topK类问题，通常比较好的方案是分治+Trie树/HashMap+小顶堆，即hash映射分流+hashMap统计+小顶堆求topK，即先将数据集按照Hash映射分解成多个小数据集，然后使用Trie树或者HashMap统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有topK中求出最终的topK。当然也可以：分流到不同机器+Trie树/HashMap+小顶堆，即先将数据集按照Hash方法分解成多个小数据集，然后分流到不同的机器上，具体多少台机器由面试官限制决定。对每一台机器，如果分到的数据量依然很大，比如内存不够或者其他问题，可以再用hash函数把每台机器的分流文件拆成更小的文件处理。然后使用Trie树或者Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有topK中求出最终的topK。
第三种方法是Hash去重+最小堆法。如果这1亿个数里面有很多重复的数，先通过hashMap，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治+最小堆法或直接最小堆法查找最大的10000个数。
实际运行：实际上，最优的解决方案应该是最符合实际设计需求的方案，在实际应用中，可能有足够大的内存，那么直接将数据扔到内存中一次性处理即可，也可能机器有多个核，这样可以采用多线程处理整个数据集。下面针对不同的应用场景，分析了适合相应应用场景的解决方案。（1）单机+单核+足够大内存如果需要查找10亿个查询词（每个占8B）中出现频率最高的10个，每个查询词占8B，则10亿个查询词所需的内存大约是10^9*8B=8GB内存。如果有这么大内存，直接在内存中先用HashMap求出每个词出现的频率，然后用小顶堆求出频率最大的10个词。
（2）单机+多核+足够大内存这时可以直接在内存中使用Hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑同（1）类似，最后一个线程将结果归并。该方法存在一个瓶颈会明显影响效率，即数据倾斜。每个线程的处理速度可能不同，快的线程需要等待慢的线程，最终的处理速度取决于慢的线程。而针对此问题，解决的方法是，将数据划分成c×n个partition（c>1），每个线程处理完当前partition后主动取下一个partition继续处理，直到所有数据处理完毕，最后由一个线程进行归并。
（3）单机+单核+受限内存这种情况下，需要用hash函数将原数据文件映射到一个一个小文件，如果小文件仍大于内存大小，继续采用Hash的方法对数据文件进行分割，直到每个小文件小于内存大小，这样每个文件可放到内存中处理。采用（1）的方法依次处理每个小文件。
（4）多机+受限内存这种情况，为了合理利用多台机器的资源，可用hash函数将原数据文件映射到一个一个小文件，然后分发到多台机器上，每台机器采用（3）中的策略解决本地的数据，最后将所有机器处理结果汇总，并利用小顶堆求出频率最大的10个词。
从实际应用的角度考虑，（1）（2）（3）（4）方案并不可行，因为在大规模数据处理环境下，作业效率并不是首要考虑的问题，算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性，以便数据量进一步加大（随着业务的发展，数据量加大是必然的）时，在不修改算法框架的前提下，可达到近似的线性比；算法应该具有容错性，即当前某个文件处理失败后，能自动将其交给另外一个线程继续处理，而不是从头开始处理。
topK问题很适合采用MapReduce框架解决，用户只需编写一个Map函数和两个Reduce函数，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解决该问题。具体而言，就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reducetask；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce函数，统计所有Reducetask，输出数据中的topK即可。
直接将数据均分到不同的机器上进行处理是无法得到正确的结果的。因为一个数据可能被均分到不同的机器上，而另一个则可能完全聚集到一个机器上，同时还可能存在具有相同数目的数据。
以下是一些经常被提及的该类问题。（1）有一个1G大小的文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。方案1：顺序读文件，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件中。这样每个文件大概是200k左右。如果其中有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似于归并排序）的过程了。
以下是一些经常被提及的该类问题。（1）给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？方案1：可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
方案2：如果允许有一定的错误率，可以使用Bloomfilter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloomfilter映射为这340亿bit，然后逐个读取另外一个文件的url，检查它是否在Bloomfilter表示的集合中，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
（2）在25亿个整数中找出不重复的整数，内存不足以容纳这25亿个整数。方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需\(2^{32}*2bit=2^{30}B\)=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所有整数遍历完成后，查看bitmap，把对应位是01的整数输出即可。
方案2：采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文件中不重复的整数。对于每个小文件，用hash_map(int,count)来统计每个整数出现的次数，输出即可。
（3）1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？方案1：这题用trie树比较合适，hash_map也应该能行。
一般采用位图(若为int型的数，最多\(2^{32}\),\(2^{32}*1bit=2^{30}/2B\)=0.5GB=500MB，完全可以放入内存)或者外排序。（1）有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。方案1：
方案2：一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了
方案3：与方案1类似，但在做完hash，分成多个文件后，可以交给多个机器来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。