数据结构 Bitmap（位图）示例 - 用户签到系统

下面提供一个基于Java BitSet的完整用户签到系统设计方案涵盖需求分析、核心思路、关键代码与测试示例。一、设计思路1. 需求定义用户每天可以签到一次重复签到不会覆盖或重复计数。支持查询任意用户在某一天是否已签到。统计某个月份的签到总天数。查询截至某一天的连续签到天数按自然日连续中间不能断开。2. 存储模型使用MapLong, BitSet存储每个用户的签到记录Key用户IDLongValueBitSet其中每个 bit 代表一天。位索引 从「基准日期」到签到日期的天数差。基准日期固定为2020-01-01也可以调整为系统上线日期。优点支持任意未来日期BitSet 会自动扩容空间利用率高。内存估算假设系统运行 10 年约 3652 天每个用户的 BitSet 约3652 bits ≈ 457 字节。1000 万活跃用户 → 约 4.3 GB 内存可接受实际生产会使用 Redis Bitmap但本例展示内存实现。3. 核心操作时间复杂度签到/查询O(1)月签到统计O(当月天数)连续签到统计最坏 O(连续天数) 实际会提前终止4. 线程安全使用ConcurrentHashMap存储对每个用户的BitSet进行读/写时加锁synchronized避免并发修改异常。二、完整 Java 代码importjava.time.LocalDate;importjava.time.temporal.ChronoUnit;importjava.util.Map;importjava.util.concurrent.ConcurrentHashMap;/** * 基于 BitSet 的用户签到系统 * 功能签到、检查、月签到统计、连续签到天数 */publicclassSignInService{// 基准日期系统上线日所有签到天数偏移基于这一天privatestaticfinalLocalDateBASE_DATELocalDate.of(2020,1,1);// 存储每个用户的签到位图privatefinalMapLong,BitSetuserSignMapnewConcurrentHashMap();/** * 用户签到 * param userId 用户ID * param date 签到日期 * return 是否签到成功若当天已签到返回false */publicbooleansignIn(LonguserId,LocalDatedate){// 不能签未来的到if(date.isAfter(LocalDate.now())){thrownewIllegalArgumentException(不能签未来的日期);}intoffsetgetOffset(date);BitSetbitSetuserSignMap.computeIfAbsent(userId,k-newBitSet());synchronized(bitSet){if(bitSet.get(offset)){returnfalse;// 已签到}bitSet.set(offset);returntrue;}}/** * 检查用户在某天是否已签到 */publicbooleanisSigned(LonguserId,LocalDatedate){BitSetbitSetuserSignMap.get(userId);if(bitSetnull){returnfalse;}intoffsetgetOffset(date);synchronized(bitSet){returnbitSet.get(offset);}}/** * 获取用户某个月的签到总天数 * param userId 用户ID * param year 年份 * param month 月份 (1-12) */publicintgetMonthlySignCount(LonguserId,intyear,intmonth){BitSetbitSetuserSignMap.get(userId);if(bitSetnull){return0;}LocalDatefirstDayLocalDate.of(year,month,1);LocalDatelastDayfirstDay.withDayOfMonth(firstDay.lengthOfMonth());intstartOffsetgetOffset(firstDay);intendOffsetgetOffset(lastDay);intcount0;synchronized(bitSet){for(intoffsetstartOffset;offsetendOffset;offset){if(bitSet.get(offset)){count;}}}returncount;}/** * 获取用户截至某一天的连续签到天数包含当天 * 连续定义从当天向前追溯直到第一个未签到的日期为止 * param userId 用户ID * param date 截止日期 */publicintgetContinuousDays(LonguserId,LocalDatedate){BitSetbitSetuserSignMap.get(userId);if(bitSetnull){return0;}intcontinuous0;LocalDatecurdate;while(true){intoffsetgetOffset(cur);synchronized(bitSet){if(!bitSet.get(offset)){break;}}continuous;curcur.minusDays(1);}returncontinuous;}// 计算日期相对于基准日期的偏移量天数privateintgetOffset(LocalDatedate){return(int)ChronoUnit.DAYS.between(BASE_DATE,date);}// ---------- 测试 Demo ----------publicstaticvoidmain(String[]args){SignInServiceservicenewSignInService();LonguserId10086L;// 签到示例LocalDatetodayLocalDate.now();LocalDateyesterdaytoday.minusDays(1);LocalDatetwoDaysAgotoday.minusDays(2);LocalDatethreeDaysAgotoday.minusDays(3);service.signIn(userId,threeDaysAgo);// 3天前签到service.signIn(userId,yesterday);// 昨天签到service.signIn(userId,today);// 今天签到// 查询某天是否签到System.out.println(今天是否签到 service.isSigned(userId,today));System.out.println(两天前是否签到 service.isSigned(userId,twoDaysAgo));// 月签到统计当前月份intmonthCountservice.getMonthlySignCount(userId,today.getYear(),today.getMonthValue());System.out.println(本月累计签到天数 monthCount);// 连续签到天数截至今天intcontinuousservice.getContinuousDays(userId,today);System.out.println(连续签到天数 continuous);// 再签一天明天不能签演示会抛异常// service.signIn(userId, today.plusDays(1)); // 抛出 IllegalArgumentException}}代码说明方法实现要点signIn()计算偏移量对BitSet加锁后设置位返回是否新签到。isSigned()获取BitSet加锁后检查指定位。getMonthlySignCount()通过月份首尾日期计算偏移范围遍历累加。getContinuousDays()从指定日期向前循环检查直到遇到未签到日停止。getOffset()利用ChronoUnit.DAYS.between计算与基准日期的天数差。三、扩展与优化建议1. 替换 BitSet 为 RoaringBitmap应对稀疏或超长周期当用户生命周期长达几十年如 50 年 ≈ 18262 天普通 BitSet 内存约 2.2KB/用户仍可接受。若出现天窗用户极少签到可改用RoaringBitmap压缩存储但对连续天数查询性能略有影响。2. 持久化与生产部署内存版仅适合单机演示或极小型应用。生产环境推荐Redis BitmapSETBIT/GETBIT/BITCOUNT/BITPOS天然支持位操作且可持久化、集群。数据库定期将 Redis 数据备份到 MySQL/HBase用于离线分析。3. 连续天数查询优化目前最坏情况遍历连续天数通常 ≤ 365 天性能无问题。如需极高并发可对每个用户额外维护一个连续签到计数器例如在签到当天更新user:sign:streak:userId做到 O(1) 查询。4. 跨月/跨年连续签到上述getContinuousDays基于日期减法自动处理跨月、跨年无需额外逻辑。5. 日活统计利用BitSet的cardinality()方法可以快速统计某天全局签到人数但需遍历所有用户的BitSet适合定时任务而非实时。四、运行示例输出假设当前日期 2026-05-22今天是否签到 true 两天前是否签到 false 本月累计签到天数 3 连续签到天数 2 // 注意3天前签过但前天未签所以截至今天连续是 昨天今天 2根据实际签到日期输出可能略有不同以上代码完整实现了基于BitSet的用户签到系统清晰展示了位图在海量布尔状态存储中的优势可直接复制运行验证。