HashMap.putAll can cause redundant space waste
Xeno Amess
xenoamess at gmail.com
Fri Feb 4 18:39:42 UTC 2022
Sorry for my mistake.
After a more throughout dig in, this thing has already fixed several years
ago, at year 2015.
Issue close.
Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 21:40写道：
> Besides, is it worthy to develop a public float Math.ceil(float) function?
>
> Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 21:39写道：
>
>> patch applied.
>>
>> Index: src/java.base/share/classes/java/lang/Module.java
>> IDEA additional info:
>> Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
>> <+>UTF-8
>> ===================================================================
>> diff --git a/src/java.base/share/classes/java/lang/Module.java
>> b/src/java.base/share/classes/java/lang/Module.java
>> --- a/src/java.base/share/classes/java/lang/Module.java (revision
>> 3d926dd66ef6551e91a4ebbbc59dcff58f5ede5a)
>> +++ b/src/java.base/share/classes/java/lang/Module.java (revision
>> deeba25d15398fea8bc971ac915e348878b2c27a)
>> @@ -1133,7 +1133,7 @@
>> boolean isBootLayer = (ModuleLayer.boot() == null);
>>
>> int numModules = cf.modules().size();
>> - int cap = (int)(numModules / 0.75f + 1.0f);
>> + int cap = (int)Math.ceil(numModules / 0.75f);
>> Map<String, Module> nameToModule = new HashMap<>(cap);
>>
>> // to avoid repeated lookups and reduce iteration overhead, we
>> create
>> Index: src/java.base/share/classes/java/util/HashMap.java
>> IDEA additional info:
>> Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
>> <+>UTF-8
>> ===================================================================
>> diff --git a/src/java.base/share/classes/java/util/HashMap.java
>> b/src/java.base/share/classes/java/util/HashMap.java
>> --- a/src/java.base/share/classes/java/util/HashMap.java (revision
>> 3d926dd66ef6551e91a4ebbbc59dcff58f5ede5a)
>> +++ b/src/java.base/share/classes/java/util/HashMap.java (revision
>> deeba25d15398fea8bc971ac915e348878b2c27a)
>> @@ -495,9 +495,9 @@
>> int s = m.size();
>> if (s > 0) {
>> if (table == null) { // pre-size
>> - float ft = ((float)s / loadFactor) + 1.0F;
>> - int t = ((ft < (float)MAXIMUM_CAPACITY) ?
>> - (int)ft : MAXIMUM_CAPACITY);
>> + double dt = Math.ceil(s / loadFactor);
>> + int t = ((dt < (double)MAXIMUM_CAPACITY) ?
>> + (int)dt : MAXIMUM_CAPACITY);
>> if (t > threshold)
>> threshold = tableSizeFor(t);
>> } else {
>> @@ -1527,12 +1527,12 @@
>> } else if (mappings == 0) {
>> // use defaults
>> } else if (mappings > 0) {
>> - float fc = (float)mappings / lf + 1.0f;
>> - int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
>> + double dc = Math.ceil(mappings / lf);
>> + int cap = ((dc < DEFAULT_INITIAL_CAPACITY) ?
>> DEFAULT_INITIAL_CAPACITY :
>> - (fc >= MAXIMUM_CAPACITY) ?
>> + (dc >= MAXIMUM_CAPACITY) ?
>> MAXIMUM_CAPACITY :
>> - tableSizeFor((int)fc));
>> + tableSizeFor((int)dc));
>> float ft = (float)cap * lf;
>> threshold = ((cap < MAXIMUM_CAPACITY && ft <
>> MAXIMUM_CAPACITY) ?
>> (int)ft : Integer.MAX_VALUE);
>> Index: src/java.base/share/classes/java/util/WeakHashMap.java
>> IDEA additional info:
>> Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
>> <+>UTF-8
>> ===================================================================
>> diff --git a/src/java.base/share/classes/java/util/WeakHashMap.java
>> b/src/java.base/share/classes/java/util/WeakHashMap.java
>> --- a/src/java.base/share/classes/java/util/WeakHashMap.java (revision
>> 3d926dd66ef6551e91a4ebbbc59dcff58f5ede5a)
>> +++ b/src/java.base/share/classes/java/util/WeakHashMap.java (revision
>> deeba25d15398fea8bc971ac915e348878b2c27a)
>> @@ -251,7 +251,7 @@
>> * @since 1.3
>> */
>> public WeakHashMap(Map<? extends K, ? extends V> m) {
>> - this(Math.max((int) ((float)m.size() / DEFAULT_LOAD_FACTOR +
>> 1.0F),
>> + this(Math.max((int) Math.ceil(m.size() / DEFAULT_LOAD_FACTOR),
>> DEFAULT_INITIAL_CAPACITY),
>> DEFAULT_LOAD_FACTOR);
>> putAll(m);
>>
>> Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 18:45写道：
>>
>>> also find some other places have same problem.
>>> If some of your already-in people aggree, I would create a pr, but
>>> according to the rules seems I should wait for now.
>>>
>>> Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 18:42写道：
>>>
>>>> import java.lang.reflect.Array;
>>>> import java.lang.reflect.Field;
>>>> import java.util.HashMap;
>>>> import java.util.Map;
>>>>
>>>> public class TestMap {
>>>>
>>>> public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
>>>> HashMap<Object, Object> a = new HashMap<>();
>>>> fill12(a);
>>>> HashMap<Object, Object> b = new HashMap<>(12);
>>>> fill12(b);
>>>> HashMap<Object, Object> c = new HashMap<>(a);
>>>> HashMap<Object, Object> d = new HashMap<>();
>>>> d.putAll(a);
>>>> System.out.println("a : " + getArrayLength(a));
>>>> System.out.println("b : " + getArrayLength(b));
>>>> System.out.println("c : " + getArrayLength(c));
>>>> System.out.println("d : " + getArrayLength(d));
>>>> }
>>>>
>>>> public static void fill12(Map<Object, Object> map) {
>>>> for (int i = 0; i < 12; i++) {
>>>> map.put(i, i);
>>>> }
>>>> }
>>>>
>>>> public static int getArrayLength(Map<Object, Object> map) throws NoSuchFieldException, IllegalAccessException {
>>>> Field field = HashMap.class.getDeclaredField("table");
>>>> field.setAccessible(true);
>>>> Object table = field.get(map);
>>>> return Array.getLength(table);
>>>> }
>>>>
>>>> }
>>>>
>>>> run this and we get the output:
>>>>
>>>> a : 16
>>>> b : 16
>>>> c : 32
>>>> d : 32
>>>>
>>>> So I go see the codes.
>>>>
>>>> /**
>>>> * Implements Map.putAll and Map constructor.
>>>> *
>>>> * @param m the map
>>>> * @param evict false when initially constructing this map, else
>>>> * true (relayed to method afterNodeInsertion).
>>>> */
>>>> final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
>>>> int s = m.size();
>>>> if (s > 0) {
>>>> if (table == null) { // pre-size
>>>> float ft = ((float)s / loadFactor) + 1.0F;
>>>> int t = ((ft < (float)MAXIMUM_CAPACITY) ?
>>>> (int)ft : MAXIMUM_CAPACITY);
>>>> if (t > threshold)
>>>> threshold = tableSizeFor(t);
>>>> } else {
>>>> // Because of linked-list bucket constraints, we cannot
>>>> // expand all at once, but can reduce total resize
>>>> // effort by repeated doubling now vs later
>>>> while (s > threshold && table.length < MAXIMUM_CAPACITY)
>>>> resize();
>>>> }
>>>>
>>>> for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
>>>> K key = e.getKey();
>>>> V value = e.getValue();
>>>> putVal(hash(key), key, value, false, evict);
>>>> }
>>>> }
>>>> }
>>>>
>>>> yep I do think *((float)s / loadFactor) + 1.0F* here is wrong.
>>>>
>>>> It should be *Math.ceil((float)s / loadFactor)*
>>>>
>>>> So I wish to generate a pull request.
>>>>
>>>> Anyone interested?
>>>>
>>>>
More information about the core-libs-dev
mailing list