qinghuan
← 黑马点评 / 全部笔记

单元 82 / 黑马点评

P1 · 重点提升L2 · 进阶

黑马点评:附近商户、签到、UV 与复盘

按业务分别使用 GEO、Bitmap 和 HyperLogLog,检查距离、连续天数与近似访客统计各自的限制。

本篇目录 · 按需要跳转

读完这篇,你能做什么

能用少量可手算数据验证附近结果和签到,并解释 UV 估算不能证明精确用户集合。

学习理由、准备要求与知识点

为什么学它

附近查询、位图和近似计数是 Redis 专用结构的代表,应按查询能力和精度要求选型。

先读这些内容

知识点清单

  • 经度与纬度
  • GEOSEARCH
  • 数据库详情回查
  • 距离顺序恢复
  • Bitmap 位偏移
  • 连续签到
  • 跨月边界
  • HyperLogLog 误差

运行前先确认完整算法使用 Java 17 标准库;JDK 源码基线为 OpenJDK 17 GA。示例是内存中的机制模型,外部服务接入需要另外配置和验证。

01先弄懂它是什么

附近商户、每天签到和访客数,解决的是三类不同问题。GEO 用来按地理位置找候选商户;签到适合按天记录是或否;UV 则是估算不同访客数量。GEOADD 的参数先经度、后纬度,GEOSEARCH 找到候选后,还要补上数据库详情并恢复距离顺序。这里的近似直线距离不是道路导航距离。

签到可按用户和月份存成位图,第 d 天使用下标 d-1。把同一天重复设为 1 不会多算一次;统计 1 的个数能得到本月签到天数,但连续签到必须从目标日期向前逐天检查,不能直接用 BITCOUNT。跨月、闰年和业务日期还要使用日历规则,并明确采用哪个时区。

HyperLogLog 适合估算“有多少个不同访客”,这个不同值的数量叫基数。它不保存完整名单,因此不能拿它查询某个用户来没来过。统计 UV 前,要先规定怎样识别同一访客、哪段时间算一天、哪些访问放在一起去重。约百分之零点八一的标准误差描述估算的统计表现,不是承诺每次结果都只差这么多,也不是给单次结果划定一个绝不会超出的误差范围。

文中这几个词,先认一认

位偏移
位图中从 0 开始编号的位置,例如每月第 1 天放在偏移 0。
基数估计
不保留全部成员名单,用较小空间估算不同成员有多少,允许一定统计误差。
未知月份
某个月的历史签到数据还没加载,不能直接把“还不知道”当成“没有签到”。

还有陌生词?到术语小抄里看一个具体例子 ↗

02看看它怎么工作

本题计算截至指定日期的跨月连续签到,输入为年月到BitSet的映射。日历向前一天,查对应月份与日期位;遇到零则连续段结束,遇到未加载月份返回已确认天数与UNKNOWN,达到查询上限返回LIMIT,避免把缺资料误判成断签。

例如二零二四年三月一日已签到,二月二十九和二十八也签到,二月二十七为零,结果三天且STOPPED。若二月数据没有加载,只能确认三月一日一天并返回UNKNOWN,不能声称连续签到恰好一天。

Redis位图偏移从字节高位开始,BITFIELD读取从偏移零开始的无符号字段时,最后读取日位可落在数值低位;Java BitSet按索引取布尔值,不直接解释同一字节顺序。跨语言转换需显式映射,不能把Redis原字节直接交给BitSet.valueOf后假定日期相同。

正在加载流程图…

图中状态只描述本篇可执行机制;业务调用仍需由外层应用负责。
查看流程图源码(Mermaid)
flowchart TD
  G["位置输入"] --> GEO["GEO候选与距离顺序"]
  S["业务时区日期"] --> B["月位图与跨月连续检查"]
  U["稳定访客标识"] --> H["HLL去重估算"]
  GEO --> V["预期与实际证据核对"]
  B --> V
  H --> V

按顺序看,每一步做了什么

  1. 为GEO、签到、UV分别定义输入和可接受误差。
  2. 核对经纬度顺序、日期时区和访客标识。
  3. 签到按日历逐日跨月读取,区分零与未知。
  4. 用确定小样本核对空间顺序、位顺序和去重结果。
  5. 复盘记录实际版本、样本和证据范围。

03对照实现代码

OpenJDK 17 LocalDate 源码 (新标签页)↗

OpenJDK 17 GA,jdk-17+35 · LocalDate.minusDays / getDayOfMonth

下方为原创 Java 教学片段,调用已核验的 JDK API 说明局部机制;不是该类原样源码,不代表Redis或数据库内核实现。完整程序见算法模块。

核心机制代码 · java
LocalDate day = instant.atZone(businessZone).toLocalDate(); // 先按业务时区定义今天。
int bitIndex = day.getDayOfMonth() - 1; // 日期从一开始,位偏移从零开始。
boolean signed = monthBits.get(bitIndex); // 已加载月份中的显式布尔状态。
LocalDate previous = day.minusDays(1); // 日历负责跨月、跨年和闰日,不手写天数减法。

LocalDate表示不含时间与时区的日期,minusDays按日历规则移动。将Instant转换为日期时需要外部明确ZoneId,不能把服务器默认时区当作产品约定。

getDayOfMonth返回从一开始的日期,因此映射到签到位时减一。月底长度随月份和闰年变化,不能固定每月三十一天来构建合法性检查。

日期对象不可变,minusDays返回新值,循环必须接收结果。到达支持的最小日期时继续减会失败,本题在边界返回LIMIT并保留明确范围。

Java日期与BitSet只是签到计算桥梁,不实现Redis GEO索引或HyperLogLog。后两种结构的误差和返回顺序需要按官方定义另行验证。

代码先调用谁,再调用谁

  1. Instant按业务时区确定日期
  2. 日期减一映射位偏移
  3. 读取已加载月份
  4. LocalDate.minusDays跨日推进
  5. 返回连续数与终止原因

04动手写一个例子

带未知状态的跨月连续签到

输入年月位图、目标日期和1到100000的最大检查天数,输出确认连续天数与STOPPED、UNKNOWN或LIMIT。缺失月份表示未加载,存在空位图表示明确未签到。Java17自测。

输入 1
2024-03-01和02-29、02-28签到,02-27未签到
输出 1
3,STOPPED
输入 2
仅加载03-01签到
输出 2
1,UNKNOWN

先检查所有位图没有超出真实月份天数的置位。一个月最多三十一位,校验成本按月份数量计算,不需要扫描所有历史日期。

从目标日期开始,先检查数据是否存在,再检查日期位。零立即终止;一则累计并向前推进,达到上限不继续请求更早月份。

返回终止原因以区分精确连续值、已确认下界和人为检查上限。这样UI不会把历史读取失败伪装成用户未签到,也能安排补取资料。

为什么这样写是对的count天均有明确置位证据且日期连续;UNKNOWN不推断缺失月份内容,STOPPED一定由已加载位图中的零终止。

时间 O(M+d)预期时间额外空间 O(1)辅助空间

M为已加载月份数,d为实际检查天数且不超过limit;每月合法性检查和每日日历、哈希查找有固定宽度,输入位图不复制。

保存为 Main.java,运行 javac --release 17 -encoding UTF-8 Main.java,再运行 java Main。程序包含固定输入自测,断言失败时会抛出错误。

Main.java · 完整可运行程序 · Java
import java.time.*;
import java.util.*;
public class Main {
    record Streak(int days,String reason){}
    static BitSet bits(int... days){BitSet b=new BitSet();for(int d:days)b.set(d-1);return b;}
    static Streak streak(Map<YearMonth,BitSet> months,LocalDate today,int limit){
        if(limit<1||limit>100000)throw new IllegalArgumentException("limit");
        for(var e:months.entrySet())if(e.getKey()==null||e.getValue()==null||e.getValue().length()>e.getKey().lengthOfMonth())throw new IllegalArgumentException("month bits"); // 闰年和月份长度由日历决定。
        LocalDate day=today;int count=0;
        while(count<limit){
            BitSet b=months.get(YearMonth.from(day));if(b==null)return new Streak(count,"UNKNOWN"); // 未加载不等于没有签到。
            if(!b.get(day.getDayOfMonth()-1))return new Streak(count,"STOPPED");
            count++;if(count==limit||day.equals(LocalDate.MIN))return new Streak(count,"LIMIT");
            day=day.minusDays(1); // 自动跨越月底与闰日。
        }throw new AssertionError();
    }
    static void eq(Streak e,Streak a){if(!e.equals(a))throw new AssertionError(a);}
    public static void main(String[] args){
        LocalDate date=LocalDate.of(2024,3,1);YearMonth march=YearMonth.of(2024,3),feb=YearMonth.of(2024,2);
        eq(new Streak(3,"STOPPED"),streak(Map.of(march,bits(1),feb,bits(28,29)),date,10));
        eq(new Streak(1,"UNKNOWN"),streak(Map.of(march,bits(1)),date,10));
        eq(new Streak(0,"STOPPED"),streak(Map.of(march,bits()),date,10));
        eq(new Streak(0,"UNKNOWN"),streak(Map.of(),date,10));
        eq(new Streak(1,"LIMIT"),streak(Map.of(march,bits(1)),date,1));
        eq(new Streak(2,"STOPPED"),streak(Map.of(YearMonth.of(2025,1),bits(1),YearMonth.of(2024,12),bits(31)),LocalDate.of(2025,1,1),10));
        try{streak(Map.of(YearMonth.of(2023,2),bits(29)),LocalDate.of(2023,2,28),10);throw new AssertionError();}catch(IllegalArgumentException expected){}
        System.out.println("PASS 7 tests");
    }
}

这些特殊情况也要试一试

  • 缺失月份与明确空月份必须区别。
  • BITCOUNT是总签到数,不是连续段。
  • Redis字节位序与JavaBitSet转换不能想当然。
进阶选读 · 后续再读:海量签到与近似UV聚合

场景大量用户跨月统计,多个分区需要合并UV。

做法签到可缓存连续段摘要并以补签版本失效,UV合并使用支持的HyperLogLog并集而非把每日估值直接相加;精确需求改用成员集合或明细。

复杂度签到摘要查询可缩短逐日扫描,但补签和更正需要维护;HLL状态规模较固定,代价是估算误差和无法枚举成员。

好处与代价精确成员记录更灵活却占用更多存储,近似统计适合趋势,不适合按人审计或精确结算。

05项目里怎么用

GEO 键可按商户类型或业务划分,写入前核对经纬度顺序和允许范围。按距离找出候选后,读取数据库详情并恢复原排序。这里的距离不是道路导航距离;COUNT、ANY 等选项会影响结果选择,应按实际版本阅读规则,并用范围边缘的位置检查。

签到接口从可信身份确定用户,日期按业务时区计算;补签、撤销和重复提交有独立规则。月位图缺失可能是没有记录、过期、淘汰或读取失败,适配层应先分类,再把明确状态传给算法,不要把所有空返回统一当未签到。

UV需要稳定且合规的访客标识,跨日统计必须通过结构合并处理重复访客,不能简单累加每日PFCOUNT。复盘记录输入、预期、实际结果和误差范围,区分命令示例、纯Java模型和真实服务测量,避免虚构项目完成状态。

容易踩的坑

  • GEO经纬度颠倒或误当导航距离。
  • BITCOUNT被用来计算连续签到。
  • 缺失历史位图直接当断签。
  • HLL标准误差被说成每次固定误差上限。

几种做法,怎么选

表格有四列,窄屏可左右滑动查看代价和适用条件。

方案优势代价与限制适用条件
GEO候选检索邻近筛选高效需要补详情与明确距离含义附近商户
月位图签到紧凑且重复置位幂等跨月补签与位序需处理按日布尔记录
HyperLogLogUV存储较小且可合并近似且不可枚举成员大规模访问趋势

06检验是否读懂了

先自己想、自己写,再展开答案核对。场景题是假设的练习情境;遇到还没学过的内容,可以做完基础后再回来。

先用自己的话解释

01今天未签到时连续数是多少?

展开参考答案与推导

本题截至今天的连续数为零,若产品统计截至昨天需显式改起点,不能混用。

02HLL能判断某人来过吗?

展开参考答案与推导

不能,它保存估算基数所需状态,不保留完整成员身份。

03LocalDate为什么还需要时区?

展开参考答案与推导

日期本身无时区,从真实时刻确定今天时需要先指定业务ZoneId。

换个情况,还会处理吗

01月初连续数突然变一,先查什么?

展开参考答案与推导

检查上月位图是否加载、键是否过期及跨月日期处理,不能直接认定用户断签。

02附近结果补详情后距离顺序乱了,怎么修?

展开参考答案与推导

保存GEO候选的ID顺序或距离映射,数据库查询后按原序重排并处理缺失项。

03每日UV相加高于月UV,正常吗?

展开参考答案与推导

正常,同一访客可能跨日重复;月UV应合并去重状态或明细后计算。

写代码试一试

01闰日跨月如何计算?

输入 / 条件
03-01、02-29、02-28为一
输出 / 预期
3

提示 使用minusDays。

展开参考答案与推导

日历自动从三月一日到闰年二月二十九日,遇二十七日零终止。

02缺上月数据返回什么?

输入 / 条件
仅03-01明确为一
输出 / 预期
1,UNKNOWN

提示 不要推断零。

展开参考答案与推导

只确认一天且历史未齐,调用方可以补取月份后重新计算。

03查询上限是一怎样返回?

输入 / 条件
今天为一,limit1
输出 / 预期
1,LIMIT

提示 这只是下界。

展开参考答案与推导

达到上限后停止,不宣称真实连续数恰好一天,reason保留范围语义。

读完之后,独立完成

课后作业:自己做一遍

本篇共 10 道作业,先完成 8 道基础与综合任务,再按前置知识挑战进阶题。其中包含 1 道思维拓展,试着换个条件,看看原来的办法是否还管用。不附参考答案。

这次练什么

能用少量可手算数据验证附近结果和签到,并解释 UV 估算不能证明精确用户集合。

本篇重点加练

连续签到要求精确日期语义,而 UV 允许估算,两种指标不能使用同一验收标准。

  • 连续签到
  • HyperLogLog 误差

重点内容会多练几次。先说清楚怎么做,再试试空数据、出错或条件改变时会发生什么。

先自己做,卡住时记下问题,再回来查。问答题写清“为什么、什么时候适用”;动手题留下输入、输出和运行步骤,方便下次重做。

基础必做

  1. 作业 01排错实验

    在本地 Redis 建立 6 个商户坐标,包含接近经度边界和两个重合坐标;改变搜索半径与结果数量,记录输入单位和排序选项。

    提交内容
    初始化命令与观测表
    怎样算完成
    • 验证经纬度顺序和合法范围
    • 记录 Redis 版本及搜索参数

    练到的知识点经度与纬度 · GEOSEARCH

  2. 作业 02代码推演

    附近商户索引返回 5 个 ID,数据库中一条已下架、一条不存在,查询结果又无序。为页面“最多显示 4 家”制定返回规则并手工推演。

    提交内容
    回查数据及结果契约
    怎样算完成
    • 区分过滤与补足策略
    • 保留可审计的距离关联

    练到的知识点数据库详情回查 · 距离顺序恢复

  3. 作业 03原理问答

    签到数据按当地自然日记录。自行构造补签、重复签到与未来日期请求,定义它们的位偏移及连续签到统计口径。

    提交内容
    日期样本与位图示意
    怎样算完成
    • 明确日期到位的映射
    • 区分真实签到与补签规则

    练到的知识点Bitmap 位偏移 · 连续签到

  4. 作业 04原理问答

    账号可更改个人时区,产品把签到日定义为账号当前时区的自然日。构造一次跨时区修改,评审历史连续天数是否应随之变化。

    提交内容
    日期事实与展示契约
    怎样算完成
    • 区分事件时间和统计日期
    • 列出需要产品决定的规则

    练到的知识点连续签到

综合应用

  1. 作业 05面试场景

    活动从月末跨到次月,产品同时展示连续签到人数和月度 UV。说明两项指标需要的输入、误差要求和不可互换的数据结构能力。

    提交内容
    指标定义与数据依赖表
    怎样算完成
    • 覆盖闰年与时区
    • 量化可接受误差并注明估算口径

    练到的知识点跨月边界 · HyperLogLog 误差

  2. 作业 06编程实践

    实现本地签到统计器并准备跨年、闰月边界及缺月数据;另用固定种子的访问 ID 样本比较精确去重与本地 HyperLogLog 估算。

    提交内容
    源码、样本和实验报告
    怎样算完成
    • 区分精确计算与估算误差
    • 不得把一次误差样本写成保证

    练到的知识点Bitmap 位偏移 · 连续签到 · 跨月边界 · HyperLogLog 误差

  3. 作业 07设计评审

    月度 UV 接近发奖阈值,产品要求低于阈值绝不发奖。评审以 HyperLogLog 估算直接作资格判定的证据需求。

    提交内容
    误差与业务决策表
    怎样算完成
    • 区分估算值和确定事实
    • 量化误判代价

    练到的知识点HyperLogLog 误差

  4. 作业 08编程实践

    写本地指标验收器:精确签到按声明的日历规则核对,UV 估算按给定误差口径汇报;输入包括小样本、空数据和跨时区记录。

    提交内容
    源码与两类验收报告
    怎样算完成
    • 两指标采用不同判据
    • 不从一次误差观测推导普遍上界

    练到的知识点连续签到 · HyperLogLog 误差

进阶挑战 · 掌握前置后选做

  1. 作业 09设计评审

    商户搬迁后地理索引更新失败,同时月报需要重算。设计两类数据的校验任务,确定各自事实来源、修复代价及不能恢复的信息。

    提交内容
    两份恢复方案
    怎样算完成
    • 覆盖索引陈旧和原始数据缺失
    • 明确线上展示与统计报表的验收差异

    练到的知识点经度与纬度 · GEOSEARCH · 数据库详情回查 · 距离顺序恢复 · 跨月边界 · HyperLogLog 误差

思维拓展

先写出你的猜想,再用例子或实验验证。答案可以不同,但要说清依据、适用情况,以及还有什么没弄懂。

  1. 作业 10思维拓展 · 开放探究

    把签到和 UV 思想迁移到设备在线监测:设备时钟会漂移,同一设备会换标识。探究“连续在线”和“独立设备数”各需怎样重新定义。

    提交内容
    定义草案与实验假设
    怎样算完成
    • 包含身份变化与缺失上报
    • 明确无法由现有数据判定的事实

    练到的知识点连续签到 · HyperLogLog 误差

完成后,再检验一次

给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题,记下卡在哪里。隔一天换一组输入再试,能解释结果和出错原因,再把这个知识点标为掌握。

继续阅读

先看能帮你完成当前练习的部分。例子跑通后,再读更深入的解释。

打开资料库,找下一份学习材料 ↗