投票系统存储优化：求支持增删查的唯一键高效压缩算法

针对你提出的投票系统存储需求，质数相乘的方案会因数值快速膨胀而不可行，以下是几种存储与处理均高效的替代方案，完美匹配你的三个核心需求：

1. 计数布隆过滤器（Counting Bloom Filter） #

核心原理 #

基于布隆过滤器的改进版本，将每个位替换为小计数器（通常4位即可），既保留了布隆过滤器的空间高效性，又支持插入、查询、删除操作。

需求适配： #

• 快速检查用户是否投票：通过3~5个哈希函数计算用户ID对应的计数器位置，若所有对应计数器值大于0，则判定用户已投票（误判率极低，可通过调整哈希函数数量控制）。
• 注册投票：对点赞/点踩对应的过滤器，将用户ID对应所有计数器加1。
• 撤销投票：将用户ID对应所有计数器减1（操作前先查询避免计数器负数）。

优势 #

• 存储空间仅为传统数组的1/10~1/5，百万级用户仅需几MB空间。
• 所有操作时间复杂度为O(k)（k为哈希函数数量），性能极高。

2. 压缩位集（Compressed BitSet） #

核心原理 #

若用户ID为整数类型，可将点赞、点踩的用户集合分别存储为位集：每个用户ID对应位集中的一位，位为1表示已投票。针对稀疏位集（大部分用户未投票），用游程编码或EWAH压缩进一步缩减存储体积。

需求适配： #

• 快速检查用户是否投票：直接定位用户ID对应的位，判断是否为1，时间复杂度O(1)。
• 注册投票：将对应位设为1。
• 撤销投票：将对应位设为0。

优势 #

• 无任何误判，精度100%。
• 存储效率极高：100万用户未压缩仅需约125KB，压缩后体积更小。
• 可快速统计投票数（统计位集中1的数量），实时计算score。

3. 布谷鸟过滤器（Cuckoo Filter） #

核心原理 #

支持删除操作的布隆过滤器替代方案，通过将元素存储在两个候选位置，解决了布隆过滤器无法准确删除的问题，空间效率接近布隆过滤器。

需求适配： #

• 快速检查用户是否投票：查询用户ID是否存在于过滤器中，时间复杂度O(1)。
• 注册投票：将用户ID插入到两个候选位置之一。
• 撤销投票：从过滤器中准确删除用户ID，无残留。

优势 #

• 支持可靠删除，无计数布隆过滤器的计数器溢出风险。
• 空间效率高，误判率可控。

数据库层面的实用方案 #

如果你的系统基于数据库，更推荐使用关联表存储投票记录：

CREATE TABLE post_votes (
    post_id INT NOT NULL,
    user_id INT NOT NULL,
    vote_type TINYINT NOT NULL, -- 1=点赞，-1=点踩，0=已撤销
    PRIMARY KEY (post_id, user_id)
);

这种方案：

• 完全满足三个核心需求，查询、插入、删除均为O(1)（依赖主键索引）。
• 存储量可控：单条记录仅十几字节，百万条记录仅需几十MB。
• 易于扩展，比如支持记录投票时间、重新投票等场景。

内容的提问来源于stack exchange，提问作者Ben