1.序言在实际开发中，经常会遇到如下需求：判断当前元素是否存在于已知集合中，并为已知集合中的元素维护一个HashSet。可以用O(1)的时间复杂度来判断结果，Java或者Redis都提供了相应的数据结构。使用这种方式除了占用内存空间外，几乎没有其他缺点。当数据量达到亿级别时，对内存空间的占用就明显体现出来，而BitMap就是解决此类问题的一种方式。二、BitMap结构1、内存消耗分析RedisBitMap可以存储的数据范围是[0,2^32-1]，超出了Integer.MAX_VALUE的上限。为了简化讨论，假设所讨论的集合元素的范围是[0,Integer.MAX_VALUE]，可以是任意数字。HashSet数据结构占用的内存空间只与集合中的元素个数（N）有关。当集合中元素个数为N时，所需内存空间约为N*4/1024/1024MB，1亿条数据占用内存空间约为381MB。基于Redis的BitMap占用的空间与集合中元素的个数无关，而是与集合中元素的最大值直接相关，所以BitMap占用的内存空间范围为[N/8/1024/1024,Integer.MAX_VALUE/8/1024/1024]。//测试1亿，5亿，10亿，Integer.MAX_VALUEListitems=Arrays.asList(100000000,500000000,1000000000,Integer.MAX_VALUE);对于（整数项目：项目）{intsize=item/8/1024/1024;System.out.printf("如果集合中的最大值为%-10s，占用的内存空间为%3sMB%n",item,size);}这里是一组测试参考数据if集合中的最大值collection为100000000，占用内存空间为11MB。如果集合中的最大值为500000000，则占用内存空间为59MB。如果集合中的最大值为1000000000，则占用内存空间为119MB。如果集合为最大值为2147483647，占用内存空间为255MB。当集合中的数据增长到10亿时，使用BItMap占用的内存最大约为255MB，而使用HashSet则增加到3.8GB。2、命令行操作BitMap可以直接使用Redis命令行操作BitMap，将偏移位置的值标记为1，表示当前数据存在。默认情况下，未标记位置的值为0。#默认bit不赋值0，当数据存在set中时，对应bit赋值1SETBITkeyoffsetvalue#检查对应bit数据是否存在（1表示存在，0表示不存在不存在）GETBITkeyoffset3，客户端操作BitMap这里提供了一个SpringBoot生态的RedisUtils工具类，内部封装了操作RedisBitMap的工具方法。//标记当前位置为trueRedisUtils.setBit(BIT_MAP_KEY,orderId,true);//获取指定位置的值（对应值是否存在）RedisUtils.getBit(BIT_MAP_KEY,orderId)以上工具类的依赖是如下，如果没有找到Jar包，请直接使用Maven原仓库源，阿里云尚未完成同步。xin.altitude.cmsucode-cms-common1.4.34.时间和空间复杂度BitMap时间存储和检索的复杂度为O(1)，下标可以直接根据值进行映射。BitMap占用的内存空间复杂度为O(n)，与集合中元素的最大值正相关，与集合中元素的个数无关。三、BitMap应用1、避免缓存穿透缓存穿透是指当前请求的数据在缓存中不存在，需要访问数据库获取数据（请求的数据在数据库中不存在）。缓存渗透会给数据库带来压力，恶意的缓存渗透甚至会导致数据库宕机。使用BitMap动态维护一个集合。在访问数据库之前，先查询该数据的主键在集合中是否存在，作为访问数据库的依据。向BitMap添加或删除数据是轻量级操作，检查操作的准确性取决于动态集合所维护的闭环的完整性。例如，向数据库中添加数据需要向BitMap中添加数据，从数据库中删除数据需要从BitMap中移除数据。如果需要严格校验可靠性，可以单独维护一个分布式定时任务，定时更新BitMap数据。2、与Bloomfilters的区别Bloomfilters的应用场景与BitMap相似，但也有一定的区别。给定一个数，BitMap可以准确知道它是否存在于已知集合中；Bloomfilter可以准确判断是否不在集合中，但无法确定是否存在于集合中。BitMap中添加或删除数据的时间复杂度为O(1)，方便快捷。创建布隆过滤器很容易，但是删除数据的操作比较麻烦。在一些需要准确判断的场景下，首选BitMap，比如判断一个手机号是否已经注册。4.总结RedisBitMap并不是一个新的数据结构，而是使用string类型封装了一层，看起来像是一个新的数据结构。BitMap不像是一种技术，更像是一种算法，在时间复杂度和空间复杂度之间寻找平衡点。BitMap的其他应用场景如签到、统计在线人数等，如果喜欢这篇文章，请点??赞??支持一下。有需要的可以微信dream4s联系我。相关源码在GitHub，视频讲解在B站，本文收集于博客世界。
