设置大量集合的大小

Question

我有一个用例，我需要为每个集合存储大量具有唯一集合大小的条目。如果我们将其简化为联系人（问题非常严重）。我们必须像一个问题：

由于用户知道他们有多少朋友有：

乔 - 玛丽，约翰，鲍勃，汤姆

玛丽 - 卡罗尔，苏茜，迈克，弗雷德， Robert

因此friends(Joe) = 4 - 唯一支持的操作是addFriend(Joe, Sam)。虽然玛丽可能是乔的朋友，但没有必要存储任何相关信息。

我不想做的是将所有条目存储在每个集合中，但是布隆过滤器并不完全正确。还有其他的选择吗？

更新：挑战是我有20M乔/玛丽/ ...在顶层设置与每组4M半独特的成员。快速代码示例如下（为简单起见，python） - 但是在规模+持久存储中，Universe即将结束。

class World: 
    def __init__(self): 
     self.friends = defaultdict(set) 

    def addFriend(self, id, member): 
     self.friends[id].add(member) 

    def friends(self, id): 
     return len(friends[id]) 

Answer 1

由于您正在考虑使用Bloom过滤器，因此听起来好像近似的答案是可以的。使用像HyperLogLog这样的小空间基数估计器代替self.friends。