海量数据处理|位图、布隆过滤器、常见例题

位图

• 题：40亿，不重复的无符号整数，如何判断某个数是否存在

• 

• 过程

  • 建立数组，大小为40亿*1bit=5亿字节，初始值全为0
  • 遍历数据，将数据作为下标，把下标的值改为1
  • 查找某个数是否存在，即查看[某数]是否等于1

布隆过滤器

• 题：40亿，非数字类型，判断某个值是否存在

• 

• 过程

  • 建立数组，大小为40亿*1bit=5亿字节，初始值全为0

  • 遍历所有用户，每个用户分别计算hash1，hash2，hash3，把所有得到的结果作为下标，将下标所在的值改为1

  • 查找某个值是否存在，计算该用户的三个hash值

    • 若三个值不全为1，一定不存在
    • 若三个值全为1，大概率存在

例题

1.一个日志文件中保存了一些IP地址，如何找到出现次数最多的IP地址

• 遍历文件，使用map获取每个ip（key）的出现次数（value），再在map中找到最大的value

2.当IP地址的数量非常大，map在内存中存不下

• 分段处理：将大文件拆成多个小文件，分别处理

  • 

  • 切分大文件为小文件

    • 将相同的IP地址分到同一个文件中

      • Group（相同的IP地址）= 相同的编号

  • 找到每个小文件中次数最多的IP记为代表

  • 在代表中找到次数最多的IP

3.给定100亿个整数，设计算法找到只出现一次的整数

• 分段处理

• 压缩

  • 某数n存在三种情况：a.一次都不出现 00；b.只出现一次 01；c.出现超过一次 10。遍历数据并记录

4.给定两个文件AB分别有100亿个整数，只有1G内存，问如何找到两个文件的交集

• 分段处理

  • 使用hash函数将A文件的所有整数映射到1000个文件中，每个文件有1000万个整数，大约40M内存， 内存可以放下，把1000个文件记为 a1,a2,a3…a1000
  • 用同样的hash函数映射B文件到1000个文件中，这1000个文件记为b1,b2,b3…b1000
  • 由于使用的是相同的hash函数，所以两个文件中一样的数字会被分配到文件下标一致的文件中，分别对a1和b1求交集，a2和b2求交集，ai和bi求交集，最后将结果汇总，即为两个文件的交集

• 压缩

  • 某数n存在三种情况：a.两个文件都不存在 00；b.存在A文件 01；c.存在B文件 11；d.两个文件都存在 11。遍历数据并记录

总结

• 分段处理

  • 核心在文件如何分

• 压缩

  • 位图（数字）
  • 布隆过滤器（非数字、有概率性）