I don't know of any benchmarks and never heard of Trove.  But I can tell
you that, having made extensive use of Java's Collections, they perform
quite well.  (And see the Javadocs for some performance information.)

As to whether to use a HashMap or TreeMap, I'd say it would depend on
just how often you need the entire set of data in the sorted order of
your keys.  If it's seldom, and the data set isn't exceedingly large, I
suppose it *could* make sense to get all the keys and iterate over them
in sorted order.  If you need to iterate over the entire set frequently,
then the TreeMap is likely to be better.  Without more information, it's
even possible that neither of these would be your ideal choice...it all
depends on what you need to accomplish.

= Steve =