RFR: 8186958: Need method to create pre-sized HashMap

XenoAmess duke at openjdk.java.net
Wed Mar 23 18:57:25 UTC 2022


On Wed, 23 Mar 2022 18:41:59 GMT, XenoAmess <duke at openjdk.java.net> wrote:

> 8186958: Need method to create pre-sized HashMap

I do have a local test to make sure the 3 functions I provided can produce equal capacity HashMap, but I think it does not need to be added into jdk.

import java.lang.reflect.Array;
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;

public class CalculateHashMapCapacityFunctionTest {

    /**
     * Calculate initial capacity for HashMap based classes, from expected size.
     *
     * @param expectedSize expected size
     * @return initial capacity for HashMap based classes.
     * @since 19
     */
    private static int calculateHashMapCapacity1(int expectedSize) {
        return (int) Math.ceil(expectedSize / 0.75);
    }

    /**
     * Calculate initial capacity for HashMap based classes, from expected size.
     *
     * @param expectedSize expected size
     * @return initial capacity for HashMap based classes.
     * @since 19
     */
    private static int calculateHashMapCapacity2(int expectedSize) {
        if (expectedSize >= 1610612736) {
            return Integer.MAX_VALUE;
        }
        return (expectedSize + (expectedSize + 2) / 3);
    }

    /**
     * Calculate initial capacity for HashMap based classes, from expected size.
     *
     * @param expectedSize expected size
     * @return initial capacity for HashMap based classes.
     * @since 19
     */
    private static int calculateHashMapCapacity3(int expectedSize) {
        if (expectedSize >= 805306368) {
            return (1 << 30);
        }
        return (expectedSize + (expectedSize + 2) / 3);
    }

    public static void main(String[] args) throws Exception {
        for (int i = Integer.MAX_VALUE; i >= 0; --i) {
            Map<Object, Object> map1 = new HashMap<>(calculateHashMapCapacity1(i));
            map1.put("1", "1");
            int length1 = getArrayLength(map1);
            Map<Object, Object> map2 = new HashMap<>(calculateHashMapCapacity2(i));
            map2.put("1", "1");
            int length2 = getArrayLength(map2);
            Map<Object, Object> map3 = new HashMap<>(calculateHashMapCapacity3(i));
            map3.put("1", "1");
            if (i % 1000000 == 0) {
                System.out.println("running : " + i);
            }
            int length3 = getArrayLength(map3);
            if (length1 != length2 || length1 != length3) {
                throw new RuntimeException("wrong: " + i);
            }
        }
    }

    static Field FIELD;

    static {
        try {
            FIELD = HashMap.class.getDeclaredField("table");
            FIELD.setAccessible(true);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static int getArrayLength(Map<Object, Object> map) throws Exception {
        Object table = FIELD.get(map);
        return Array.getLength(table);
    }

}

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

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


More information about the core-libs-dev mailing list