java - 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 是一种结构，其中所有元素都组织在 a binary tree 中.因此添加一个成员或访问它是 ~O(log(N))。

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

因此访问散列集中的数据需要计算散列函数(在 Java 中通常是 .hashCode())和可能的冲突解决。这是它的估计为 O(1)，即恒定数量的操作。

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