16370

Growth Policy of ArrayList in Java 6SE

I was wondering if anyone knows the growth policy of ArrayList in Java 1.6? The java doc says

The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

But I just wonder the details because I know the size I'm targeting to start but I want to make sure I'm making the initial size big enough to not cause an instant resize. I know with HashMap you can set a load factor is there something similar happening in the back ground? Or is it always growing when space is out?

Answer1:

ArrayList doesn't need a loadFactor as it always grows when it is 100% filled, so you can create it with exactly the size you know in advance and it won't grow if you fill that many elements in later. Hashtables on the other hand become ever more inefficient the more they are filled, and thus you can ajust the tradoff between performance and wasted space with the loadFactor, but this isn't the case for growable Arrays like ArrayList.

Answer2:

This is what I see when I look at the source of ensureCapacity:

int newCapacity = (oldCapacity * 3)/2 + 1;

Answer3:

You can read the source for yourself. Every copy of the Sun JDK comes with a src.zip that contains the source.

Answer4:

int newCapacity = oldCapacity + (oldCapacity >> 1);

It is 50% increment .

if 100 elements are there ensureCapacityInternal() will increase to size of 150 .

Please check source code in JDK 7

Recommend

  • Visual Studio 2008, Vista x64 and Kaspersky = blue screens (BSOD)?
  • Finding path obstacles in a 2D image
  • Bug in Storyboard animation?
  • phase unwrap issue (the unwrapping of the phases is not correcly)?
  • How to join two tables and map the result to a case class in slick
  • ExtJS 4 Spring 3 file upload. Server sends bad response content type
  • Build entire solution for .NET 4 and .NET 4.5 and copy files to specific folders
  • how to force the use of cmov in gcc and VS
  • How to clear out the contents of a map when clear() method call throws UnsupportedOperationException
  • Background not visible in surface view
  • Update Search Results to Lazy Adapter in android
  • How to apply async task into this
  • WebApp in AppServices vs CloudService
  • How do i find all references to a user control
  • The symbol you provided is not a function
  • C# 4 and CLR Compatibility
  • Action Pack components in Rails
  • react split panel resize
  • SqlCommand back up Database
  • uml Composition relationships to RDF and OWL
  • blade.php method outputting it's result to the form
  • Azure table store snapshot/backup capability
  • xcode don't localize specific strings
  • Using JRuby with Rails 3.2
  • xtable package: Skipping some rows in the output
  • How integrated is Collada to OpenGL ES
  • Atlas images wrong size on iPad iOS 9
  • Body moving without any force applied? (Box2d)
  • Change JButton Shape while respecting Look And Feel
  • Why HTML5 Canvas with a larger size stretch a drawn line?
  • TFS: Get latest causes slow project reloading
  • Controls, properties, events and timers running in design time
  • VBA Convert delimiter text file to Excel
  • How do I rollback to a specific git commit
  • using conditional logic : check if record exists; if it does, update it, if not, create it
  • python regex in pyparsing
  • Setting background image for body element in xhtml (for different monitors and resolutions)
  • Android Google Maps API OnLocationChanged only called once
  • How can I use threading to 'tick' a timer to be accessed by other threads?
  • jQuery Masonry / Isotope and fluid images: Momentary overlap on window resize