HashSet初始化时间复杂度及Leetcode元音反转解法性能差异疑问

我正在解决LeetCode题目「反转字符串中的元音字母」，以下是我的第一种解法：

class Solution {
    public String reverseVowels(String s) {
        String vowels = "aeiouAEIOU";
        char[] arr = s.toCharArray();

        int length = s.length();
        int i = 0;
        int j = length - 1;

        while(i < j && i < length && j > 0) {
            while(i < j && vowels.indexOf(arr[i]) == -1) {
                i ++;
            }
            while(j > i && vowels.indexOf(arr[j]) == -1) {
                j --;
            }
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i ++;
            j --;
        }

        return String.valueOf(arr);
    }
}

由于vowels.indexOf()的时间复杂度为O(n)（n为vowels字符串长度），我决定使用查找更快的数据结构，因此实现了如下HashSet版本：

class Solution {
    public String reverseVowels(String s) {
        Set<Character> set = new HashSet<>(Arrays.asList('A','a','E','e','I','i','O','o','U','u'));
        char[] arr = s.toCharArray();

        int length = s.length();
        int i = 0;
        int j = length - 1;

        while(i < j && i < length && j > 0) {
            while(i < j && !set.contains(arr[i])) {
                i ++;
            }
            while(i < j && !set.contains(arr[j])) {
                j --;
            }
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i ++;
            j --;
        }

        return String.valueOf(arr);
    }
}

我认为用n个字符构造HashSet的时间复杂度为O(n)，且每次查找为O(1)，本以为该版本会更快，但在LeetCode上，第一种解法耗时3ms，第二种耗时5ms。

请问为何第二种解法更慢？用n个元素构造HashSet的时间复杂度是多少，这在此案例中如何影响运行时？

解答 #

1. 为何HashSet版本更慢？

• 极小数据集下线性查找的常数项更低：虽然理论上indexOf是O(k)（k=10，元音数量），但对于只有10个字符的字符串，线性遍历的实际执行速度极快，远低于HashSet查找的开销。HashSet的contains方法需要执行哈希计算、定位桶位置，还要处理潜在的哈希冲突，这些步骤的常数开销远大于遍历10个字符。
• JVM对字符串方法的高度优化：String.indexOf()是JVM内置的高度优化方法，很多实现是native代码或者经过汇编级优化，执行效率比Java层面的HashSet操作高得多。
• HashSet的初始化开销：构造HashSet时，需要将10个字符逐个插入，涉及数组初始化、哈希值计算、自动装箱（char转Character对象）等操作。虽然这部分是O(n)复杂度，但对于n=10的场景，初始化的实际耗时在单次测试中占比不可忽略，而第一种解法的元音字符串是常量，初始化几乎没有额外开销。

2. 构造HashSet的时间复杂度及对运行时的影响

构造包含n个元素的HashSet的时间复杂度是O(n)，因为每个元素的插入操作平均时间复杂度为O(1)。但在这个案例中：

• 虽然n=10，O(n)的理论复杂度看起来很低，但实际初始化过程包含多个额外步骤（比如创建HashSet内部数组、处理自动装箱），这些额外的常数开销在单次运行中被放大，导致整体启动成本更高。
• 加上每次contains调用的常数开销，使得HashSet版本的总耗时超过了直接使用indexOf的版本。

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