Java中HashSet与TreeSet查询耗时测试的疑问

背景 #

我了解Java中TreeSet的查询时间复杂度为O(logN)，HashSet为O(1)（常数时间）。为验证这一结论，我编写了如下Java测试程序：

import java.util.HashSet;
import java.util.Set;
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);
    }
}

测试结果 #

多次运行程序后得到如下结果：

• Output 1: Time taken by TreeSet MINUS Time Taken by HashSet = 105.6000 nanoseconds
• Output 2: Time taken by TreeSet MINUS Time Taken by HashSet = 99.1000 nanoseconds
• Output 3: Time taken by TreeSet MINUS Time Taken by HashSet = 36.8000 nanoseconds
• Output 4: Time taken by TreeSet MINUS Time Taken by HashSet = 50.6000 nanoseconds
• Output 5: Time taken by TreeSet MINUS Time Taken by HashSet = -30.4000 nanoseconds

疑问 #

我原本预期两者的耗时差值会更大，但实际结果中差值最小仅36纳秒，甚至出现TreeSet耗时更短的负数情况。请问这是正常现象吗？还是我的测试程序存在疏漏？

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