java - 为什么 HashSet 查找唯一字符的解决方案很慢？

Question

我制定了 O(n^2) 和 O(n) 解决方案来查找唯一字符，并且很想真正看到性能差异。我本以为 HashSet 解决方案会将 O(n^2) 解决方案从水中炸出来，但它实际上比仅仅执行嵌套循环要慢。

import java.util.HashSet;

class AllUnique
{
    // O(n^2) solution
    static boolean isUnique(String str)
    {
        int ind = 0;
        boolean unique = true;
        while (ind != str.length())
        {
            int inner_ind = ind + 1;
            while (inner_ind != str.length())
            {
                if (str.charAt(ind) == str.charAt(inner_ind))
                {
                    unique = false;
                }
                inner_ind++;
            }
            ind++;
        }
        return unique;
    }

    // O(n) solution
    static boolean isUnique2(String str)
    {
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < str.length(); i++)
        {
            set.add(str.charAt(i));
        }
        return set.size() == str.length();
    }
}

使用一个非常简单的驱动程序来测试毫秒差异: 公开课计划{

    public static void main(String[] args) {
        String[] stringArr = new String[10000];
        for (int i = 0; i < 10000; i++)
        {
            stringArr[i] = "wefwefwefwefwefalkjegb";
        }
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++)
        {
            AllUnique.isUnique(stringArr[i]);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Total execution time: " + (endTime-startTime) + "ms");

        long startTime2 = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++)
        {
            AllUnique.isUnique2(stringArr[i]);
        }
        long endTime2 = System.currentTimeMillis();
        System.out.println("Total execution time: " + (endTime2-startTime2) + "ms");
    }
}

散列 Character 对象真的需要那么长时间吗？

通常，嵌套循环解决方案比 HashSet 解决方案快约 5-10ms。

Answer 1

在您的基准测试中不公平的一件事是 HashSet 不与您的嵌套循环代码操作相同的实体。 Java autoboxing将原始 char 值包装为 Character 对象。其中一些会产生额外的成本，例如 GC 和在内置缓存中进行查找。

另一个问题是基准测试很难正确进行。很酷的工具之一是 JMH 。它有很多野外例子，例如关于维护者blog .