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

Question

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

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

我想知道对于添加的 N 个成员，这个操作复杂度如何成为 O(N)？如何执行唯一性检查？redis 是否存储了所有 SET 的所有成员的哈希表？

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

Answer 1

对于添加的 N 个成员，复杂性不是 O(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)。