是否有一种针对唯一键数组的压缩算法，可以让我快速添加键、删除键或检查键是否存在？

Question

我正在考虑开发一个高效存储的投票系统。我的应用程序的用户应该能够对某个帖子投赞成票或反对票、撤消投票、再次投票等，但可能永远不会为单个帖子注册多个投票（就像 StackOverflow 一样）。

对我来说存储这些数据的明显方法是这样的..（我使用下面的名称，但假设这些是唯一的 ID）

{
  postId: 123,
  upvotedBy: ["bob", "sally", "mark"],
  downvotedBy: ["susan", "ryan"],
  score: 1
}

如果帖子疯传，这些数组可能会变得非常大，甚至可能超过单个数据库记录的存储限制。这让我想到，也许有一个数学技巧可以避免存储这些数组。我唯一的要求是

1. 快速查看用户X是否已登记投票
2. 允许用户 X 登记投票（如果他还没有）
3. 允许用户 X 注销其投票（如果已注册）

糟糕的解决方案

假设每个用户的id都是素数。例如

bob: 2
sally: 3
mark: 5
susan: 7
ryan: 11

对于每个帖子，我可以将

upvotedBy

和

downvotedBy

初始化为 1

{
  postId: 123,
  upvotedBy: 1,
  downvotedBy: 1,
  score: 0
}

当用户对帖子投赞成票时，我只需设置

upvotedBy := upvotedBy * userId

（当他对帖子投反对票时也是如此）。现在我可以快速检查用户是否已经为某个帖子投票，并且可以快速注册和取消投票。我上面的例子现在看起来像

{
  postId: 123,
  upvotedBy: 30,
  downvotedBy: 77,
  score: 1
}

当然，一旦我开始将数千个素数相乘，存储效率就会变得非常低。

问题

是否存在实现这些要求的存储和处理高效的压缩算法？

Answer 1

如果你可以检查某个键是否存在，那么你的数据结构就相当于存储了所有键。

执行此操作所需的空间有一个下限，并且有简洁的数据结构在所有情况下都非常接近该下限。但它们非常复杂，并且对于您的用例来说并不实用。

如果您坚持，您可以使用 Roaring Bitmaps 库。

但是为什么你真的想首先压缩这些数据呢？如果是为了减少网络流量或实现高效操作，那么解决方案是仅存储计数（或不存储任何内容，因为标准化），并将投票本身移至单独的表中，正如 @greybeard 在评论中建议的那样。