面试知识库
高 进阶

扩展数据类型（Bitmap-HLL-GEO）#

一句话答案#

三种基于基本类型扩展的特殊结构：Bitmap（位图，底层是 String/SDS，做签到与活跃统计）、HyperLogLog（基数估算，12KB 算上亿 UV，误差 0.81%）、GEO（地理位置，底层是 ZSet + GeoHash，做”附近的人”）。

核心要点

1. Bitmap（位图）

本质：不是独立类型，底层就是 String（SDS），把每个 bit 当一个布尔位用
极限：单个 key 最大 512MB = 2^32 bit ≈ 42 亿个位
优势：极致省内存，1 亿用户的签到/活跃标记只需 ~12.5MB
plaintext
SETBIT sign:u1001:202606 0 1     # 用户 6 月第 1 天签到（offset=日期-1）
GETBIT sign:u1001:202606 0       # 查第 1 天是否签到
BITCOUNT sign:u1001:202606       # 本月签到总天数
BITPOS  sign:u1001:202606 1      # 本月首次签到是第几天
BITOP AND dest day1 day2         # 两天都活跃的用户（位与）→ 留存统计
bash

典型场景：签到日历、连续签到、日活/月活去重、用户在线状态、布隆过滤器底层。

2. HyperLogLog（基数统计）

作用：估算一个集合的不重复元素个数（基数 cardinality）
原理：基于伯努利试验的概率算法，不存储元素本身，只存桶里的最大前导零
内存：固定 12KB，无论统计多少元素都不变；标准误差 0.81%
代价：只能算"有多少个"，不能判断"某个元素是否存在"，也不能取出元素
plaintext
PFADD   uv:20260601 user1 user2 user3   # 加入访客
PFCOUNT uv:20260601                      # 估算今日 UV
PFMERGE uv:week uv:0601 uv:0602 ...      # 合并多天得周 UV（去重）
bash

对比：精确去重用 Set（1 亿 UV 要几 GB），能容忍 0.81% 误差用 HLL（恒定 12KB）。

HyperLogLog 基数估算原理（深挖推导）

核心直觉：用”最长前导零”反推元素数量。 对每个元素哈希成一串均匀随机的二进制位，统计其最大前导零个数 ρ（从高位起连续 0 的个数）。一个均匀随机值出现「恰好 k 个前导零」的概率是 2^-(k+1)（前 k 位都是 0、第 k+1 位是 1）。反过来想：要观测到「最大前导零 = ρ」，大概需要扔进约 2^ρ 个不同元素才会碰上一次。所以记录见过的 ρ_max，元素数量约 ≈ 2^ρ_max。

直觉类比：抛硬币，连续抛出 N 次正面才停。
  抛了很多组，其中"连续正面最长那组"是 10，
  说明大概玩了 2^10 ≈ 1024 组——前导零就是这个"最长连续正面"。
plaintext

分桶降方差（harmonic mean）。 单看一个 ρ_max 方差极大（运气好一次就连出 20 个零，估计值暴涨）。解决办法：用哈希值的前 14 位把元素分进 m = 2^14 = 16384 个桶，每桶各自只记录落进本桶元素的 ρ_max；最后对 16384 个桶的估值取调和平均（harmonic mean，对异常大的单桶值不敏感，能压制离群桶），再乘偏差修正常数 α，得到全局基数估计。分桶 = 把”一次随机试验”变成”16384 次独立试验取平均”，方差随桶数下降。

误差公式：标准误差 = 1.04 / √m
  m = 16384 → 1.04 / 128 ≈ 0.0081 = 0.81%
  桶越多越准，但内存越大——0.81% 是 Redis 选的平衡点
plaintext

12KB 怎么来的。 每个桶只需存一个小整数 ρ_max。64 位哈希里前导零最多 50 来个，6 bit（可表示 0~63）足够。

内存 = 桶数 × 每桶位数 = 2^14 × 6 bit
     = 16384 × 6 / 8 字节 = 12288 字节 ≈ 12KB（恒定，与元素数无关）
plaintext

串起来记：哈希→数前导零→2^ρ 反推数量→分 16384 桶各记 ρ_max→调和平均降方差→每桶 6bit=12KB→误差 1.04/√16384=0.81%。适用海量基数去重（UV 统计），只能数总数、能 PFMERGE 求并集，但无法求交集、无法判断单个元素是否存在。

3. GEO（地理位置）

本质：底层就是 ZSet，把经纬度通过 GeoHash 编码成一个 52 位整数当 score
能力：存坐标、算两点距离、查某半径内的成员（附近的人/店）
plaintext
GEOADD shops 116.40 39.90 "店A" 116.41 39.91 "店B"   # 经度 纬度 名称
GEODIST shops 店A 店B km                              # 两店距离
GEOSEARCH shops FROMMEMBER 店A BYRADIUS 5 km ASC      # 店A 周边 5km（6.2+）
# 6.2 前用 GEORADIUS / GEORADIUSBYMEMBER
bash

因为底层是 ZSet，可直接用 ZREM 删除成员、ZCARD 统计数量。

面试回答（2分钟版）

除了五种基本类型，Redis 还有三种常考的扩展类型。第一是 Bitmap 位图，它本质不是独立类型，底层就是 String，把每个 bit 当布尔位用，最大 512MB 能存 42 亿个位。最典型的是签到统计，用 SETBIT 以”日期减一”作 offset 记录签到，BITCOUNT 数本月签到天数，再用 BITOP 做位运算算留存，1 亿用户的标记只要十几 MB，非常省内存。第二是 HyperLogLog，用来做基数统计，比如海量 UV 去重，它基于概率算法不存元素本身，无论多少数据都固定占 12KB，标准误差只有 0.81%，代价是只能算总数、不能判断单个元素是否存在；如果业务能容忍千分之几的误差，用它比用 Set 省几个数量级内存。第三是 GEO，做地理位置，底层其实是 ZSet，把经纬度用 GeoHash 编码成整数当 score，所以能算距离、查附近的人，常见于 LBS 的”附近商家”。这三个的共同思路是：在基本类型之上用巧妙编码换取特定场景的极致空间或能力。

追问与易错

追问方向：

  • “Bitmap 存签到为什么省内存？”→ 每个用户每天只占 1 bit，一个 key 存一个用户一个月只要 4 字节，1 亿用户月活标记约 12.5MB；对比用 Set 存 userId 每个至少几十字节，差几百倍
  • “HyperLogLog 的 0.81% 误差能接受吗？”→ UV/PV 这类运营统计本身是趋势性指标，千分之八的误差无影响；但涉及金额、精确去重（如发券防重）绝不能用，要用 Set 或布隆过滤器
  • “HLL 和布隆过滤器区别？”→ HLL 回答”有多少个不重复元素”（基数），布隆回答”某个元素是否存在”（成员判定）；两者都不存原始元素、都有误差、都不可取出元素，但解决的问题不同
  • “GEO 的底层和 GeoHash 是什么？”→ 底层是 ZSet，把二维经纬度通过 GeoHash 算法降维成一维的 52 位整数作为 score，相邻位置编码前缀相同，所以按 score 范围查询就能找到邻近点；查半径时是先按 GeoHash 框选再精算距离过滤
  • “签到统计连续签到天数怎么算？”→ 取出整月的 bit（GETRANGE / BITFIELD 或 BITCOUNT 配合），从今天往前找第一个 0 之前的连续 1 的个数；或用 BITPOS 找最近的未签到位

易错点：

  • ❌ “Bitmap / HLL / GEO 是独立的新数据结构”——它们是基于 String 和 ZSet 的扩展用法，不是新的底层结构
  • ❌ “HyperLogLog 能判断某个用户来过没有”——它只能估算总数，无法做成员判定
  • ❌ Bitmap 的 offset 用很大的值（如直接用 userId 几十亿）会瞬间撑大 key 到几百 MB——offset 要紧凑，按”用户维度一个 key、日期当 offset”组织