为什么 redis 命令“LLEN”具有常数时间复杂度而不是 O(n)？
Why redis command ‘LLEN’ has constant time complexity instead of O(n)?
我知道redis list 底层是用链表实现的。但是在计算列表长度的时间复杂度时，不应该是O(n)吗？
您可以在 https://github.com/redis/redis/blob/unstable/src/adlist.h 找到列表类型的声明。如果您查看第 50 行周围的部分，您会发现：
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
注意存储列表长度的 unsigned long len。这就是为什么它是 O(1).
我知道redis list 底层是用链表实现的。但是在计算列表长度的时间复杂度时，不应该是O(n)吗？
您可以在 https://github.com/redis/redis/blob/unstable/src/adlist.h 找到列表类型的声明。如果您查看第 50 行周围的部分，您会发现：
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
注意存储列表长度的 unsigned long len。这就是为什么它是 O(1).