Why is ArrayList faster than HashSet in java?
I'm used to the fact that HashSet is a pretty fast implementation of a data structure because it uses hashes (and in turn is implemented through HashMap). I was solving some problems and decided to check the performance, so here it is:
You are given an array of numbers - [11, 3, 11, 11, 3, 2, 0, -2, 2] You must write a function that returns a number that appears "odd" times.
Here is my solution:
public class OddNumInArray {
public static List<Integer> oddNumList(int [] ar){
Collection <Integer> l = new ArrayList<>();
for (int n: ar) {
if (l.contains(n)) {
l.remove(n);
}
else {
l.add(n);
}
}
return (List) l;
}
public static Set<Integer> oddNumHSet(int [] ar){
Set <Integer> l = new HashSet<>();
for (int n: ar) {
if (l.contains(n)) {
l.remove(n);
}
else {
l.add(n);
}
}
return l;
}
public static void main(String [ ]arg) {
int [] a1 = new int [10000000];
for (int i=0; i<10; i++){
a1[i]=(new Random()).nextInt(5);
}
long cur= System.nanoTime();
System.out.println(oddNumList(a1));
long c1 = System.nanoTime()-cur;
System.out.println("TIME CONSUMED:" +c1);
cur= System.nanoTime();
System.out.println(oddNumHSet(a1));
long c2 = System.nanoTime()-cur;
System.out.println("TIME CONSUMED:" + c2);
System.out.println("c1/c2*100: "+ (new Double(c1)/new Double(c2)*100));
}
}
And here's the output:
[1, 0]
TIME CONSUMED:101804000
[0, 1]
TIME CONSUMED:183261000
c1/c2*100: 55.55137208680516
So why the implementation with ArrayList is almost 2 times faster than one with HashSet? Thank.
+3
source to share