我们现在有这么个需求,允许运营上传一批用户 ID (可能会有很多个,最大值可以到千万级),然后服务端需要在请求的时候确定这次 id 是否在一批用户 ID 中。其实就是面试很常见的,怎么在一堆值中确定某个值是否存在。
我们这边目前的打算是通过 redis + bloom filter 的形式去判定该 ID 是否命中(跟产品讨论过,允许一定的误差),但是个人感觉这个方案思路有点常规,或者说有点简单。不知道大佬们是否有其他的思路。指教下一些其他的路子~
1
fishCatcher 2021-12-17 00:03:10 +08:00 via iPhone
最大千万级,直接放内存哈希表就行了
|
2
foam 2021-12-17 00:09:34 +08:00
布隆过滤器+1.
蹲一波别的想法 |
3
ximenmenglong 2021-12-17 00:13:52 +08:00
https://nullprogram.com/blog/2014/09/18/
这个实例挺符合你的需求 |
4
raycool 2021-12-17 00:21:18 +08:00
这样应该能满足要求吧。
这个思路很常规吗。 |
5
monkeyWie 2021-12-17 10:04:29 +08:00
id 是整数型的直接用 bitmap 就行吧
|
6
xrzxrzxrz OP @fishCatcher 主要是考虑内存成本问题,因为理论上允许用户上传很多批用户 ID ,这样会用到太多内存
|
8
xrzxrzxrz OP @ximenmenglong 我看看哈
|
9
xrzxrzxrz OP @raycool 应该是能满足的 因为当时看到这个需求的时候,第一时间想到的就是这个方案,所以觉得太常规,想看看有没有其他的思路,可能是我认识不够
|
10
t4we 2021-12-17 10:14:59 +08:00
hyperloglog
|
11
dqzcwxb 2021-12-17 11:05:03 +08:00
试试布谷鸟过滤 Cuckoo Filter
|
12
git00ll 2021-12-17 18:25:12 +08:00
见张表,加个索引。一亿数据都没关系
|
13
Rocketer 2021-12-18 02:20:47 +08:00
现在都是拿空间换时间,这种需求只要不是大到离谱的数据量都可以放内存里用 HashSet 实现。内存才多少钱,O(1)的复杂度不香吗?
|