为什么哈希表删除O(1)？

Why is HashTable Delete O(1)?(为什么哈希表删除O(1)？)

问题描述

我理解为什么HashTable Add是O(1)(但是，如果我错了，请纠正我)：要添加的项总是分配给支持数组中的第一个可用位置。

我理解Lookup为什么是O(N)(同样，如果我错了，请纠正我)：您需要遍历支持数组来查找请求的值/键，并且此操作的运行时间将与集合的大小成正比。

然而，为什么是Deleteconstant?在我看来，添加/查找中涉及的相同原则是必需的。

编辑

MSDN文章指的是找不到请求删除的项目的情况。它提到这是一个O(1)运算。

推荐答案

插入和删除的最坏情况应该是O(n)，请参阅http://en.wikipedia.org/wiki/Hash_table。

当我们插入时，我们必须检查值是否在表中，因此在最坏的情况下O(n)。

想象一下所有哈希值都相同的病理情况。

可能MSDN指的是平均复杂性。

这篇关于为什么哈希表删除O(1)？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！