Re: HashMap vs. TreeMap

On 2007.12.16., at 8: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

If you know the number of map elements in advance, you can pass that
to the constructor, i.e. if you need to store n elements, you can try:

Map map = new HashMap(n * 4 / 3, .75f);

Then you'll avoid resizing.

In case you wonder, 4/3 is the multiplicative inverse of .75f, which'd
be the default load factor java.util.HashMap uses. Of course, if you
have specific statistics for collision within your stored objects'
keys (or better yet, can affect it by implementing hashCode() on your
own key classes to be reasonably collision free), you can maybe run
with even a higher load factor (which means, less additional memory to
use).

Attila.

--
home: http://www.szegedi.org
weblog: http://constc.blogspot.com


> 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.
>
> Thanks
> Avinash

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

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