Originally posted by Thomas Paul:
1.4.1 on Win 2K pro:
total time for TreeMap: 422
total time for Hashtable: 156
total time for HashMap: 312
total time for Hashtable presized: 109
total time for HashMap presized: 172
Originally posted by Ron Newman:
But you're going to take that hit anyway, because neither HashMap nor Hashtable is final.
You're probably aware of this, but Hashtable seems to outperform HashMap (at least for the general case) in the Java 1.4 and 1.4.1. There has been a little bit of confusion over at the JavaRanch Performance forum where we've been discussing the issue.
Hi. This is the first I've heard of this. I looked into it briefly and I believe I know what's going on. I don't have time to write it up tonight, but I'll try to do it soon. For starters, the microbenchmark is not good. It should time the test repeatedly so that you can make sure you're getting a repeatable result. Timing the first run gives you startup transients, which are not what you want. Also you have to figure out how you want to deal with garbage collection: either eliminate it from the timings by calling System.gc() outside of the timing loop, or time runs long enough to predictably include GC.
That said, Hashtable really is faster than HashMap for the data set in this benchmark: strings formed from sequential numbers. The pre 1.4 HashMap implementation, which was retained in Hashtable, does very well on sequential keys because it doesn't scatter them at all: it puts them in sequential buckets. As a result, there are *no* collisions. The price you pay is that certain regular but non-consecutive sequences will all hash to the same bucket, resulting in horrible performance. The 1.4 version (and especially the 1.4.1 version) scatters the keys pseudo-randomly, resulting in occasional collisions when hashing consecutive sequences like the one in the microbenchmark. (The mathematics of this is pretty simple; you can easily calculate roughly how many collisions you'll get.) To test this conjecture, use pseudo-random numbers in the keys instead of consecutive. I did, and found that HashMap is a bit faster than Hashtable, as expected.
Loosely speaking, then, the 1.4.1 implementation is a better general purpose implementation. If you know that you'll be dealing with a consecutive sequence, the 1.3 implementation (still present in Hashtable) could well be faster. On the other hand, for consecutive keys you could just use an array (or List), which would be *really* fast : )
I hope this brief letter was at all comprehensible.
Time is the best teacher, but unfortunately, it kills all of its students - Robin Williams. tiny ad:
SKIP - a book about connecting industrious people with elderly land ownershttps://coderanch.com/t/skip-book