为什么 redis 删除单个字符串的 key 时间复杂度是 1？
woshixiaohao1982 · 2017-05-08 22:07:42 +08:00 · 1990 次点击这是一个创建于 2557 天前的主题，其中的信息可能已经有所发展或是发生改变。
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)取决于头接链表上的元素。
 |
1
woshixiaohao1982 OP 为什么 redis 删除字符串的 key 时间复杂度是 O(1)
|
 |
2
msg7086 2017-05-09 01:14:58 +08:00
所以如果 Hashtable 空间足够大的话不就是 O(1)了。大 O 是表示数量级的啊，有少量哈希冲突不影响 O(1)数量级。
|
|
3
woshixiaohao1982 OP @msg7086 👌🏻理解了，少量的冲突，就当做是 O(1)的时间复杂度
|
Select Language