java - 包含依赖于 HashMap 大小的 HashMap 操作吗？

Question

根据我对 hashmap 的理解

问题 1:- 对于 Hashmap，返回每个键的唯一哈希码

time to determine whether a object is contained in hashmap is constant and does not depend on size of hashmap

问题 2:- 对于 Hashmap，为每个键返回相同的哈希码，但为 equals 方法返回 false

time to determine whether a object is contained in hashmap is dependant on size of hashmap

这是真的吗？

Answer 1

通常认为 hashmap 查找只需要 O(1) 时间。这是查找的平均时间。但在最坏的情况下，它也可能是 O(n)。例如，如果在 HashMap 的实现中使用链表，则可能会发生这种情况。但如果使用自平衡树，可以避免这种情况，从而将最坏情况的时间减少到 O(log n) 时间。