RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v23]

[Stuart Marks]

On Wed, 2 Mar 2022 18:48:46 GMT, XenoAmess <duke at openjdk.java.net> wrote:

>> 8281631: HashMap copy constructor and putAll can over-allocate table
>
> XenoAmess has updated the pull request incrementally with one additional commit since the last revision:
> 
>   revert changes to IdentityHashMap

src/java.base/share/classes/java/util/HashMap.java line 498:

> 496:         if (s > 0) {
> 497:             if (table == null) { // pre-size
> 498:                 double dt = Math.ceil(s / loadFactor);

Quick update on this. The division must be done in double, not float, before being passed to `Math.ceil`. I'd recommend casting the load factor to double:

    double dt = Math.ceil(s / (double) loadFactor);

The reason is that the significand of a float has only 24 bits, so the low order 8 bits of the eventual `int` will end up being zeroes even when they have some significant values. This starts to occur at larger sizes. For example, if `s` is 25165825, the result is 33554434.0 with double division but it's only 33554432.0 with float division. This latter value is too small, so if it were used the HashMap would need to be resized when `s` mappings are added.

Similar changes should be made in `readObject` below and in `WeakHashMap`.

I haven't had a chance to look at the test yet, sorry. You might want think about how to test for cases like this. Don't go off the deep end though. I don't think we want to have a test that creates lots of maps with 25 million entries, and we also don't want to duplicate the computations in the test itself like the Enum ConstantDirectory test does.

src/java.base/share/classes/java/util/HashMap.java line 1530:

> 1528:             // use defaults
> 1529:         } else if (mappings > 0) {
> 1530:             double dc = Math.ceil(mappings / lf);

As above, cast `lf` to `double`.

src/java.base/share/classes/java/util/WeakHashMap.java line 252:

> 250:      */
> 251:     public WeakHashMap(Map<? extends K, ? extends V> m) {
> 252:         this(Math.max((int) Math.ceil(m.size() / 0.75),

Use `(double) DEFAULT_LOAD_FACTOR` in the denominator.

src/java.base/share/classes/java/util/WeakHashMap.java line 558:

> 556:          */
> 557:         if (numKeysToBeAdded > threshold) {
> 558:             int targetCapacity = (int)Math.ceil(numKeysToBeAdded / loadFactor);

Cast to double here too.

-------------

PR: https://git.openjdk.java.net/jdk/pull/7431