为什么 redis 删除单个字符串的 key 时间复杂度是 1？

[woshixiaohao1982]

DEL DEL key [key ...]

删除给定的一个或多个 key。

不存在的 key 会被忽略。

可用版本：

= 1.0.0 时间复杂度： O(N)，N 为被删除的 key 的数量。 删除单个字符串类型的 key，时间复杂度为 O(1)。 删除单个列表、集合、有序集合或哈希表类型的 key，时间复杂度为 O(M)，M 为以上数据结构内的元素数量。

据我所知，二分查找的时间复杂度是 O(lgN) hashmap 是 O(M)取决于头接链表上的元素。

[woshixiaohao1982]

为什么 redis 删除字符串的 key 时间复杂度是 O(1)

[msg7086]

所以如果 Hashtable 空间足够大的话不就是 O(1)了。大 O 是表示数量级的啊，有少量哈希冲突不影响 O(1)数量级。

[woshixiaohao1982]

@msg7086 👌🏻理解了，少量的冲突，就当做是 O(1)的时间复杂度