Re: HashMap vs. TreeMap

HashMap is much faster--O(1) vs. O(log N).

Memory wise, each approach has a wrapper object per entry which is roughly
the same size. Depending on the implementation, each wrapper takes up
roughly 24 bytes (8 for the wrapper, 12 bytes for 3 references, 4 bytes for
an int), so N * 24. HashMap has an array which takes up another 4 bytes per
entry, and the default load factor is 0.75, so N * 4 * 4 / 3. This doesn't
take into account the impact of collisions, but it's close enough.

TreeMap: N * 24 bytes
HashMap: N * 29.3 bytes

I would go with HashMap. It only uses about 5 more bytes per entry which,
compared to 24, isn't much considering the speed improvements.

Bob

On Dec 16, 2007 8:04 AM, Avinash Lakshman <[email protected]> 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.esometimes 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
>
> _________________________________________________________________
> Get the power of Windows + Web with the new Windows Live.
> http://www.windowslive.com?ocid=TXT_TAGHM_Wave2_powerofwindows_122007
> ===================================
> This list is hosted by DevelopMentor(R)  http://www.develop.com
>
> View archives and manage your subscription(s) at
> http://discuss.develop.com
>

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

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