假设都为正整数

一般都会想到用 hashmap 或者 排序之后使用二分查找也称折半查找（Binary Search）

这种简单粗暴的方法比较消耗内存


一个整数4个字节 100百万个整数占用约 4M内存  1亿个整数占用约400M内存 
40亿个整数占用约16G内存


比较巧妙的方法是使用 java中自带的 BitSet  java.util.BitSet

BitSet 是一个可以自动扩展的bitmap 可以将索引对应的位置设置成0或1
底层使用long数组来保存位信息 ，long数组按需自动扩展

一个long 8个字节 64位，对应64个整数 64*4=256字节，可节省大量内存


读取40亿个整数初始化bitset 然后使用 get方法判断是否存在  
public boolean get(int bitIndex)


随机生成1000W个整数 然后查询0到9是否存在

 

bitmap/bitset 常用使用场景  桶排序 去重 查询 Bloom Filter(布隆过滤器) 等 


BitSet原理及测试代码 

https://gitee.com/dyyx/hellocode/blob/master/src/dyyx/test/BitsetTest.java