java中HashMap.containsKey()的时间复杂度是多少？

Question

我需要知道：Java 中 HashMap.containsKey() 的时间复杂度是多少？

原文由 Hossein 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

来自 API doc of HashMap ：

此实现为基本操作（get 和 put）提供恒定时间性能，假设散列函数将元素适当地分散在桶中。

因为 containsKey() 只是一个 get() 丢弃了检索到的值，所以它是 O(1)（再次假设哈希函数正常工作）。

原文由 Michael Borgwardt 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

通常是 O(1)，但如果我们使用了一个错误的 hashCode 函数，我们需要将多个元素添加到一个桶中，这样在最坏的情况下它可以是 O(n)。

原文由 mishadoff 发布，翻译遵循 CC BY-SA 3.0 许可协议