Java 为什么 HashSet 的 remove() 需要 O(1) 时间，而 ArrayList 的 remove() 需要 O(n) 时间？

Question

我发现Java HashSet 的remove(Object o) 需要O(1) 常数时间，而ArrayList 的remove(Object o) 操作需要O(N)，其中N 是ArrayList 的大小。

谁能详细解释一下，这是为什么？

Answer 1

HashSet'sremove()需要花费O(1)预期的时间来定位要删除的元素 - 这hashCode()会将您带到包含该元素的 bin，并且每个 bin 预计都有少量条目，因此在 bin 中查找元素并将其删除应该是常数时间。

另一方面，在 a 中，ArrayList您必须遍历所有元素，直到找到要删除的元素 - 这需要O(n). 即使在您找到元素之后，移除本身也涉及移动索引高于被移除元素的所有元素 - 这也需要O(n).