【直通BAT】海量数据面试总结

朱雀 2022-02-15 13:05 276阅读 0赞

**目录**

*  **海量数据计算总结**
 *  **海量数据去重总结**

# 1. 计算容量 #

在解决问题之前，要先计算一下海量数据需要占多大的容量。常见的单位换算如下：

*  1 byte = 8 bit
 *  1 KB = 210 byte = 1024 byte ≈ 103 byte
 *  1 MB = 220 byte ≈ 10 6 byte
 *  1 GB = 230 byte ≈ 10 9 byte
 *  1 亿 = 108

1 个整数占 4 byte，1 亿个整数占 4\*108 byte ≈ 400 MB。

# 2. 拆分 #

可以将海量数据拆分到多台机器上和拆分到多个文件上：

*  如果数据量很大，无法放在一台机器上，就将数据拆分到多台机器上。这种方式可以让多台机器一起合作，从而使得问题的求解更加快速。但是也会导致系统更加复杂，而且需要考虑系统故障等问题；
 *  如果在程序运行时无法直接加载一个大文件到内存中，就将大文件拆分成小文件，分别对每个小文件进行求解。

有以下策略进行拆分：

*  按出现的顺序拆分：当有新数据到达时，先放进当前机器，填满之后再将数据放到新增的机器上。这种方法的优点是充分利用系统的资源，因为每台机器都会尽可能被填满。缺点是需要一个查找表来保存数据到机器的映射，查找表可能会非常复杂并且非常大。

![1240][]

*  按散列值拆分：选取数据的主键 key，然后通过哈希取模 hash(key)%N 得到该数据应该拆分到的机器编号，其中 N 是机器的数量。优点是不需要使用查找表，缺点是可能会导致一台机器存储的数据过多，甚至超出它的最大容量。

![1240 1][]

*  按数据的实际含义拆分：例如一个社交网站系统，来自同一个地区的用户更有可能成为朋友，如果让同一个地区的用户尽可能存储在同一个机器上，那么在查找一个用户的好友信息时，就可以避免到多台机器上查找，从而降低延迟。缺点同样是需要使用查找表。

![1240 2][]

# 3. 整合 #

拆分之后的结果还只是局部结果，需要将局部结果汇总为整体的结果。

注：大部分海量数据都可以使用hash取模来处理，因为同一个值hash取模后一定会分配到同一个位置。如果内存实在小，N的值可以取大一些。再者，Hadoop和spark也是处理海量数据的方案，不过非大数据方向应该不做要求。

--------------------

下面是海量数据去重问题：

# 1. 问题描述 #

对于海量数据，要求判断一个数据是否已经存在。这个数据很有可能是字符串，例如 URL。

# 2. HashSet #

最直观的方法是使用 HashSet 存储，那么就能以 O(1) 的时间复杂度判断一个数据是否已经存在。

考虑到数据是海量的，那么就需要使用拆分的方式将数据拆分到多台机器上，分别在每台机器上使用 HashSet 存储。我们需要使得相同的数据拆分到相同的机器上，可以使用哈希取模的拆分方式进行实现。

# 3. BitSet #

如果海量数据是整数，并且范围不大时，就可以使用 BitSet 存储。通过构建一定大小的比特数组，并且让每个整数都映射到这个比特数组上，就可以很容易地知道某个整数是否已经存在。因为比特数组比整型数组小的多，所以通常情况下单机就能处理海量数据。

![1240 3][]

以下是一个 BitSet 的实现，当然在实际开发中可以直接使用语言内置的实现。

class BitSet { 
        int[] bitset;
    
        public BitSet(int size) { 
            bitset = new int[(size >> 5) + 1]; // divide by 32
        }
    
        boolean get(int pos) { 
            int wordNumber = (pos >> 5); // divide by 32
            int bitNumber = (pos & 0x1F); // mod 32
            return (bitset[wordNumber] & (1 << bitNumber)) != 0;
        }
    
        void set(int pos) { 
            int wordNumber = (pos >> 5); // divide by 32
            int bitNumber = (pos & 0x1F); // mod 32
            bitset[wordNumber] |= 1 << bitNumber;
        }
    }

使用 BitSet 还可以很容易地解决一个整数出现次数的问题，例如使用两个比特数组就可以存储 0~3 的信息。其实判重问题也可以简单看成一个数据出现的次数是否为 1，因此一个比特数组就够了。

# 4. 布隆过滤器 #

布隆过滤器能够以极小的空间开销解决海量数据判重问题，但是会有一定的误判概率。它主要用在网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统。

布隆过滤器也是使用 BitSet 存储数据，但是它进行了一定的改进，从而解除了 BitSet 要求数据的范围不大的限制。在存储时，它要求数据先经过 k 个哈希函得到 k 个位置，并将 BitSet 中对应位置设置为 1。在查找时，也需要先经过 k 个哈希函数得到 k 个位置，如果所有位置上都为 1，那么表示这个数据存在。

由于哈希函数的特点，两个不同的数通过哈希函数得到的值可能相同。如果两个数通过 k 个哈希函数得到的值都相同，那么使用布隆过滤器会将这两个数判为相同。

可以知道，令 k 和 m 都大一些会使得误判率降低，但是这会带来更高的时间和空间开销。

布隆过滤器会误判，也就是将一个不存在的数判断为已经存在，这会造成一定的问题。例如在垃圾邮件过滤系统中，会将一个邮件误判为垃圾邮件，那么就收不到这个邮件。可以使用白名单的方式进行补救。

![1240 4][]

# 5. Trie #

Trie 树又叫又叫字典树、前缀树、单词查找树，它是一颗多叉查找树。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。

如果海量数据是字符串数据，那么就可以用很小的空间开销构建一颗 Trie 树，空间开销和树高有关。

![1240 5][]

Leetcode : Implement Trie (Prefix Tree)

class Trie { 
        private class Node { 
            Node[] childs = new Node[26];
            boolean isLeaf;
        }
    
        private Node root = new Node();
    
        public Trie() { 
        }
    
        public void insert(String word) { 
            insert(word, root);
        }
    
        private void insert(String word, Node node) { 
            if (node == null) return;
            if (word.length() == 0) { 
                node.isLeaf = true;
                return;
            }
            int index = indexForChar(word.charAt(0));
            if (node.childs[index] == null) { 
                node.childs[index] = new Node();
            }
            insert(word.substring(1), node.childs[index]);
        }
    
        public boolean search(String word) { 
            return search(word, root);
        }
    
        private boolean search(String word, Node node) { 
            if (node == null) return false;
            if (word.length() == 0) return node.isLeaf;
            int index = indexForChar(word.charAt(0));
            return search(word.substring(1), node.childs[index]);
        }
    
        public boolean startsWith(String prefix) { 
            return startWith(prefix, root);
        }
    
        private boolean startWith(String prefix, Node node) { 
            if (node == null) return false;
            if (prefix.length() == 0) return true;
            int index = indexForChar(prefix.charAt(0));
            return startWith(prefix.substring(1), node.childs[index]);
        }
    
        private int indexForChar(char c) { 
            return c - 'a';
        }
    }

# 参考资料 #

*  Bloom Filters: Is element x in set S?
 *  程序员面试金典
 *  程序员代码面试指南

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：  
公众号\*\*`菜鸟名企梦`**后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；  
公众号**`菜鸟名企梦`**后台发送“资料”:即可领取**5T精品学习资料\*\*、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**  
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240 6]

**推荐阅读**

**[☞【直通BAT】一篇文章搞定java容器面试][BAT_java]**

[1240]: /images/20220215/9fde6485735342ab9a62a502f97ab7ee.png
[1240 1]: /images/20220215/52603c2d4e984c21897b50e952c797c8.png
[1240 2]: /images/20220215/0ca208b1cdc14b38951bb198d886442b.png
[1240 3]: /images/20220215/a2ad769dc8a44f5186798693c1b39b2d.png
[1240 4]: /images/20220215/115b3b44e99948989a86501583f5987c.png
[1240 5]: /images/20220215/4c13fd6d24e54253a4599313fb26b834.png
[1240 6]: /images/20220215/f0c7545d479e4017ba8297eaa0242765.png
[BAT_java]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247485255&idx=1&sn=73cba8342196c477b85b42195546d95f&chksm=eb5124b3dc26ada5070b85eaa005a52d43127f4a09d8138706ae018ef305435a27801d81494c&scene=21#wechat_redirect