TimurMahammadov / google-collections

Automatically exported from code.google.com/p/google-collections
Apache License 2.0
0 stars 0 forks source link

Missing Maps.newHashMapWithCapacity #55

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago
Maps.newHashMapWithExpectedSize is probably very useful in most cases, but
sometimes we know how many elements exactly will be added.

Maps therefore needs a newHashMapWithCapacity method, just like Lists.

Original issue reported on code.google.com by sebd...@gmail.com on 2 Apr 2008 at 10:54

GoogleCodeExporter commented 9 years ago
If you "know how many elements exactly will be added", then
newHashMapWithExpectedSize() is what you *want* to be using.  If you want to 
control
the actual capacity (which isn't really a capacity, it's a minimum table size) 
and
load factor, just use the HashMap constructors directly, or make your own 
helper method.

By this same logic, Lists.newArrayListWithCapacity() was supposed to have been
deleted already, and will definitely be removed as of
http://code.google.com/p/google-collections/issues/detail?id=26

Original comment by kevin...@gmail.com on 2 Apr 2008 at 4:02

GoogleCodeExporter commented 9 years ago
To elaborate, it's better for performance reasons to create a HashMap whose 
capacity
is larger than its expected size. That way, the hash table will have more 
buckets,
reducing the likelihood of a collision and improving CPU performance. Though 
more
memory is needed, it's a net performance gain on average.

Original comment by jared.l....@gmail.com on 2 Apr 2008 at 5:35

GoogleCodeExporter commented 9 years ago
Oh I see, thanks for the details on performance improvements (maybe this could 
be
added to the javadoc).

Original comment by sebd...@gmail.com on 3 Apr 2008 at 7:28

GoogleCodeExporter commented 9 years ago
After reading the HashMap source code, I realized that my earlier remark was 
incorrect.

The capacity is the initial number of buckets. HashMap resizes its internal 
table when 
   size > loadFactor * capacity

Consequently, if you create a HashMap with a capacity equal to its subsequent 
size, a
resize will occur. The newHashMapWithExpectedSize method prevents that resize 
from
occuring.

I'll update the Javadoc to explain that.

Original comment by jared.l....@gmail.com on 3 Apr 2008 at 5:18

GoogleCodeExporter commented 9 years ago
Right.  That's true, so long as the load factor isn't 1.0. :)

(Note that even if the load factor is 1.0 does not mean that all the buckets 
will
ever be filled; that would only occur if there were zero collisions.)

The goal of nHMWES is to prevent that resize from occurring until the actual 
size
exceeds the expected size by more than a particular small margin.  Meaning you 
should
be able to get your expected size wrong by a little bit without consequence.  (I
haven't checked its implementation lately, but that's what it's supposed to do.)

Original comment by kevin...@gmail.com on 3 Apr 2008 at 7:05