这里写目录标题

• 问题
• 方法0、mysql
• 方法1：分布式集合/分布式哈希
• 方法2：多路归并排序
• • 整体流程
  • 手撕归并排序
• 方法3：桶排序
• • 整体思路
  • 手撕桶排序
• 方法4：BitMap
• • 什么是bitmap
  • 整体思路
  • 手撕bitmap
• 方法5：布隆过滤器
• • 什么是布隆过滤器
  • 整体思路
  • 手撕布隆过滤器

问题

场景1：10亿个正整数，给定一个数值，如何快速判定该数值是否在10亿个正整数当中？假如机器只有1G内存？一个整数4个字节，10亿个正整数，40亿个字节~4G内存，而机器的内存只有1G

场景2：10亿个正整数，快速排序，假如机器只有1G内存？

方法0、mysql

将数据存到mysql中，如果并且为该列设置索引，如果可以从表中select到，就可以判定数值在其中

方法1：分布式集合/分布式哈希

如果有很多机器，但是每个机器的上线是 1G的内存的话，可以考虑采用redis的set
10台机器，每台机器1G，将10亿个整数分成4份加载到4台机器中（分别通过redis存入缓存sadd（set.add））

方法2：多路归并排序

整体流程

1、将10亿数据分成4组，每组1G数据，先对每组数据进行快排/归并排序
2、再将排序后的4组数据，各拿0.25G数据出来，进行归并，一组的0.25数据处理完，补充该组的下一个0.25

手撕归并排序

方法3：桶排序

整体思路

1、依次遍历整数，按照其大小分到n个桶中，（如果存在数据量很大的桶，将桶再分割为更小的桶）
2、将n个桶中的数据进行快排
3、再将排序后的数据，分桶输出即可

手撕桶排序

方法4：BitMap

什么是bitmap

本来一个int类型的数据，占4个字节，32个位，如果用位来表示的话，一个int只需要占对应下表的一个位即可
10亿个整数，用int表示：约4G数据
如果最大值是10亿，用位图表示：4/32G数据，那么1G内存就可以直接处理

整体思路

1、用java写bitmap结构或者直接使用redis中的bitmap结构
2、直接将全部的输入到bitmap中
3、判断bitmap中是否有给定的数值

手撕bitmap

方法5：布隆过滤器

什么是布隆过滤器

由一个位图和多个无偏hash函数组成

整体思路

1、如果判断存在时允许有一定的误差可以考虑布隆过滤器
2、使用redis的布隆过滤器添加全部输入
3、通过布隆过滤器判断给定数值是否不存在

手撕布隆过滤器