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

下面提供一个基于Java BitSet的完整用户签到系统设计方案，涵盖需求分析、核心思路、关键代码与测试示例。

一、设计思路

1. 需求定义

• 用户每天可以签到一次，重复签到不会覆盖或重复计数。
• 支持查询任意用户在某一天是否已签到。
• 统计某个月份的签到总天数。
• 查询截至某一天的连续签到天数（按自然日连续，中间不能断开）。

2. 存储模型

使用Map<Long, BitSet>存储每个用户的签到记录：

• Key：用户ID（Long）
• Value：BitSet，其中每个 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_DATE=LocalDate.of(2020,1,1);// 存储每个用户的签到位图privatefinalMap<Long,BitSet>userSignMap=newConcurrentHashMap<>();/** * 用户签到 * @param userId 用户ID * @param date 签到日期 * @return 是否签到成功（若当天已签到返回false） */publicbooleansignIn(LonguserId,LocalDatedate){// 不能签未来的到if(date.isAfter(LocalDate.now())){thrownewIllegalArgumentException("不能签未来的日期");}intoffset=getOffset(date);BitSetbitSet=userSignMap.computeIfAbsent(userId,k->newBitSet());synchronized(bitSet){if(bitSet.get(offset)){returnfalse;// 已签到}bitSet.set(offset);returntrue;}}/** * 检查用户在某天是否已签到 */publicbooleanisSigned(LonguserId,LocalDatedate){BitSetbitSet=userSignMap.get(userId);if(bitSet==null){returnfalse;}intoffset=getOffset(date);synchronized(bitSet){returnbitSet.get(offset);}}/** * 获取用户某个月的签到总天数 * @param userId 用户ID * @param year 年份 * @param month 月份 (1-12) */publicintgetMonthlySignCount(LonguserId,intyear,intmonth){BitSetbitSet=userSignMap.get(userId);if(bitSet==null){return0;}LocalDatefirstDay=LocalDate.of(year,month,1);LocalDatelastDay=firstDay.withDayOfMonth(firstDay.lengthOfMonth());intstartOffset=getOffset(firstDay);intendOffset=getOffset(lastDay);intcount=0;synchronized(bitSet){for(intoffset=startOffset;offset<=endOffset;offset++){if(bitSet.get(offset)){count++;}}}returncount;}/** * 获取用户截至某一天的连续签到天数（包含当天） * 连续定义：从当天向前追溯，直到第一个未签到的日期为止 * @param userId 用户ID * @param date 截止日期 */publicintgetContinuousDays(LonguserId,LocalDatedate){BitSetbitSet=userSignMap.get(userId);if(bitSet==null){return0;}intcontinuous=0;LocalDatecur=date;while(true){intoffset=getOffset(cur);synchronized(bitSet){if(!bitSet.get(offset)){break;}}continuous++;cur=cur.minusDays(1);}returncontinuous;}// 计算日期相对于基准日期的偏移量（天数）privateintgetOffset(LocalDatedate){return(int)ChronoUnit.DAYS.between(BASE_DATE,date);}// ---------- 测试 Demo ----------publicstaticvoidmain(String[]args){SignInServiceservice=newSignInService();LonguserId=10086L;// 签到示例LocalDatetoday=LocalDate.now();LocalDateyesterday=today.minusDays(1);LocalDatetwoDaysAgo=today.minusDays(2);LocalDatethreeDaysAgo=today.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));// 月签到统计（当前月份）intmonthCount=service.getMonthlySignCount(userId,today.getYear(),today.getMonthValue());System.out.println("本月累计签到天数： "+monthCount);// 连续签到天数（截至今天）intcontinuous=service.getContinuousDays(userId,today);System.out.println("连续签到天数： "+continuous);// 再签一天（明天不能签，演示会抛异常）// service.signIn(userId, today.plusDays(1)); // 抛出 IllegalArgumentException}}

代码说明

三、扩展与优化建议

1. 替换 BitSet 为 RoaringBitmap（应对稀疏或超长周期）

• 当用户生命周期长达几十年（如 50 年 ≈ 18262 天），普通 BitSet 内存约 2.2KB/用户，仍可接受。
• 若出现天窗（用户极少签到），可改用RoaringBitmap压缩存储，但对连续天数查询性能略有影响。

2. 持久化与生产部署

• 内存版仅适合单机演示或极小型应用。生产环境推荐：
  • Redis Bitmap（SETBIT/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的用户签到系统，清晰展示了位图在海量布尔状态存储中的优势，可直接复制运行验证。