Java中使用HashMap的字符映射方法时间复杂度是O(n)还是O(n²)？

这个方法的平均时间复杂度为O(n)，得出O(n²)的判断是因为错误理解了HashMap核心方法的时间复杂度。

核心误区是认为HashMap.containsKey()需要遍历整个Map、耗时O(n)，这个认知混淆了哈希表和数组、线性表的实现逻辑：

• HashMap是基于哈希表实现的键值对结构，containsKey()、put()、get()这类基础操作的平均时间复杂度都是O(1)：调用时会先对key计算哈希值，直接定位到底层数组对应的存储桶位置，不需要遍历全量元素。
• 只有极端故障场景（比如所有key的哈希值完全冲突，全部落入同一个桶形成超长链表/红黑树）下，操作才会退化，但对于Character这类JDK内置的基础类型，其hashCode()实现非常稳定，正常使用中几乎不会触发这种退化。
• 额外补充：Character类型的总取值范围只有65536个不同值，也就是说这个Map的最大容量永远不会超过65536，哪怕真的按最坏的退化场景计算，当输入字符串长度远大于这个阈值时，整体耗时依然和输入长度线性相关。

对给出的代码逐段拆解复杂度：

private static Map<Character, Character> mapCharacters(String message) {
    Map<Character, Character> map = new HashMap<>();
    char idx = 'a';
    // 遍历输入字符串，共n次循环，n为message长度，这部分复杂度O(n)
    for (char ch : message.toCharArray()) {
        // containsKey平均O(1)
        if (!map.containsKey(ch)) {
            // put操作平均O(1)
            map.put(ch, idx);
            ++idx;
        }
    }
    return map;
}

循环内所有操作的平均耗时都是常数级，整体嵌套下来的总平均复杂度就是O(n)，不存在平方级的耗时增长。

注：如果这里把HashMap换成List这类线性存储结构，每次判断元素是否存在都要遍历整个列表，那整体复杂度才会变成O(n²)。

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