java - 从 ArrayList 与哈希表中删除的 Big-O 中存在不一致吗？

Question

我正在看this website列出了各种操作的 Big O 复杂性。对于动态数组，删除复杂度为 O(n)，而对于哈希表，则为 O(1)。

对于像 ArrayList 这样的动态数组，复杂度必须是 O(n)，这必须意味着从中心删除一些值，然后将每个索引移一以保持数据 block 连续的操作。因为如果我们只是删除存储在索引 k 处的值而不进行移位，则时间复杂度为 O(1)。

但是在具有线性探测的哈希表中，删除是相同的事情，您只需通过哈希函数运行您的值，转到保存数据的动态数组，然后删除存储在其中的值。

那么为什么哈希表的时间复杂度为 O(1)，而动态数组的时间复杂度为 O(n)？

Answer 1

这已解释here 。关键是每个动态数组的值数量保持在恒定值以下。

编辑:正如 Dukeling 指出的，我的答案解释了为什么具有单独链接的哈希表具有 O(1) 删除复杂度。我应该补充一点，在您正在查看的网站上，哈希表被认为具有 O(1) 删除复杂性，因为它们通过单独的链接和非线性探测来分析哈希表。