皮皮网

1.BitMap原理与实现
2.BitMap和BitSet
3.位向量工作原理
4.使用函数计算素数个数并求和：输入两个正整数m和n（1≤m，源码n≤500），源码要求定义和调用函prime
5.BitSet简介

BitMap原理与实现

        比较经典的问题是： 在只能够使用2G的内存中，如何完成以下操作：

        ①：对亿个不重复的整数进行排序。

        ②：找出亿个数字中重复的数字。

        无论是排序还是找重复的数字都需要将这亿个数字加入到内存中在去进行操作，很明显，题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的

        * 4/（* * ） = 3.G

        那么这时候就需要用到 BitMap结构了

        bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,源码而map的key值正是这个数字本身。

        相比于一般的数据结构需要用4个byte去存储数值本身，相当于是节省了 4*8：1 = 倍的内存空间

        bitMap不一定要用bit数组,可以使用 int,long等等的基本数据类型实现，因为其实质都是在bit位上存数据，用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少

            例如：java中的BitSet使用Long数组

        BitMap的实现当然少不了位运算，先来明确几个常见位运算，这是实现BitMap的基础：

        set(bitIndex): 添加操作

            1 .确定该数处于数组中的哪个元素的位上

             int wordIndex = bitIndex >> 5;

        因为我用的是int[]实现，所以这里右移 5 位（2^5 = ）

            2 .确定相对于该元素中的位置偏移

             int bitPosition = bitIndex & ((1 << 5) - 1);

        这里相当于是 bitIndex % （1<<5）的取模运算，因为当取模运算的除数是2的次幂，所以可以使用以下的位运算来计算，提升效率（对比HashMap的容量为什么总是2的幂次方的问题，HashMap求下标时也是使用 hash&(n-1)）

        tips: 位运算的优先级是低于+,-等等的，所以要加上括号,防止发生不可描述的错误

            3 .将该位置1

             bits[wordIndex] |= 1 << bitPosition;

        相当于是将指定位置处的bit值置1，其他位置保持不变，也就是将以这个bitIndex为key的位置为1

        tips: 这里是参考了网上的各位大佬的文章,取余 + 按位或，又对比了下BitSet的源码：

             words[wordIndex] |= (1L << bitIndex);

        没有取余操作，直接|，这两个一样吗？答案当然是一样的

        举个栗子：

             1 << == 1<<     

             1L << ==1L<<

        即对于int和long型数据，直接左移其位数相当于是附带了对其的取模操作

        总结：使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。

        Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构

        当一个元素加入布隆过滤器中的时候，会进行哪些操作：

        当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行哪些操作：

        然后，一定会出现这样一种情况：不同的字符串可能哈希出来的位置相同（可以适当增加位数组大小或者调整我们的哈希函数来降低概率）,因此：布隆过滤器可能会存在误判的情况

        总结来说就是： 布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

        Bloom Filter的应用: 常用于解决缓存穿透等场景。

BitMap和BitSet

        Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，可以很大力度的节省空间，常用于对大量整数做去重和查询操作。

        1byte=8bit

        1kb=byte

        1mb=kb

        1gb=mb

        java中 int类型占用4个字节=4*8=bit

        从上述结果来看，按位存储比按字节存储数字节约了（7./0.-1约等于倍空间），而且按字节存储根据内存4G的要求无法一次性在内存中进行处理。

        众所周知，每一位的取值无非就是0和1，给每一位编号，那么用0表示数字存在，1表示数字不存在。

        假如现在有一个字节也就是8位的空间，那么按照BitMap，可以表示8个数字，

        按照上图所示，该字节的8位表示了整数数组[6,5,2,0]。那么java中int类型占用了4个字节，也就是位，那么就可以最多表示个数字。超过位数字呢？那就使用两个以上int去表示。

        假设我们要存储的数字最大值位N，则申请int temp[1+N/]的数组空间，其中：

        temp[0]可表示 0~

        temp[1]可表示 -

        .....以此类推

        给定任一整数M，M数字所在数组中的下标位置就应该是M/，M数字所在的位就是M%

        总共两步

1.找到整数所在数组temp的下标

        int index = M/

2.将temp[index] 的第M%位置1

        temp[index]=temp[index] | (1<<(M%))

        根据bitMap的原理可知，想要清除掉一个数字，那就是将对应的位置0

        总共两步

1.找到整数所在数组temp的下标

        int index = M/

2.将temp[index] 的第M%位置0

        temp[index]=temp[index] &（~ (1<<(M%))）

        根据每一位代表一个数字，1表示存在，0表示不存在，那么只需要判断整数对应位是否位1即可

        总共两步

1.找到整数所在数组temp的下标

        int index = M/

2.将temp[index] 的第M%位置0

        temp[index] &(1<<(M%) ！= 0？"存在":"不存在"

        运行结果

        BitSet就是实现了Bit-Map算法。BitSet位于java.util包下，从JDK1.0开始就已经有了。该类实现了一个按需增长的位向量。位集的每一个组件都有一个boolean类型的值。BitSet的每一位代表着一个非负整数。可以检查、设置、清除单个位。一个BitSet可以通过逻辑与、逻辑或、逻辑异或去修改另一个BitSet。默认情况下，所有位的标识都是false。

        设值

        清除

        检查

        BitSet有三种构造方法，我们直接来看无参构造器

        可以看到BitSet是使用long数组存储。那么long类型占用8个字节，即位，一个long类型可表示个数字。默认设置BitSet可表示最大的位数为位。与上述自己实现的基本类似。

        再来看set方法

        get方法

        clear方法

        可以看到JDK中的BitSet实现原理与第三节中一样，采用Bit-Map思想，BitSet封装较多的API，可供开发者们随意使用。

位向量工作原理

       位向量，也叫位图，源码是源码一个我们经常可以用到的数据结构，在使用小空间来处理大量数据方面有着得天独厚的源码通用oa系统源码优势；位向量的定义就是一串由0.1组成的序列。

       Java中对位向量的源码实现类时Java.util.BitSet;C++标准库中也有相应的实现，原理都是源码一样的； BitSet源码也很简单，很容易看懂 ，源码如果读者在对位向量有一定的源码了解后，可以通过读源码来了解BitSet的源码具体实现。

       一个bit上有两个值，源码正好可以用来判断某些是源码非状态的场景，在针对大数据场景下判断存在性，源码BitSet是源码ubuntu源码在线查看相比其他数据结构比如HashMap更好的选择，在Java中，位向量是用一个叫words的long型数组实现的，一个long型变量有位，可以保存个数字；比如我们有[2,8,6,,]这5个数要保存，一般存储需要 5*4 = 字节的存储空间。但是如果我们使用Java.util.BitSet进行存储则可以节省很多的空间只需要一个long型数字就够了。BitSet只面向数字只面向数字使用，自己写源码教程对于string类型的数据，可以通过hashcode值来使用BitSet。

       由于，1 << , 1<<, 1<< 这些数字的结果都为1，BitSet内部，long[]数组的大小由BitSet接收的最大数字决定，这个数组将数字分段表示[0,科目一考题源码],[,],[,]...。即long[0]用来存储[0,]这个范围的数字的“存在性”，long用来存储[,]，依次轮推，这样就避免了位运算导致的冲突。原理如下：

       |------------|----------|----------|----------|----------| |

       Java的BitSet每次申请空间，申请位，即一个long型变量所占的docker源码不会go位数；

使用函数计算素数个数并求和：输入两个正整数m和n（1≤m，n≤），要求定义和调用函prime

       import java.util.*;

       public class Main{

       public static void main(String[]args){

       Scanner sc=new Scanner(System.in);

       int a=sc.nextInt();//m

       int b=sc.nextInt();//n

       ArrayList&lt;Integer&gt;list=new ArrayList&lt;Integer&gt;();//定义一个list存放素数

       while(a&lt;=b){

       //如果a为素数，将其放入list中

       if(prime(a,list)){

       list.add(a);

       }

       a++;

       }

       //输出

       if(list.size()==0){

       System.out.print("none");

       return;

       }

       System.out.print(list.size()+"");

       int sum=0;

       Iterator&lt;Integer&gt;iter=list.iterator();

       while(iter.hasNext()){

       sum=sum+iter.next();

       }

       System.out.print(sum);

       }

       //判断该数是否为素数

       public static boolean prime(int n,ArrayList&lt;Integer&gt;list){

       if(n==1){

       return false;

       }

       int max=(int)Math.sqrt(n);

       for(int i=0;i&lt;list.size();i++){

       if(n%list.get(i)==0){

       return false;

       }

       if(list.get(i)&gt;max){

       return true;

       }

       }

       return true;

       }

       }

扩展资料：

       在高级编程语言中，如果你想使用某个类或接口，那就要用import导入这个类，如在Java中编写servlet，使用httpServlet，那就要在文件的开头（包之后）写上，

       import javax.servlet.http.*;表示导入javax.servlet.http这个包中所有的文件。

       import java.util.*;导入java.util包中的类接口。

       Java中import的作用是导入要用到的包中的类接口。import就是在java文件开头的地方，先说明会用到那些类别。接着我们就能在代码中只用类名指定某个类，也就是只称呼名字，不称呼他的姓。

       这其中包的作用就是给java类进行分拣分类，不同业务逻辑的java类放在同一个包中。比如实体包，工具包。

       Java的实用工具类库java.util包。在这个包中，Java提供了一些实用的方法和数据结构。本章介绍Java的实用工具类库java.util包。在这个包中，Java提供了一些实用的方法和数据结构。

       例如，Java提供日期(Data)类、日历(Calendar)类来产生和获取日期及时间，提供随机数(Random)类产生各种类型的随机数，还提供了堆栈(Stack)、向量(Vector)、位集合(Bitset)以及哈希表(Hashtable)等类来表示相应的数据结构。

参考资料：

百度百科——java.util

       

BitSet简介

        基本原理和用途

        BitSet即位图，是一个很长的“0/1”序列，他的功能就是存储0或者1。

        他的这个特点使得在java环境中存储一个数要比直接存一个int节省很多内存空间（一个int占4个字节位，而用BItSet“存放”一个数只需要1个位）。

        比如我们有{ 1,3,5,7}需要存放，内存中占用了4个int的长度即*4(bit)，如果使用BitSet，就是这个样的[...,1,0,1,0,1,0,1]，只需要占用几个bit就可以表示。1个G的内存有8 * * * = 8. * ^9个bit，也就是可以存放亿+个数。

        BitSet的初始大小为1个long的大小，即8字节个bit。如果我们创建的BitSet指定了位数，系统会根据情况取成的整数倍个bit，即整数个long的位数，这样做是为了内存补齐。

        BitSet适合用于无重复，整数，常用于大数据场景或者日志统计。

        参考文章：

        Java中BitSet的使用及详解