如何在3亿个整数存储0，2亿个数据，判断是否存在，限制内存500M

如何在3亿个整数存储0，2亿个数据，判断是否存在，限制内存500M

问题：如何在3亿个整数存储0，2亿个数据，判断是否存在，限制内存500M 解决方案 1，分治， 2，布隆过滤器 3，Redis 4，Hash，开辟3亿数组 5，数组，2亿个数组 位运算 左移 8： 0000 0000 0000 000 0000 0000 0000 1000–>2^3=8 <<2： 0000 0000 0000 000 0000 0000 0010 0000–>2^5=32 右移 2 0000 0000 0000 000 0000 0000 0000 0010–>2^1=2 乘法：2/4 2>>2 除法：8/4 8>>2 无符号移动 位&；同上，同为1就是1，否则为0； 位| ；只要有一个位1则为1，否则为0 解决思路 一个bit位可以表示32个数 【2，3，32，65】，最大，2亿，最小0； data[0]=0000 0000 0000 000 0000 0000 0000 0110 0~31 data[1]=0000 0000 0000 000 0000 0000 0000 0001 32~63 data[2]=0000 0000 0000 000 0000 0000 0000 1010 64~95 。。。。。。 data[6400000000]=0000 0000 0000 000 0000 0000 0000 1010 存储199999968~2000000000 这样空间节省32倍； 32/32=1;32%32=0第一个数组的第二位 65/32=3;’65%32=1 在第三个数组的第二个位置 开2亿 int数组 占位 2亿*4(byte)/1024(kb)/1024(mb)=762M，用下标，用内存 byte数组 占位 2亿/1024(kb)/1024(mb)=86M，用下标，用内存 bitmap 762(m)/32= 23M，只需要23， 因为一个bitmap 存储32个数 package com.utils; public class BitMap { /** * 有点 * 1，对于大数据速度快 o(n); * 2，节省空间 * 3，适用场景大数据。签到类似的场景 * 缺点 * 1，数据不能重复 只有0和1 * 2，数据量小时没有优势 * 3，无法处理字符串 *

* 如何用 byte数组，则一个数组标示8个数， * 如果用 int数组 则可以一个值存储32个数； *

* 二外知识 * Java的位运算符:与（&）、非（~）、或（|）、异或（^） */ byte[] bits; int max;//最大值 //byte数组位运算的位置 private final int byte_w = 3; public BitMap(int max) { //赋值最大值，并且初始化bits数据大小； this.max = max; bits = new byte[(max >> byte_w) + 1]; } /** * 添加元素 * * @param n 元素的值 */ public void add(int n) { int bitIndex = n >> byte_w;//除以8标示计算在哪个数组里面，即是数组下标； int loc = n & 7; //使用&运算，性能提升很多,相当于 n%8; //接下来将bit 数组里面的数据对应的 loc 的index 设置为1 bits[bitIndex] |= 1 << loc; } /** * 查找 * * @param n * @return */ public boolean find(int n) { //如果排除数字越界问题 if (n < 0 | n > max) { return false; } int bitIndex = n >> 3;//除以8标示计算在哪个位置 int loc = n & 7; //使用&运算，性能提升很多,相当于 n%8; int flag = bits[bitIndex] & (1 << loc); return flag != 0; } /** * 删除元素,相当于将改元素对应的数组从0置位1 * * @param n 元素的值 */ public void remove(int n) { if (n < 0 | n > max) { return; } int bitIndex = n >> byte_w;//除以8标示计算在哪个数组里面，即是数组下标； int loc = n & 7; //使用&运算，性能提升很多,相当于 n%8; //接下来将bit 数组里面的数据对应的 loc 的index 设置为1 System.out.println(bits[bitIndex]); bits[bitIndex] &= ~(1 << loc); System.out.println(bits[bitIndex]); } /** * 验证结果 * * @param args */ public static void main(String[] args) { BitMap bitMap = new BitMap(100); bitMap.add(1); bitMap.add(3); bitMap.add(8); System.out.println(bitMap.find(5)); System.out.println(bitMap.find(3)); bitMap.remove(1); System.out.println(bitMap.find(1)); } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。