data-structures - 为什么在redis SET中插入的时间复杂度是O(n)？

Question

我正在阅读 redis 的 SADD 命令帮助页面。 http://redis.io/commands/sadd

然后我发现有人在问下面的评论

I am wondering how this operation complexity can be O(N) for N members added ? How is performed the unicity check ? Does redis store a hash table with all members of all SETs ?

事实证明这是一个很好的问题，我很好奇为什么 SET 的插入是 O(n)？

Answer 1

复杂度不是 O(n)，而是添加 N 个成员的 O(N)。具体来说，这意味着您可以认为每个插入操作都是在常数时间内完成的 - O(1) - 这只是渐近正确的。

在下文中，我们假设 n 是集合中的项目数。

要执行 SADD 操作，Redis 必须首先查找表示集合的对象(哈希查找 - 复杂度 O(1))，然后尝试在对象本身中添加项目。

集合可以在内存中表示为一个整数集或一个哈希表。

如果对象是一个整数集(即整数的排序向量)，它将执行二进制搜索以搜索项目的位置 - O(log n) 然后最终插入项目 - O(n) - 然而，这仅适用于较小的 n 值。必须选择 set-max-intset-entries，以便整个对象适合 CPU 缓存以获得最佳性能。

如果对象是哈希表，则 Redis 将必须执行查找并在需要时添加项目 - 复杂度为 O(1)。

因为 SADD 命令可以添加 N 项，所以最终的渐近复杂度是 O(N)。