Redis HGETALL时间复杂度的解释是什么

Question

HGETALL该命令的时间复杂度根据文档O(N) 计算，其中 N 是哈希值的大小。在许多提到的情况下HGETALL，用户经常会被警告其时间复杂度，例如在这个答案中，但没有深入了解HGETALL幕后的功能以及为什么时间复杂度是这样的。那么为什么是 O(N) 呢？这与 Redis 存储哈希值的方式有关吗？是网络原因，还是只是受 CPU 限制？HGET时间复杂度为 O(1)并且不以任何方式依赖于大小，因此我可以将哈希集存储为与某些分隔符连接的一个值以提高性能吗？

Answer 1

Redis 将 Hash 作为哈希表存储在内存中。从本质上讲，从任何哈希表中获取单个条目都是 O(1) 操作。HGETALL 必须一一获取哈希表中的所有条目。所以，它是 O(N)。如果您编写了自己的哈希表并且没有使用 Redis，它也会以这种方式工作。这就是哈希表的工作原理。

\n

将哈希表序列化为单个字符串然后保存该字符串不会为您节省任何内容。您要将后端的 O(N) 操作替换为代码中的操作。

\n

我总是发现在时间复杂性的讨论中缺少的一点是，它是关于扩展，而不是时间。人们谈论事物“更慢”和“更快”。但这与毫秒无关。O(1) 操作是“恒定时间”而不是更慢。这仅仅意味着每次总是花费相同的时间\xe2\x80\x94。一个函数的复杂度可能是 O(1)，但仍然比其他具有 10 亿个条目的 O(N) 函数慢。

\n

就 Redis 而言，HGETALL 非常快且O(N)。除非您的哈希中有数千个字段，否则您可能不需要担心它。

\n