1。BitMapBit-map的基本思想是用一个位来标记一个元素对应的Value，Key就是这个元素。由于数据是以Bit为单位存储的，可以大大节省存储空间。（PS：着重节省存储空间）假设有这样一个需求：找出20亿个随机整数中是否存在某个数m，假设32位操作系统，Java中4G内存，int占4字节，1byte=8bits(1byte=8bit)如果每个数都存储在int中，即20亿个int，那么占用空间约为(2000000000*4/1024/1024/1024)≈7.45GifBit-by-位存储不同，20亿个数等于20亿位，占用空间大约为(2000000000/8/1024/1024/1024)≈0.233G一个数呢？刚才说了，每一位代表一个数，0代表不存在，1代表存在，符合二进制，这样我们就可以很方便的表示数字{1,2,4,6}：图片计算机的最小内存分配单位是字节，也就是8位，那如果要表示{12,13,15}呢？当然在另外8位上表示：如果图片是这样的话，好像变成了一个二维数组。1个int占32位，那么我们只需要申请一个长度为inttmp[1+N/32]的int数组即可存储，其中N代表要存储的这些数的最大值，所以：tmp[0]：可表示0~31tmp[1]：可表示32~63tmp[2]：可表示64~95。..这样，给定任意一个整数M，那么M/32就会得到下标，M%32就知道在这个下标的什么地方加了。这里有个问题，我们怎么把一个数字放进去呢？比如你想把数字5放进去，你是怎么做到的？首先5/32=0，5%32=5，也就是说应该在tmp[0]的第五个位置，然后我们将1向左移动5位，然后按位或图片替换为二进制，也就是图片。相当于86|32=11886|(1<<5)=118b[0]=b[0]|(1<<5)也就是说，如果要插入一个数，向左移动1代表该数的一位，然后与原数按位或运算化简，就是86+(5/8)|(1<<(5%8))因此，公式可以概括为：p+(i/8)|(1<<(i%8))其中，p代表当前值，i代表当前值要插入的号码。清空上面就是添加，那么要清空怎么办呢？还是上面的例子，假设我们要去掉6，应该怎么做呢？从图中可以看出，只需要将数字的位置设置为0将1向左移动6位，到达数字6所代表的位，然后逐位取反，最后与原数按位与，从而将位置设为0b[0]=b[0]&(~(1<<6))b[0]=b[0]&(~(1<<(i%8)))找到前面我们也说过，每一位代表一个数，1表示有（或存在），0表示无（或不存在）。通过将值设置为1或者0来实现加清零，那么判断一个数是否存在就是判断这个数所在的位是0还是1。假设，我们想知道3是否存在，那么我们只需要判断b[0]&(1<<3)如果这个值为0，则不存在。如果为1，则表示存在。对7内的5个元素（4、7、2、5、3）进行排序（假设这些元素不重复），我们可以使用Bit-map的方式来达到排序的目的。要表示8个数字，我们只需要8位（1字节）。首先，我们开辟1Byte的空间，将这些空间中的所有Bit都设置为0，然后将对应的位置设置为1。最后遍历一次Bit区域，输出为1的位的个数（2,3,4,5,7),这样就达到了排序的目的，时间复杂度为O(n)。优点：计算效率高，无需比较和移位；更少的内存占用，比如N=10000000；只有N/8=1250000Byte=1.25M内存占用缺点：所有数据不能重复。即无法对重复数据进行排序和查找。只有在数据比较密集的情况下，快速去重20亿整数中唯一整数的个数才有优势，而内存是不够容纳这20亿整数的。首先，根据“内存空间不足以容纳这5亿个整数”，我们可以快速关联Bit-map。下面的关键问题是如何设计我们的Bit-map来表示这20亿个数字的状态。其实这个问题很简单。一个数只有三种状态，即不存在、只有一个和重复。因此，我们只需要2位来存储一个数的状态。假设我们设置一个不存在的数字为00，存在一次为01，存在两次以上为11，那么我们大概需要2G左右的存储空间。接下来的任务就是将这20亿个数放入（store），如果对应的状态位为00，则改为01，表示存在一次；如果对应的状态位为01，则改为11，表示已经有一个，即出现多次；如果是11，对应的状态位不变，仍然表示出现了多次。最后通过统计01的状态位个数，得到不重复数的个数，时间复杂度为O(n)。快速查找这就是我们前面说的，int数组中一个元素是4个字节，占32位，然后除以32就知道这个元素的下标，求32的余数（%32）就知道在哪了位，如果该位为1，则表示存在。Summary&ReviewBitmap主要用于快速检索关键字的状态，通常要求关键字是一个连续的序列（或者关键字大部分是一个连续的序列），最基本的情况下，用1bit来表示一个关键字的状态（可以标记2个状态），但也可以根据需要使用2bit（表示4个状态）和3bit（表示8个状态）。Bitmap的主要应用：表示连续（或接近连续，即大部分会出现）关键词序列的状态（状态/关键词的个数越小越好）。在32位机器上，对于一个整数，比如inta=1，它在内存中占用32位，这是为了方便计算机运算。但是对于一些应用场景来说，这是一个巨大的浪费，因为我们可以用对应的32bit位来存储0-31的十进制数，而这就是Bit-map的基本思想。Bit-map算法就是利用这种思想来处理大量数据的排序、查询和去重。补充1在数字不溢出的前提下，对于正数和负数，左移一位相当于乘以2的1次方，左移n位相当于乘以1次方2的，右移一位相当于除以2，右移n位相当于除以2的n次方。<<左移相当于乘以2的n次方，例如：1<<6相当于1×64=64，3<<4相当于3×16=48\>右移相当于除以2的n次方，例如：64>>3相当于64÷8=8^异或，相当于求余数，例如：48^32相当于48%32=16补2呢不使用第三方变量，交换两个变量的值//方法一a=a+b;b=a-b;a=a-b;//方法二a=a^b;b=a^b;a=a^b;3.BitSetBitSet实现了一个位向量，根据需要增长。每个位都有一个布尔值。BitSet的位可以用非负整数来索引（PS：意思是每个位都可以代表一个非负整数）。可以找到、设置和清除位。可以通过逻辑运算符修改另一个BitSet的内容。默认情况下，所有位都具有默认值false。另外推荐：Java进阶视频资源图片图片图片可以看。和我们之前想的差不多，用了一个长数组来存储。初始长度为64，当SET值时，先向右移动6位（相当于64）计算在数组中的位置，然后改变状态位。看不懂没关系，看懂这两句就够了：intwordIndex=wordIndex(bitIndex);单词[wordIndex]|=(1L<
