栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

十亿数据量 判断元素是否存在

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

十亿数据量 判断元素是否存在

核心是采用:bitMap

假设一个场景,要存0-7之内的数字[3,5,6,1,2],尽量的节省空间。


传统思路就是单纯使用集合存储:

使用redis的set集合存储,但若是数据量放大到十亿级别,集合的所占用的内存会很是大。并且,redis单个实例最大为2.5亿。

另外一种思路是使用BitMap:

表示[3,5,7,1,2],咱们能够用8bit的空间来存储,每一个数字都在对应的位置中以1的方式表示

位置7位置 6位置 5位置 4位置 3位置 2位置 1位置 0
10101110

这样,相当于每一位只存储了一个字符,只需要知道该下标是否为1,即可。

这里是不是就会发现,存储的数据必须为正整数,才可以使用bitMap进行存储。

所以我们需要做的就是,把数据转换成:正整数。

我们采用google开源的cityhash算法,先将string转换为32位整数,然后构建512MB的bitmap存储这些整数。

为什么是32位呢,因为redis实现了bitMap算法,可以从用redis的setBit进行数据存储。但是因为redis官方规定:setting bit number 2^32 -1;也就是说,存储的正整数必须小于32位。

有一个很好的工具类hutool,实现了cityhash算法,直接引用:

        
            cn.hutool
            hutool-all
            5.8.2
        
        String code="237021200005599";
        byte[] codebyte = code.getBytes();
        int codeInt = HashUtil.cityHash32(codebyte);
        System.out.println(codeInt);

 但是由于,HashUtil.cityHash32返回的是int,是一个整数,redis的bitMap仅支持正整数,存在差异性,所以我不会了。最好存进去的数就是一个32位正整数。

还有一个办法就是下面这个:不要使用redis的bitMap

RoaringBitmap 和 Roaring64Bitmap

32位以下数据直接使用 RoaringBitmap;(包含负数)

64位以下数据直接使用 Roaring64Bitmap;(包含负数)

使用hutool工具,转换成64位的整数,Roaring64Bitmap直接支持Long类型。

        
            org.roaringbitmap
            RoaringBitmap
            0.9.0
        
        //将字符串转换成64位bit
        String code="ddadsadsa";
        byte[] codebyte = code.getBytes();
        Long codeInt = HashUtil.cityHash64(codebyte);

        //将Long插入到bitMap中
        Roaring64Bitmap rr = Roaring64Bitmap.bitmapOf();
        rr.add(codeInt);

        long l = -4543844943551498834L;

        //判断是否存在
        System.out.println(rr.contains(l));

参考文章:BitMap与RoaringBitmap、JavaEWAH - JavaShuo

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963100.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号