Re: HashMap vs. TreeMap

On Saturday 15 December 2007 23:04, Avinash Lakshman wrote:
> Hi All
>
> I need to store about a million key/value pairs. Which is more memory
> efficient HashMap or TreeMap? With the HashMap it looks like the
> resizing happens to be exponential but that is not the case with
> TreeMap i.e sometimes I may have 64,000 keys but the internal table
> allocated with the HashMap is at nearly double the value. I do not
> care about access times i.e I need a sparse HashMap. How can I
> acheive this? Can I think of the TreeMap as a poor man's sparse
> HashMap? Are there  any other implementations I could look at? Please
> advice.

Two things:

1) You should consider the Gnu Trove / Trove4J collections, especially
with very large hash tables. The implementation is much more
space-efficient (it does not use chaining, which wastes a lot of
memory; it also does not require wrapper objects.) Furthermore, the
API, while a drop-in, type-compatible with the standard collections
library, contains extra sets of classes for storing primitive types
directly (non-boxed).

2) If you know how big the table is going to be, you should allocate it
that big from the start and not rely on the automatic table growing
behavior that occurs when the table overflows (or, in the case chained
implementations, the chains get too long).


What is a "sparse" hash map? Trove4J's tables allow you control the
maximum load factor before the table is grown, but as I said, you
shouldn't allow that to happen if you don't have to.


<http://trove4j.sourceforge.net/>


> Thanks
> Avinash


Randall Schulz

===================================
This list is hosted by DevelopMentor®  http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com