从ArrayList和Hash表中删除的大O中的不一致？

Question

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

对于像ArrayLists这样的动态数组是O(n)，这意味着必须从中心移除一些值，然后将每个索引移到一个上，以保持数据块的连续性。因为如果我们只是删除存储在索引k处的值而不是移位，那么它就是O(1)。

但是在具有线性探测的哈希表中，删除是一回事，您只需通过Hash函数运行您的值，转到保存数据的Dynamic，并删除存储在其中的值。

那么，为什么哈希表获得O(1)信用，而动态数组获得O(n)？

Answer 1

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

编辑:正如杜克林所指出的，我的回答解释了为什么有单独链接的哈希表具有O(1)删除复杂性。我要补充的是，在您正在查看的网站上，哈希表被认为具有O(1)删除复杂性，因为它们分析具有单独链接而不是线性探测的哈希表。

Answer 2

哈希表的要点是，它们保持接近最佳情况，其中最好的情况意味着每个桶只有一个条目。显然，您可以接受从桶中删除唯一条目需要O(1)时间。

Answer 3

当有许多散列冲突时，您当然需要在使用线性探测时进行大量的移位。

但是哈希表的复杂性是在简单均匀散列假设下进行的，这意味着它假定哈希冲突的数量最少。

当发生这种情况时，我们只需要删除一些值，并移动没有值或少量(本质上是恒定的)值。