海量数据处理
海量数据处理
我们这里的海量数据处理主要是通过几个实际问题，应用数据结构，来熟悉哈希数据结构，位图数据结构，和布隆过滤器。如果哈希数据结构，位图数据结构和布隆过滤器
请点击[https://github.com/jacksparrowwang/cg19.github.com/tree/master/Data%20Structure](github)
海量数据的处理问题，遇到的问题一般有文件过大无法加载到内存，文件内容庞杂无法很快搜素到想要的内容，还有一个问题，如何在庞大的数据中统计出想要的内容。
北冥有鱼，其名为鲲，鲲之大，一锅炖不下
这就像大数据一样。那么我们来如何处理呢？实例来分析
-
给定一个大小超过 100G 的文件, 其中存在 IP 地址, 找到其中出现次数最多的 IP 地址(hash文件切分)
这里给定了一个100G的文件，其中内容很多，但是要我们找到其中存在IP，而且是出现次数最多的IP地址。这时候有人会说，让电脑一点一点去找，但是这里100G要全是IP地址，那么在一般电脑上是无法加载的，就算有那这里我们要在空间上实现优化。这里就像前面的北冥有鱼，其名为鲲，鲲之大，一锅炖不下啊。
那么没我们就得想办法，我们可以采用哈希切分的办法来进行切分数据，把数据分成若干分，然后逐一去加载到内存中去统计。
何为哈希切分。哈希切分，就是利用哈希值，来进行切分，然后把相同的值放入到一个集合中。比如我们现在要把100g的文件切分成100份（如果觉得100份后依然很大那么我们可以切割成1000份），那么读取每一个文件内容，计算它的哈希值，让其模100，如果等于0，就放入0号集合中，如果等于1就放入1号集合中，依次循环。那么等到把所有的元素遍历完，那么100个集合也就成功的形成（哈希算法够复杂计算出哈希值分布够均匀）。在这集合中相同的IP一定在同一个集合中。因为相同的IP所对应的哈希值一定相同。到这时我们在让它加载到内存中进行统计，这样我们就把一锅炖不下的问题转变成了多个锅分开炖。 -
给定100亿个整数, 找到其中只出现一次的整数(位图变形, 用两位来表示次数).
这个题解题的主要思想是要进行空间上面的优化，查找很简单，但是要进行大数据的查找，时间上虽说让其久一点，但空间的消耗也是巨大，那么我们如何减小空间上的开销呢？
那么我们在学习一种数据结构叫位图，位图其实就是以最小的空间来标记是否存在要查找的元素。这里我们要得是找到出现一次的整数，位图中是采用了一个比特位来表示是否存在，查找是否存在一次那么我们就可以用两位比特位来表示，比如用00表示没有，用01表示出现一次用10表示不是此数据，此数据绝对出现超过三次那么我们就可以继续查找。
这样做的好处就是大大优化了空间上的开销，同时对于这种思想，我们还可以进行改进，比如需要找出出现5次的数据那么我们就可以用三位比特位来表示。 -
有两个文件, 分别有100亿个query(查询词, 字符串), 只有1G内存, 找到两个文件的交集(hash文件切分 + 布隆过滤器).
前面已经提到对于大数据内容进行查找统计，我们用到是哈希切分，哈希切分的主要作用就是很大程度上优化了空间上的消耗。
这里有两个文件都是100亿个query，那么我们在进行统计时候，用哈希切分来进行切分，比如我们现在要把数据分成100份那么，取每个数据进行求哈希值，然后模100，如果模值等于0，那么我们就把它归为0号集合，再将其插入到布隆过滤器中，让然后让另一个文件也进行哈希切分，并且切分成100份，模以100，等于0，就归于0号集合，然后将这个0号集合到布隆过滤器中的0号元素进行查找，这样我们就可以找到0号元素中的交集，那么我们再进行下一个集合的查找，以此类推。。。 -
给上千个文件, 每个文件大小为1K - 100M, 设计算法找到某个词存在在哪些文件中(倒排索引).
这个问题就类似于一些搜索引擎，比如百度，当输入一个或者两个关键字时，会很快返回上百个或者上千个文件链接。那么他们是怎么做到的呢？
这个现实利用哈希表，键值对来进行倒排索引，哈希表的实现，如果不知道哈希表的实现请戳上面链接。哈希表正向是一个key对用一个value那么我们用开，我们给文件进行编号，通过编号我们就可以找到相应的value，这是正向索引，那么现在我们来倒过来，文件中的关键字作为key，文件的编号作为value，那么我们就可以很轻松的找到文件。
关于搜索引擎的关键字搜索，是分为两种服务器，一种是线上服务器，就像现在你打开百度搜索，一种是线下服务器，为什么还要有个线下服务器呢？这就是为了实现倒排索引，也是为了提高效率，就比如百度，在百度上会定期的更新数据，这样就会把新添加的数据抓取下来，进行关键字和编号的对应，然后让线上服务器进行加载，就可以了。哈希切分其他用处
一般大公司服务器，不可能为一台，那么就会遇到一个问题，如果有人登陆到服务器，如何在巨大的服务器群体中快速的找到，并且登陆呢？那么在设计服务器群体时，就进行了哈希切分，比如在你注册的时候就把你得账号密码进行哈希计算，然后通过模取到几就会把你得账号分到哪台服务器上管理，这样，就可以大大减少了挨个查找所消耗的时间。
如有错误，还望指正，谢谢。