# HashSet and TreeSet

I got some homework in which I had to take the novel War and Peace and put it into a HashSet and TreeSet respectively. I had to time it, to check differences and my question is whether my implementation is good or not. If the way I calculate time is even accurate. I am using

System.currentMillis()


but I was debating with myself whether

System.nanoTime()


would be a better choice. I might just have misunderstood something about the assignment since this just seems way too easy to be the actual solution.

Just to clarify: The code works. I am questioning the efficiency of my implementation.

package SetExercise;

import java.io.*;
import java.util.*;

public class FileToSet {

public static void main(String[] args) {
HashSet<String> hs = new HashSet<>();
TreeSet<String> ts = new TreeSet<>();
long start = System.currentTimeMillis();
fileToHashSet("war-and-peace.txt", hs);
long end = System.currentTimeMillis();
long elapsed = end - start;
System.out.println("Total time HashSet (ms): " + elapsed);
start = System.currentTimeMillis();
fileToTreeSet("war-and-peace.txt", ts);
end = System.currentTimeMillis();
elapsed = end - start;
System.out.println("Total time TreeSet (ms): " + elapsed);
}

static void fileToHashSet(String path, HashSet<String> set) {
try {
BufferedReader in = new BufferedReader(new FileReader(path));
while(in.readLine() != null) {
String line = in.readLine();
set.add(line);
}
in.close();
} catch(FileNotFoundException fnfe) {
System.out.println(fnfe.getMessage());
} catch(IOException ioe) {
System.out.println(ioe.getMessage());
}
}

static void fileToTreeSet(String path, TreeSet<String> set) {
try {
BufferedReader in = new BufferedReader(new FileReader(path));
while(in.readLine() != null) {
String line = in.readLine();
set.add(line);
}
in.close();
} catch(FileNotFoundException fnfe) {
System.out.println(fnfe.getMessage());
} catch(IOException ioe) {
System.out.println(ioe.getMessage());
}
}
}


## 6 Answers

I'm afraid you aren't actually reading the entire file into either Set. In fact, you're quite lucky this code isn't throwing an IOException.

while(in.readLine() != null) {
String line = in.readLine();
set.add(line);
}


This loop, present in both fileToHashSet and fileToTreeSet, is actually reading two lines every iteration. You're only placing every other line into either Set, which may or may not be significant. Try a loop like the below instead...

String line;
while ((line = in.readLine()) != null) {
set.add(line);
}


Aside from that, I believe you should be timing several trials and averaging these to get a more resilient statistic. Otherwise, your results might be too influenced by other factors. Benchmark accuracy is important, right? As you have it now, you're potentially even giving an advantage to the second benchmark, since the first may require slower disk I/O, while the second might be benefit from the OS caching the file in memory.

Other potential factors that may disadvantage the first are early VM initialization ocurring simultaneously, VM analysis "priming" the just-in-time compiler to allow better dynamic optimizations further along during the VM life, etc.

And, lastly, a small notice... if you have two catch blocks that do identical work, only differing in exception type, I suggest you take advantage of one of the newer features of Java 7 -- catching multiple exception types. In fact, you should probably also use the (also a recent addition) try-with-resources

try (final BufferedReader in = new BufferedReader(new FileReader(path))) {
String line;
while ((line = in.readLine()) != null) {
set.add(line);
}
} catch (final FileNotFoundException | IOException ex) {
System.err.println(ex);
}


Note you should probably not catch exceptions unless you actually plan to use them. Let them propagate out of main, where they will be printed to System.err, anyways.

There's also no reason to have two separate methods here, either; both are Set<String> -- why not make your method polymorphic?

P.S. use System.err for printing error messages rather than System.out.

P.P.S. I'll give an educated guess that HashSet will be faster than TreeSet by virtue of the underlying implementation... one necessitates a total order, after all.

P.P.P.S. Listen to Jon and use nanoTime here :-)

• Thanks for your answer. Now that you mention it you are right, I probably never load the entire file x) Thanks again! Sep 11, 2012 at 0:16
• pastebin.com/30a6mTKC This is what I ended up with. The HashSet seems to win consistently with about 20 to 25 ms. Sep 11, 2012 at 3:28
• @Vipar I wouldn't hold a reference to cache. Aside from that, you should be averaging over hundreds if not thousands of trials. You shouldn't keep summing start and end like that... just find the time before the iterations, compute the elapsed duration, and divide by 1,000 or how many iterations you expect to do. Aside from that, use Set.clear over initializing a new Set each iteration. Sep 11, 2012 at 3:32
• here: pastebin.com/KbMqEdbi Would you say this is more accurate? Sep 11, 2012 at 3:40
• @Vipar sure; here is my attempt. Sep 11, 2012 at 4:03

To measure the time taken, you should use System.nanoTime. That should only be used for "stopwatch" type operations - never for taking the "current system time" in a wall-clock way. Conversely, System.currentTimeMillis should not be used for "stopwatch" type operations, as it can be affected by system clock changes etc.

From the docs for nanoTime:

This method can only be used to measure elapsed time and is not related to any other notion of system or wall-clock time. The value returned represents nanoseconds since some fixed but arbitrary origin time (perhaps in the future, so values may be negative). The same origin is used by all invocations of this method in an instance of a Java virtual machine; other virtual machine instances are likely to use a different origin.

Note that the important point isn't the difference in granularity here - it's the difference in purpose. They could both be returning milliseconds, and it would still make sense to have two different calls.

• I see. Makes sense. So the way that I do it, is still correct though? Instead of using currentMillis() I should just use nanoTime()? Sep 10, 2012 at 23:32
• @Vipar: Sort of - but you should do this in a loop, and take the file system out of the equation. Load the file into memory first, e.g. into a List<String>. Chances are with your current code, IO will form the bulk of the time. Sep 10, 2012 at 23:34
• I think I have to load the file directly into either set though. Wouldn't first loading the file into a list then into a set, be kind of "cheating" if you had to check the time it took for either to successfully load a file into a set? Sep 10, 2012 at 23:36
• @Vipar: You should measure the time to load the data from a file, basically. That's unless you want to run one test loading into a HashSet, then clear out the file system cache etc before loading it into a TreeSet... Sep 10, 2012 at 23:38
• @Vipar: It would entirely depend on the operating system, but basically it's a pain. But yes, it would have very different results from not clearing the cache. Try it - I expect you'll see that whichever kind of set you test first, that will have poorer performance (the first time you run it after boot, at least). You need to work out what you care about: IO, or set performance. The IO is likely to drown out the set performance. Sep 10, 2012 at 23:44

If you want to test differences between HashSet<E> and TreeSet<E>, you should put all the other code out of the measured region — that includes any file I/O, stdout/stderr I/O, and possibly also set initialization (be it new or clear()) — to factor out the variability of interaction with OS and devices.

The measured region should contain only a loop in which you add the preloaded data into the set. You should therefore load the file first and keep it in a memory construct, e.g. String[].

If you decide to include the set initialization in the measurement, don't use clear(). In a real-world scenario, the set is usually used only once, hence use new. This is specifically important in the case of HashSet<E>, where additions of elements can result in extending the capacity of internal storage structure (a HashMap<K,V>) once a load threshold is exceeded. Calling subsequently clear() leaves the set capacity extended, thus it modifies conditions for all following measurement repetitions.

Speaking of the load threshold, you also have to decide upon the initial capacity, because when you set it too low (or leave it as default), the aforementioned HashSet<E> capacity extension may occur, resulting in a time-expensive rehashing (a repeated insertion) of all elements present in the set. Of course, this as well can be exactly what you want to include in the measurement / comparison.

A minor point would be the type parameter of a set, as the compiler generates some casts and bridge methods under the hood, but this is not meant to advocate the use of a raw type.

The core of the solution then should look like this:

public static void main(String[] args) {
final String[] data = preload(args[0]); // skipped for brevity
final long count = Long.valueOf(args[1]);
final Consumer<String> log = System.out::println;

log.accept("Total time HashSet (ns): " + measure(HashSet::new, data, count));
log.accept("Total time TreeSet (ns): " + measure(TreeSet::new, data, count));
}

static <E> long measure(Supplier<Set<E>> factory, E[] data, long count) {
return Stream.generate(factory)
.limit(count)
.mapToLong(set -> {
final Stream<E> stream = Stream.of(data);
final long start = System.nanoTime();
stream.forEach(set::add);
return System.nanoTime() - start;
}).sum();
}


Or if you opt for the clear() initialization method anyway:

static <E> long measureClear(Supplier<Set<E>> factory, E[] data, long count)) {
final Set<E> set = factory.get();
set.addAll(Arrays.asList(data)); // ensure capacity to avoid rehashing
return measure(() -> {set.clear(); return set;}, data, count);
}


A few libraries that you could use:

See also: Effective Java, 2nd edition, Item 47: Know and use the libraries

• Well, but Josh Bloch talks there explicitly about standard java libraries, not 3rd-party ones. Even if you can consider various Apache projects as 'common', there is quite many of them, in various quality and applicability, you can't keep track of them all. Using a 3rd-party library for just one call (that you can reimplement faster than you can find a suitable library) is a kind of an overkill... Sep 20, 2012 at 22:25
• Oftentimes the only third-party libraries students can use are ones provided by their professor.
– Eva
Jan 16, 2013 at 11:58

To the time measurements, I like the math in the way you compute the elapsed time by summing:

long start = 0;
long end = 0;
for(int i = 0; i < count; i++) {
start += System.nanoTime();
fileToSet(path,hs);
end += System.nanoTime();
hs.clear();
}
long average = (end - start) / count;


Why you should not do this, however, is that you can quickly run out of the long range. Slightly refined:

long elapsed = 0;
for(int i = 0; i < count; i++) {
long start = System.nanoTime();
fileToSet(path,hs);
elapsed += System.nanoTime() - start;
hs.clear();
}
long average = elapsed / count;


But what can happen here is that if the fileToSet() is faster than the system time granularity, you may end up summing zeroes. That's why you'd be better using an inverse approach instead — measure all operations outside the benchmarked code, then substract this from the total time:

long start = System.nanoTime();
long end = start;
long exclude = 0;
for(int i = 0; i < count; i++) {
exclude += System.nanoTime() - end;
fileToSet(path,hs);
end = System.nanoTime();
hs.clear();
}
long elapsed = (end - start) - exclude;
long average = elapsed / count;

final long[] tabTime = new long[6];
tabTime[0] = System.nanoTime();
Set<String> set;
// Java 7 used, no need to have HashSet<String>(5000)
set = new HashSet<>(5000); // numberOfLines
// set = new TreeSet<>(5000); // numberOfLines
try {
tabTime[1] = System.nanoTime();
final BufferedReader in = new BufferedReader(new FileReader(
System.getProperty("user.home") + "/WarAndPeace.txt"));
tabTime[2] = System.nanoTime();
String s;
while ((s = in.readLine()) != null) {
set.add(s);
}
tabTime[3] = System.nanoTime();
in.close();
} catch (final FileNotFoundException fnfe) {
System.out.println(fnfe.getMessage());
} catch (final IOException ioe) {
System.out.println(ioe.getMessage());
}
tabTime[4] = System.nanoTime();
final Set treeSet = new TreeSet(set);
tabTime[5] = System.nanoTime();
for (int i = 1, n = tabTime.length; i < n; i++) {
System.out.format("%d.%d%n", (tabTime[i] - tabTime[0]) / 1000000,
(tabTime[i] - tabTime[0]) % 1000000);
}


The test I've done show that putting String s outside the while is faster
But Scanner, in this case, it very slow (but it is very powerful and useful for managing input)
Hash is naturally faster than Tree, above all if they are opened with good size, and you have to put outside the time scope the print to have real results

• Just visually, this code looks chaotic and not readable. Sep 11, 2012 at 9:53
• @KonradRudolph it is the same than Vipar one with tool to trace time consumption. So he can play with HashSet/TreeSet and put the String in and out the while to look what's happen, no more. No intention to be verbose.
– cl-r
Sep 11, 2012 at 12:10