HashSet 和 TreeSet 性能测试

Question

我读到了 TreeSet 比 HashSet 慢的原因（将元素添加到 TreeSet 中更慢）所以我进行了性能测试，我试图找出将元素添加到 HashSet 然后将它们移动到 TreeSet 或首先把它们放在那里。看起来将元素插入 HashSet 更快，但只有当我插入大量元素时，为什么？我读过，如果我不需要对元素进行排序，请始终使用 HashSet，但显然，有时它会更慢。

当我插入一个具体的值（“1”）而不是随机数时，TreeSet 也更快，因为没有排序，那么我怎么知道什么时候使用 HashSet 或 TreeSet？

我的第二个问题，当我像这样创建 TreeSet 时，为什么我不能访问“NavigableSet”方法？

Set<Integer> treeSet = new TreeSet<Integer>();     //cant type treeSet.lower(e: E)
TreeSet<Integer> treeSet = new TreeSet<Integer>(); //can  type treeSet.lower(e: E)

谢谢你帮我解决这个问题。

结果如下：

5 000 000（随机数）

5 000 000（数字“1”）

500 000（随机数）

50 000（随机数）

这是我的代码：

package performancetest;

import java.text.DecimalFormat;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.TreeSet;

public class HashSet_vs_TreeSet {
private static DecimalFormat df = new DecimalFormat("#.#####");
private static double hashTime, treeTime, hashToTreeTime;
private static int numbers = 0;

public static void main(String[] args){
    start();
    hashSetTest();
    treeSetTest();
    fromHashToTreeSet();
    difference();
}

/**
 * in this method, instead of "System.exit(1)" i try'ed "start()" but when i did lets say three mistakes, after correct input the 
 * methods hashSetTest();treeSetTest();fromHashToTreeSet();difference(); were running 4 times... i made this method exactly for the
 * purpose to repeat itself in case of a input mistake.
 */
public static void start(){
    System.out.print("Enter a number(a advise bigger or equal to 50 000): ");
    Scanner scan = new Scanner(System.in);
    try{
        numbers = scan.nextInt();
    }catch(InputMismatchException e){
        System.out.println("ERROR: You need to enter a number");
        System.exit(1);
    }
    System.out.println(numbers + " numbers in range from 0-99 was randomly generated into " +
            "\n1)HashSet\n2)TreeSet\n3)HashSet and then moved to TreeSet\n");
}

public static void hashSetTest(){
    /**
     * i try'ed HashSet<Integer> hashSet = new HashSet<Integer>();
     * but changing the load factor didn't make any difference, what its good for then ?
     */
    HashSet<Integer> hashSet = new HashSet<Integer>(5000,(float) 0.5);
    double start = System.currentTimeMillis() * 0.001;

    for (int i = 0; i < numbers; i++) {
        hashSet.add((int)(Math.random() * 100));
    }

    hashTime = (System.currentTimeMillis() * 0.001) - start;

    System.out.println("HashSet takes " + df.format(hashTime) + "s");
}

public static void treeSetTest(){
    TreeSet<Integer> treeSet = new TreeSet<Integer>();
    double start = System.currentTimeMillis() * 0.001;

    for (int i = 0; i < numbers; i++) {
        treeSet.add((int)(Math.random() * 100));
    }

    treeTime = (System.currentTimeMillis() * 0.001) - start;

    System.out.println("TreeSet takes " + df.format(treeTime) + "s");
}

public static void fromHashToTreeSet(){
    HashSet<Integer> hashSet = new HashSet<Integer>();
    double start = System.currentTimeMillis() * 0.001;

    for (int i = 0; i < numbers; i++) {
        hashSet.add((int)(Math.random() * 100));
    }

    TreeSet<Integer> treeSet = new TreeSet<Integer>(hashSet);
    hashToTreeTime = (System.currentTimeMillis() * 0.001) - start;

    System.out.println("TreeSet from HashSet takes " + df.format(hashToTreeTime) + "s");
}

public static void difference(){
    double differenceSec = 0;
    double differenceTimes = 0;

    if(hashTime < treeTime){
        differenceSec = (treeTime - hashTime);
        differenceTimes = (treeTime / hashTime);
        System.out.println("\nHashSet takes " + df.format(differenceSec) + "s less then TreeSet, it is " + df.format(differenceTimes) + " times faster");
    }else{
        differenceSec = (hashTime - treeTime);
        differenceTimes = (hashTime / treeTime);
        System.out.println("\nTreeSet takes " + df.format(differenceSec) + "s less then HashSet, it is " + df.format(differenceTimes) + " times faster");
    }
}
}

Answer 1

好吧，当你谈论 TreeSet 和 HashSet 的性能时，你应该清楚地了解这些结构是如何组织的，其组织的后果是什么。

通常，TreeSet 是一种结构，其中所有元素都组织在二叉树中。因此添加成员或访问它是 ~ O(log(N))。

另一方面，HashSet 是类似于数组的结构。不同之处在于，在数组中索引是一个唯一的数字，而在 HashSet 中每个键都需要借助哈希函数转换为索引。哈希函数可能对不同的输入数据产生相同的结果，这种情况称为hash collision。一个好的哈希函数（是的，它们可能是坏的，也可能是好的）在给定的一组输入数据上产生尽可能多的唯一结果。

因此，访问哈希集中的数据需要计算哈希函数（在 Java 中通常是.hashCode()）以及可能的冲突解决。其估计为 O(1)，即操作次数恒定。

您应该明白 O(1) 并不总是小于 O(log(n))，它的渐近性较小且足够大n。哈希函数的正确选择也很重要。