HashSet和TreeSet性能测试 [英] HashSet and TreeSet performance test
问题描述
我读到有关TreeSet比HashSet慢的信息(将元素添加到TreeSet的速度较慢)，所以我进行了性能测试，我试图找出将元素添加到HashSet并将其移入其中是否更好TreeSet或将它们放在第一位.看起来将元素插入到HashSet中的速度更快，但是仅当我插入大量元素时，为什么?我读过，如果我不需要对元素进行排序，请始终使用HashSet，但显然，有时它会更慢.
I read about how TreeSet is slower than HashSet, (that adding elements into a TreeSet is slower) so i made a performance test, i'm trying to find out if it's better to add elements to HashSet and then move them into a TreeSet or put them in there in the first place. It looks like that inserting elements into a HashSet is faster but only when i insert a large amount of elements, why? I've read that if i don't need the elements sorted, always use HashSet, but apparently, sometimes it's slower.
当我插入一个具体的值("1")而不是随机数时，TreeSet也会更快，因为没有排序，那么我怎么知道何时使用HashSet或TreeSet?
When I insert a concrete value("1") instead of random numbers, TreeSet is also faster because there is no sorting, so how can i know when to use HashSet or TreeSet?
第二个问题是，当我这样创建TreeSet时，为什么不能访问"NavigableSet"方法?
And my second question, when i create TreeSet like this, why don't i have access to "NavigableSet" methods?
Set<Integer> treeSet = new TreeSet<Integer>(); //cant type treeSet.lower(e: E)
TreeSet<Integer> treeSet = new TreeSet<Integer>(); //can type treeSet.lower(e: E)
感谢您的帮助.
以下是结果:
5000000(随机数)
5 000 000 (random numbers)
5 000 000(数字"1")
5 000 000 (numbers "1")
500 000(随机数)
500 000 (random numbers)
5万个(随机数字)
这是我的代码:
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");
}
}
}
推荐答案
好，当您谈论TreeSet和HashSet的性能时，您应该清楚地了解这些结构是如何组织的，其组织的后果是什么.
Well, when you talk about peformance of TreeSet and HashSet you should clearly understand how these structures are organized what consequences of its organization.
通常，TreeSet是一种结构，其中所有元素都组织在二叉树.因此，添加或访问它的成员是〜O(log(N)).
Typically TreeSet is a structure where all elements are organized in a binary tree. Thus adding a member or accessing it is ~O(log(N)).
另一方面，HashSet是类似于数组的结构.区别在于，数组索引中的索引是唯一数字，而HashSet中的每个键都需要借助哈希函数.对于不同的输入数据，散列函数可能会产生相同的结果，这种情况称为hash collision.一个好的哈希函数(是的，它们可能是坏的，也可能是好的)可以在给定的一组输入数据上产生尽可能多的唯一结果.
In other hand HashSet is a structure similar to an array. The difference is that in an array index is an unique number, while in a HashSet each key needs to be translated into index with the help of a hash function. A hash function may produce the same results for different input data, the situation is called hash collision. A good hash function (yes, they could be bad and good) produces as many unique results on a given set of input data as possible.
因此，访问哈希集中的数据需要计算哈希函数(在Java中通常为.hashCode())和可能的冲突解决方案.估计为O(1)，即操作次数恒定.
So accessing data in a hash set costs calculations of a hash function (in Java usually this is .hashCode()) and possible conflict resolution. That is its estimated as O(1) i.e. a constant number of operations.
您应该了解，O(1)并不总是小于O(log(n))，它渐近性较小且足够大n.正确选择哈希函数也很重要.
You should understand that O(1) is not always less than O(log(n)), it's less asymptotically and on big enough n. Also a proper choice of a hash function does matter.
这篇关于HashSet和TreeSet性能测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
