• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

HashMap behavior

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 961
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ranch Hand
Posts: 148
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 961
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Edwin

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

can you send us the link
 
Prantik Biswas
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the prompt reply folks.

Let me look into Sun's code and will post back my findings
reply
    Bookmark Topic Watch Topic
  • New Topic