海量数据问题集-持续更新

站长

2023年09月19日 14:25 · 阅读数 25

前言

拾人牙慧，此篇自用且持续更新，核心内容并非我自己所写，仅作总结

Redis热Key问题

套路解答

热Key的收集大致有如下几种方法可用：

凭借业务经验，进行预估哪些是热Key。比如某商品在做秒杀，那这个商品的Key就可以判断出是热Key。
主动收集热Key，应用层通过代码抛给消息队列收集分析。
用Redis的自带命令，monitor和redis-cli -hotkeys来统计热Key。

热Key的解决有两种主流的方案

利用二级缓存，比如caffeine+Redis。将热点数据优先放在本地缓存中，这样加载会更快，减少网络IO，尽可能地减少Redis地压力。
将热Key存储到多个Redis节点中，多份数据可读，通过合理的分流手段，避免数据倾斜，降低单个节点的请求压力。

Redis海量数据查询

套路解答

如果取少量的数据，可以选择keys [pattern]命令，扫描符合正则表达式的数据。因为Redis是单线程操作数据的，因此Keys命令会造成阻塞，查询大量数据带来的长时间中断是不可忍受的，因此我们需要使用另一个不阻塞的命令Scan。scan 指令优点是可以无阻塞地查询数据，缺点是会有一定的重复概率，需要在客户端做一次去重，而且整体所花费的时间会比直接用 keys 指令长。

扩展一下：我们常用的图形化用户界面(GUI)或者客户端框架Redisson，在查询大量数据时，内部都用的是Scan命令，Redisson更极端一些，直接将Keys命令内部转换成Scan命令。

两大文件数据找交集

套路解答

方法一：分治法

最常规的就是分治法。每个文件的大小，50(亿=1000*1000)*64(byte=/1024/1024)约等于50GB，远远超过内存限制的4G，所以不能将数据完整加载到内存中处理。

首先遍历文件a，对每个url采用适当的hash方法并根据100取模，尽可能将数据切分为100个小文件a0, a1, a2, ..., a99，这样每个大小约为500MB。使用同样的方法切割文件b，把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b99。这样处理之后，所有可能相同的url都在对应的一组小文件里，比如a0和b0....a99和b99。

然后我们每次拿一对小文件，先将其中一个存到HashSet中，然后遍历另一个小文件的url，看在HashSet中是否存在。如果存在则将其存储到一个单独的文件中，最后循环处理完剩下的一对对小文件，即可得到文件a、b的共同url。

方法二：布隆过滤器

如果允许有一定的错误率，可以使用 Bloom filter，4G 内存大概可以表示 340 亿 bit。将其中一个文件中的 url 使用 Bloom filter 映射为这 340 亿bit，然后挨个读取另外一个文件的 url，检查是否与 Bloom filter，如果是，那么该 url 应该是共同的 url（注意会有一定的错误率）。

方法三：Trie(字典)(前缀)树

一般而言，URL 的长度差距不会不大，而且前面几个字符，绝大部分相同。这种情况下，非常适合使用字典树（trie tree）这种数据结构来进行存储，降低存储成本的同时，提高查询效率。

如何从海量数据中找出高频词？

套路解答

由于内存限制，我们依然无法直接将大文件的所有词一次读到内存中。因此，同样可以采用分治策略(分而治之，进行哈希取余)，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB，进而直接将单个小文件读取到内存中进行处理。

接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1) ；若存在，则执行 map.put(x, map.get(x)+1) ，将该词频数加 1。

上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。(求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆)

如何在大量的数据中找出不重复的整数？

套路解答

方法一：分治法

方法一还是可以用分治法解决，先将 2.5 亿个数划分到多个小文件，用 HashSet/HashMap 找出每个小文件中不重复的整数，再合并每个子结果，即为最终结果。

方法二：位图法

从一道高大上的面试题来学习位图算法BitMap

位图BitMap也叫位映射，位图通过使用位数组来表示某些元素是否存在，就是用一个或多个 bit 来标记某个元素对应的值，而键就是该元素。采用位作为单位来存储数据，可以大大节省存储空间，通过位运算快速查找，判重，排序等。对于整数相关的算法的求解，位图法是一种非常实用的算法。位图在JDK中的默认实现是BitSet这个类，内部使用long数组word，用long而不是int、byte是因为BitSet在and和or时需要遍历数组，64bit的效率高于32和8。内部实现简单解释一下，我这是long数组，也就是数组下标对应一个long值，也就是64位，可以代表64个数，a[0]：0 ~ 63，a[1]：63 ~ 127....因为long换成位来表示就有64，假设我想表示存在一个整数为3，那么需要用BitMap来判断a[0]换成二进制后，第三位是否为1。举个不恰当的例子，如果没有0~63只有3是存在的，那么a[0]=8(二进制为001000.....)时，也就是第三位为1时，可以判断3在BitMap中存在。

2.5亿个整数，极限一点假设全都不一样，假设全存起来，需要(2.510^8)48(1Byte=8bit)=810^9(bit)，换算成G(/1024/1024/1024/8)约等于0.9G。因为题目是找不重复，不能用单纯的两个状态来区分，所以采用2-BitMap，value用两个bit表示，00表示未出现，01表示key代表的数字出现过一次，10表示出现过多次，11不用。如果我用int数组存储，一个value能代表32个值，也就是只要不到30M就能存储2.5亿全部不同的数据，因为用了2个bit所以需要不到60M内存。但是BitMap在未进行优化的时候是需要一组连续的数据空间，假设int的最大值和最小值同时包含，为了建立连续空间的BitMap，需要存储int范围所有的数据，也就是2^32约等于42亿，因为用了2Bit，所以存下int的所有数据需要2^32*2bit/1024/1024/1024/8=1G的内存空间。

如果有1G的内存空间，那么可以遍历2.5亿数据，在2-BitMap修改对应位置的数据，最后位图输出对应位置是10的整数即可。当然如果没有1G的内存空间，可以使用谷歌Guava包中的强化版EWAHCompressedBitmap，可以在BitMap的上层加一层做专门的指向，从而解决数据极度分布不均匀造成的空间利用率低下的问题。

如何查询最热门的查询串？

套路解答

每个查询串最长为 255B，1000w 个串需要占用约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中处理。

方法一：分治法。

划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。方法可行，但不是最好，下面介绍其他方法。

方法二：HashMap 法

虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑把所有字符串及出现次数保存在一个 HashMap 中，所占用的空间为 300w*(255+4)≈777M（其中，4 表示整数占用的 4 个字节）。由此可见，1G 的内存空间完全够用。

首先，遍历字符串，若不在 map 中，直接存入 map，value 记为 1；若在 map 中，则把对应的 value 加 1，这一步时间复杂度 O(N) 。接着遍历 map，构建一个 10 个元素的小顶堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆。遍历结束后，堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度 O(Nlog10) 。

方法三：字典(前缀)树 www.cnblogs.com/TheRoadToTh…

方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。

在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加 1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为 1。最后依然使用小顶堆来对字符串的出现次数进行排序。

如何从 5 亿个数中找出中位数？

套路解答

数据流的中位数-LeetCode原题

维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 1。若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。以下是来自leetCode宫水三叶大佬的题解，很清晰。

插入前两者大小相同，说明插入前数据流元素个数为偶数，插入后变为奇数。我们期望操作完达到「l 的数量为 r 多一，同时双堆维持有序」，进一步分情况讨论：

如果 r 为空，说明当前插入的是首个元素，直接添加到 l 即可；
如果 r 不为空，且 num <= r.peek()，说明 num 的插入位置不会在后半部分（不会在 r 中），直接加到 l 即可；
如果 r 不为空，且 num > r.peek()，说明 num 的插入位置在后半部分，此时将 r 的堆顶元素放到 l 中，再把 num 放到 r（相当于从 r 中置换一位出来放到 l 中）。

插入前两者大小不同，说明前数据流元素个数为奇数，插入后变为偶数。我们期望操作完达到「l 和 r 数量相等，同时双堆维持有序」，进一步分情况讨论（此时 l 必然比 r 元素多一）：

如果 num >= l.peek()，说明 num 的插入位置不会在前半部分（不会在 l 中），直接添加到 r 即可。
如果 num < l.peek()，说明 num 的插入位置在前半部分，此时将 l 的堆顶元素放到 r 中，再把 num 放入 l 中（相等于从 l 中替换一位出来当到 r 中）。

class MedianFinder {
    PriorityQueue<Integer> l = new PriorityQueue<>((a,b)->b-a);
    PriorityQueue<Integer> r = new PriorityQueue<>((a,b)->a-b);
    public void addNum(int num) {
        int s1 = l.size(), s2 = r.size();
        if (s1 == s2) {
            if (r.isEmpty() || num <= r.peek()) {
                l.add(num);
            } else {
                l.add(r.poll());
                r.add(num);
            }
        } else {
            if (l.peek() <= num) {
                r.add(num);
            } else {
                r.add(l.poll());
                l.add(num);
            }
        }
    }
    public double findMedian() {
        int s1 = l.size(), s2 = r.size();
        if (s1 == s2) {
            return (l.peek() + r.peek()) / 2.0;
        } else {
            return l.peek();
        }
    }
}
时间复杂度：addNum 函数的复杂度为 O(log⁡n)O(\log{n})O(logn)；findMedian 函数的复杂度为 O(1)O(1)O(1)
空间复杂度：O(n)O(n)O(n)

以上这种方法，需要把所有数据都加载到内存中。当数据量很大时，就不能这样了，因此，这种方法适用于数据量较小的情况。5 亿个数，每个数字占用 4B，总共需要 2G 内存。如果可用内存不足 2G，就不能使用这种方法了，下面介绍另一种方法。

好文推荐

海量大数据处理面试题和思路总结，这一篇还蛮不错的，总结到位。

写在最后

加班之风盛行，昨晚11点走，真的栓Q，这篇算是下班后的学习小结吧。回头看看我之前写的东西，回顾一下，感觉不太熟练了。

海量数据问题集-持续更新

前言

Redis热Key问题

相关问法

套路解答

Redis海量数据查询

相关问法

套路解答

两大文件数据找交集

相关问法

套路解答

如何从海量数据中找出高频词？

相关问法

套路解答

如何在大量的数据中找出不重复的整数？

相关问法

套路解答

如何查询最热门的查询串？

相关问法

套路解答

如何从 5 亿个数中找出中位数？

相关问法

套路解答

好文推荐

写在最后