Java 中 HashSet 搜索时间与 TreeSet 搜索时间

Question

我读到，TreeSet 中的搜索时间是 log(N) 的量级，而 HashSet 中的搜索时间是 1（常数）的量级。现在，为了在程序中测试这一点，我编写了一个 Java 程序。

import java.util.TreeSet;
import java.util.Random;

public class SearchSpeed {
    int totalElements, target;
    Set<Integer> hashSet, treeSet;
    Random r;

    // parameterized constructor
    SearchSpeed(int totalElements){
        this.totalElements = totalElements;
        r = new Random();
        hashSet = new HashSet<>();
        treeSet = new TreeSet<>();
    }

    // populating the sets and selecting the target element
    void populateSets(){
        hashSet.clear();
        treeSet.clear();
        int num, count = 0;
        while(hashSet.size() != totalElements){
            num = r.nextInt();
            hashSet.add(num);
            treeSet.add(num);
            count++;
            if(count == 5000){    // picking the 5000th element as the target element
                target = num;
            }
        }
    }

    // searching the target element in HashSet
    long searchHash(){
        long initialTime = System.nanoTime();
        hashSet.contains(target);
        long finalTime = System.nanoTime();
        return finalTime - initialTime;
    }

    // searching the target element in TreeSet
    long searchTree(){
        long initialTime = System.nanoTime();
        treeSet.contains(target);
        long finalTime = System.nanoTime();
        return finalTime - initialTime;
    }


    public static void main(String[] args) {

        SearchSpeed ss = new SearchSpeed(10000);

        long hashTime = 0, treeTime = 0;
        for(int i = 0; i < 1000; i++){
            ss.populateSets();
            hashTime += ss.searchHash();
            treeTime += ss.searchTree();
        }
        double avgTreeTime = treeTime/1000.0;
        double avgHashTime = hashTime/1000.0;

        System.out.printf("Time taken by TreeSet MINUS Time Taken by HashSet = %.4f nanoseconds\n",avgTreeTime - avgHashTime);
    }
}

运行这个程序几次后，这些是我得到的结果：

输出 1：TreeSet 花费的时间减去 HashSet 花费的时间 = 105.6000 纳秒
输出 2：TreeSet 花费的时间减去 HashSet 花费的时间 = 99.1000 纳秒
输出 3：TreeSet 花费的时间减去 HashSet 花费的时间 = 36.8000 纳秒
输出 4：TreeSet 花费的时间减去 HashSet 花费的时间 = 50.6000 纳秒
输出 5：TreeSet 花费的时间减去 HashSet 花费的时间 = -30.4000 纳秒

我预计时间差会更大一些，但在某些情况下，时间差低至 36 纳秒，甚至在某些情况下为负值。
这是我应该期待的吗？或者我在编写程序时错过了什么？

Answer 1

是的。你错过了很多。事实上，你几乎不可能做到这一点。不过好消息是，有一个库可以实现这一点。具体来说，JMH。

JVM 并不是一个简单的东西。它运行代码的速度很慢，并执行各种看似毫无意义的记录，以便它知道哪 0.1% 的代码消耗了 95% 的 CPU 资源（这些数字并不夸张；这就是大多数应用程序最终所做的事情。一个学术案例 只是测试某些算法的速度显然不是这样的，但是 JVM 针对现实生活中的应用程序进行了优化，而不是测试用例）。一旦它弄清楚那是什么，它就会使用所有看似毫无意义的簿记来制作高度优化的机器代码，例如被编写来优化分支（CPU 在“不跳转”时往往比“执行跳转”更快，这是任何循环结构都会被转换成的。JVM 知道到目前为止，更频繁地采用哪个“路径”并进行优化因此，如果没有提示，仅编译时优化器就无法做到这一点）。

这是您不能仅依靠计算 2 个 nanoTime() 调用之间的增量并提取有关计时的有意义的结论的大约 900 个原因之一。

JMH 修复了其中的一些问题。不是全部，而是大多数。按照上面链接的教程进行操作，将您的基准测试挂在 JMH 安全带中，然后然后检查您的结果。