为何Java中HashMap.containsKey()为常数时间复杂度而ArrayList.contains()为线性？

1. ArrayList.contains()的线性时间逻辑 #

ArrayList本质是动态数组，元素按插入顺序直接存储在数组中，没有额外的索引结构辅助快速定位。
调用contains(Object o)时，它会从数组第一个元素开始，逐个调用equals()方法与目标值对比：

// ArrayList.contains()核心逻辑简化版
for (int i = 0; i < size; i++) {
    if (o.equals(elementData[i])) {
        return true;
    }
}
return false;

最坏情况下，目标元素在数组末尾或不存在，必须遍历整个数组，因此时间复杂度为O(n)（线性时间）。

2. HashMap.containsKey()的常数时间逻辑 #

HashMap基于哈希表（数组 + 链表/红黑树）实现，核心是通过哈希函数将键（Key）映射为数组索引：

• 存储数据时：调用put(K key, V value)会先计算key的哈希值，通过哈希算法确定其在底层数组的存储位置；若出现哈希冲突，就将键值对挂在对应位置的链表或红黑树上。
• 查询数据时：调用containsKey(Object key)会先计算目标key的哈希值，直接定位到数组对应位置，再在该位置的链表/红黑树中查找匹配的key（无冲突时可直接命中）。

理想状态下（无哈希冲突），仅需一次定位就能找到目标，时间复杂度为O(1)；即使存在冲突，当链表长度超过阈值转为红黑树后，最坏查找复杂度也仅为O(logn)，远优于线性遍历。

一句话总结 #

ArrayList依赖顺序遍历对比查找元素，HashMap依赖哈希值直接定位查找元素，这就是两者时间复杂度差异的根本原因。

内容的提问来源于stack exchange，提问作者Brendan B