为什么haskey的时间复杂度是O(1)。为了找到一个键，它必须迭代列表中的所有元素，所以为什么它是 O(1)
arraylist 的 contains 方法的时间复杂度是多少
最佳答案
哈希表不是列表。它是专门为常见情况下的 O(1) 查找而设计的数据结构(最坏情况查找确实是 O(n))。它通过哈希的概念来实现这一点，哈希是从 key 内容派生的数字，用于直接计算 key 在数组中的索引。
ArrayList 只是下面的一个数组，因此 contains 就是您所期望的线性搜索结构。
关于java - 哈希表和ArrayList的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25827055/