首页   快速返回

如何判断一个数是否在40亿个整数中     所属分类 java
假设都为正整数

一般都会想到用 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

上一篇     下一篇
当下最好的生意

一个小故事讲明白区块链

币圈吹牛逼套路汇总

延迟队列原理及使用场景

JVM CMS 常用参数

JVM CMS 介绍