aspose file tools*
The moose likes Java in General and the fly likes HashMap behavior Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "HashMap behavior" Watch "HashMap behavior" New topic
Author

HashMap behavior

Prantik Biswas
Greenhorn

Joined: Mar 22, 2005
Posts: 7
I have a quick question on hashmap behavior.

Does the hashmap size ever decrease if has increased beyond its initial capacity?

In other words if initial capacity is 16 and I try to put 17 items in the hashmap size would increase to roughly 32. Now if I remove 16 items will the hashmap size drop back to 16??

thanks and regards
Edwin Dalorzo
Ranch Hand

Joined: Dec 31, 2004
Posts: 961
The javadoc API just says:


When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the capacity is roughly doubled by calling the rehash method.


It seems to indicate that it just happens to increase the size of the HashMap, but never to decrease it, since the event just happens the it "exceeds" certain value.

Maybe you can study the source clasess provided with the JDK and see what actually happens.
[ October 04, 2006: Message edited by: Edwin Dalorzo ]
sven studde
Ranch Hand

Joined: Sep 26, 2006
Posts: 148
Behind the scenes, the collection classes use ordinary arrays to store data. Since ordinary arrays are fixed in size, when you try to add some data to a collection, and the array behind the scenes is full, a new larger array is created, and all the data is copied over to the new array, and then the old array is destroyed. Obviously, doing all that creating, copying, and destroying is not very efficient. That's why collections double in size when they are expanded rather than just expanding by 1. If collections only expanded by 1, then all the creating, copying and destroying would take place everytime you added more data to a collection. Not very efficient.

When you decrease the size of a collection, there is usually not much of a reason to create a new smaller array, then copy all the data to the new array, and destroy the larger array. The data can happily remain in the larger array. If however you are doing something that is memory intensive, and some efficiency can be sacraficed, you can use the trimToSize() method provided by some collections to cut down on the memory used. However, I don't see trimToSize() in the method list for a HashMap.
[ October 05, 2006: Message edited by: sven studde ]
Edwin Dalorzo
Ranch Hand

Joined: Dec 31, 2004
Posts: 961
I think it is important to set clear that not all Java Collections use array to store data (for instance java.util.LinkedList does not).

Another important thing to take into account is that altough HashMap does use an array to store the data, when you delete an element, behind the scenes, that index in the underlying array is set to null, so that the actual object can be garbage collected.

The previous post seems to suggest that there is no problem in holding that information in memory, which would be a bad idead.

You can learn more about this reading Effective Java by Joshua Bloch, see the Item 5: Eliminate obsolete references.

The HashMap is a clear example of this. See in the source code of the HashMap the method clear(), to illustrate this explanation.
[ October 04, 2006: Message edited by: Edwin Dalorzo ]
Madhu Sudhana
Ranch Hand

Joined: Apr 16, 2006
Posts: 127
Hi Edwin

If there is online facility to go through the effective java book

can you send us the link


"And the trouble is, if you don't risk anything, you risk even more." -- Erica Jong.
Prantik Biswas
Greenhorn

Joined: Mar 22, 2005
Posts: 7
Thanks for the prompt reply folks.

Let me look into Sun's code and will post back my findings
 
 
subject: HashMap behavior