• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2021 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 /*
18  * @test
19  * @bug 8005698
20  * @run testng/othervm -Dtest.map.collisions.shortrun=true InPlaceOpsCollisions
21  * @summary Ensure overrides of in-place operations in Maps behave well with lots of collisions.
22  */
23 package test.java.util.Map;
24 
25 import java.util.Map;
26 import java.util.function.BiFunction;
27 import java.util.function.Function;
28 import java.util.function.Supplier;
29 
30 import org.testng.annotations.Test;
31 import static org.testng.Assert.assertTrue;
32 import static org.testng.Assert.assertFalse;
33 import static org.testng.Assert.assertEquals;
34 import static org.testng.Assert.assertNull;
35 
36 public class InPlaceOpsCollisions extends MapWithCollisionsProviders {
37 
38     @Test(dataProvider = "mapsWithObjectsAndStrings")
testPutIfAbsent(String desc, Supplier<Map<Object, Object>> ms, Object val)39     public void testPutIfAbsent(String desc, Supplier<Map<Object, Object>> ms, Object val) {
40         Map<Object, Object> map = ms.get();
41         Object[] keys = map.keySet().toArray();
42         Object retVal;
43         removeOddKeys(map, keys);
44         for (int i = 0; i < keys.length; i++) {
45             retVal = map.putIfAbsent(keys[i], val);
46             if (i % 2 == 0) { // even: not absent, not put
47 
48                 assertEquals(retVal, keys[i],
49                         String.format("putIfAbsent: (%s[%d]) retVal", desc, i));
50                 assertEquals(keys[i], map.get(keys[i]),
51                         String.format("putIfAbsent: get(%s[%d])", desc, i));
52                 assertTrue(map.containsValue(keys[i]),
53                         String.format("putIfAbsent: containsValue(%s[%d])", desc, i));
54             } else { // odd: absent, was put
55                 assertNull(retVal,
56                         String.format("putIfAbsent: (%s[%d]) retVal", desc, i));
57                 assertEquals(val, map.get(keys[i]),
58                         String.format("putIfAbsent: get(%s[%d])", desc, i));
59                 assertFalse(map.containsValue(keys[i]),
60                         String.format("putIfAbsent: !containsValue(%s[%d])", desc, i));
61             }
62             assertTrue(map.containsKey(keys[i]),
63                     String.format("insertion: containsKey(%s[%d])", desc, i));
64         }
65         assertEquals(map.size(), keys.length,
66                 String.format("map expected size m%d != k%d", map.size(), keys.length));
67     }
68 
69     @Test(dataProvider = "mapsWithObjectsAndStrings")
testRemoveMapping(String desc, Supplier<Map<Object, Object>> ms, Object val)70     public void testRemoveMapping(String desc, Supplier<Map<Object, Object>> ms, Object val) {
71         Map<Object, Object> map = ms.get();
72         Object[] keys = map.keySet().toArray();
73         boolean removed;
74         int removes = 0;
75         remapOddKeys(map, keys, val);
76         for (int i = 0; i < keys.length; i++) {
77             removed = map.remove(keys[i], keys[i]);
78             if (i % 2 == 0) { // even: original mapping, should be removed
79                 assertTrue(removed,
80                         String.format("removeMapping: retVal(%s[%d])", desc, i));
81                 assertNull(map.get(keys[i]),
82                         String.format("removeMapping: get(%s[%d])", desc, i));
83                 assertFalse(map.containsKey(keys[i]),
84                         String.format("removeMapping: !containsKey(%s[%d])", desc, i));
85                 assertFalse(map.containsValue(keys[i]),
86                         String.format("removeMapping: !containsValue(%s[%d])", desc, i));
87                 removes++;
88             } else { // odd: new mapping, not removed
89                 assertFalse(removed,
90                         String.format("removeMapping: retVal(%s[%d])", desc, i));
91                 assertEquals(val, map.get(keys[i]),
92                         String.format("removeMapping: get(%s[%d])", desc, i));
93                 assertTrue(map.containsKey(keys[i]),
94                         String.format("removeMapping: containsKey(%s[%d])", desc, i));
95                 assertTrue(map.containsValue(val),
96                         String.format("removeMapping: containsValue(%s[%d])", desc, i));
97             }
98         }
99         assertEquals(map.size(), keys.length - removes,
100                 String.format("map expected size m%d != k%d", map.size(), keys.length - removes));
101     }
102 
103     @Test(dataProvider = "mapsWithObjectsAndStrings")
testReplaceOldValue(String desc, Supplier<Map<Object, Object>> ms, Object val)104     public void testReplaceOldValue(String desc, Supplier<Map<Object, Object>> ms, Object val) {
105         // remap odds to val
106         // call replace to replace for val, for all keys
107         // check that all keys map to value from keys array
108         Map<Object, Object> map = ms.get();
109         Object[] keys = map.keySet().toArray();
110         boolean replaced;
111         remapOddKeys(map, keys, val);
112 
113         for (int i = 0; i < keys.length; i++) {
114             replaced = map.replace(keys[i], val, keys[i]);
115             if (i % 2 == 0) { // even: original mapping, should not be replaced
116                 assertFalse(replaced,
117                         String.format("replaceOldValue: retVal(%s[%d])", desc, i));
118             } else { // odd: new mapping, should be replaced
119                 assertTrue(replaced,
120                         String.format("replaceOldValue: get(%s[%d])", desc, i));
121             }
122             assertEquals(keys[i], map.get(keys[i]),
123                     String.format("replaceOldValue: get(%s[%d])", desc, i));
124             assertTrue(map.containsKey(keys[i]),
125                     String.format("replaceOldValue: containsKey(%s[%d])", desc, i));
126             assertTrue(map.containsValue(keys[i]),
127                     String.format("replaceOldValue: containsValue(%s[%d])", desc, i));
128         }
129         assertFalse(map.containsValue(val),
130                 String.format("replaceOldValue: !containsValue(%s[%s])", desc, val));
131         assertEquals(map.size(), keys.length,
132                 String.format("map expected size m%d != k%d", map.size(), keys.length));
133     }
134 
135     @Test(dataProvider = "mapsWithObjectsAndStrings")
testReplaceIfMapped(String desc, Supplier<Map<Object, Object>> ms, Object val)136     public void testReplaceIfMapped(String desc, Supplier<Map<Object, Object>> ms, Object val) {
137         // remove odd keys
138         // call replace for all keys[]
139         // odd keys should remain absent, even keys should be mapped to EXTRA, no value from keys[] should be in map
140         Map<Object, Object> map = ms.get();
141         Object[] keys = map.keySet().toArray();
142         int expectedSize1 = 0;
143         removeOddKeys(map, keys);
144         int expectedSize2 = map.size();
145 
146         for (int i = 0; i < keys.length; i++) {
147             Object retVal = map.replace(keys[i], val);
148             if (i % 2 == 0) { // even: still in map, should be replaced
149                 assertEquals(retVal, keys[i],
150                         String.format("replaceIfMapped: retVal(%s[%d])", desc, i));
151                 assertEquals(val, map.get(keys[i]),
152                         String.format("replaceIfMapped: get(%s[%d])", desc, i));
153                 assertTrue(map.containsKey(keys[i]),
154                         String.format("replaceIfMapped: containsKey(%s[%d])", desc, i));
155                 expectedSize1++;
156             } else { // odd: was removed, should not be replaced
157                 assertNull(retVal,
158                         String.format("replaceIfMapped: retVal(%s[%d])", desc, i));
159                 assertNull(map.get(keys[i]),
160                         String.format("replaceIfMapped: get(%s[%d])", desc, i));
161                 assertFalse(map.containsKey(keys[i]),
162                         String.format("replaceIfMapped: containsKey(%s[%d])", desc, i));
163             }
164             assertFalse(map.containsValue(keys[i]),
165                     String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i));
166         }
167         assertTrue(map.containsValue(val),
168                 String.format("replaceIfMapped: containsValue(%s[%s])", desc, val));
169         assertEquals(map.size(), expectedSize1,
170                 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1));
171         assertEquals(map.size(), expectedSize2,
172                 String.format("map expected size#2 m%d != k%d", map.size(), expectedSize2));
173 
174     }
175 
testComputeIfAbsent(Map<T, T> map, String desc, T[] keys, Function<T, T> mappingFunction)176     private static <T> void testComputeIfAbsent(Map<T, T> map, String desc, T[] keys,
177             Function<T, T> mappingFunction) {
178         // remove a third of the keys
179         // call computeIfAbsent for all keys, func returns EXTRA
180         // check that removed keys now -> EXTRA, other keys -> original val
181         T expectedVal = mappingFunction.apply(keys[0]);
182         T retVal;
183         int expectedSize = 0;
184         removeThirdKeys(map, keys);
185         for (int i = 0; i < keys.length; i++) {
186             retVal = map.computeIfAbsent(keys[i], mappingFunction);
187             if (i % 3 != 2) { // key present, not computed
188                 assertEquals(retVal, keys[i],
189                         String.format("computeIfAbsent: (%s[%d]) retVal", desc, i));
190                 assertEquals(keys[i], map.get(keys[i]),
191                         String.format("computeIfAbsent: get(%s[%d])", desc, i));
192                 assertTrue(map.containsValue(keys[i]),
193                         String.format("computeIfAbsent: containsValue(%s[%d])", desc, i));
194                 assertTrue(map.containsKey(keys[i]),
195                         String.format("insertion: containsKey(%s[%d])", desc, i));
196                 expectedSize++;
197             } else { // key absent, computed unless function return null
198                 assertEquals(retVal, expectedVal,
199                         String.format("computeIfAbsent: (%s[%d]) retVal", desc, i));
200                 assertEquals(expectedVal, map.get(keys[i]),
201                         String.format("computeIfAbsent: get(%s[%d])", desc, i));
202                 assertFalse(map.containsValue(keys[i]),
203                         String.format("computeIfAbsent: !containsValue(%s[%d])", desc, i));
204                 // mapping should not be added if function returns null
205                 assertTrue(map.containsKey(keys[i]) != (expectedVal == null),
206                         String.format("insertion: containsKey(%s[%d])", desc, i));
207                 if (expectedVal != null) {
208                     expectedSize++;
209                 }
210             }
211         }
212         if (expectedVal != null) {
213             assertTrue(map.containsValue(expectedVal),
214                     String.format("computeIfAbsent: containsValue(%s[%s])", desc, expectedVal));
215         }
216         assertEquals(map.size(), expectedSize,
217                 String.format("map expected size m%d != k%d", map.size(), expectedSize));
218     }
219 
220     @Test(dataProvider = "mapsWithObjectsAndStrings")
testComputeIfAbsentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val)221     public void testComputeIfAbsentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val) {
222         Map<Object, Object> map = ms.get();
223         Object[] keys = map.keySet().toArray();
224         testComputeIfAbsent(map, desc, keys, (k) -> val);
225     }
226 
227     @Test(dataProvider = "mapsWithObjectsAndStrings")
testComputeIfAbsentNull(String desc, Supplier<Map<Object, Object>> ms, Object val)228     public void testComputeIfAbsentNull(String desc, Supplier<Map<Object, Object>> ms, Object val) {
229         Map<Object, Object> map = ms.get();
230         Object[] keys = map.keySet().toArray();
231         testComputeIfAbsent(map, desc, keys, (k) -> null);
232     }
233 
testComputeIfPresent(Map<T, T> map, String desc, T[] keys, BiFunction<T, T, T> mappingFunction)234     private static <T> void testComputeIfPresent(Map<T, T> map, String desc, T[] keys,
235             BiFunction<T, T, T> mappingFunction) {
236         // remove a third of the keys
237         // call testComputeIfPresent for all keys[]
238         // removed keys should remain absent, even keys should be mapped to $RESULT
239         // no value from keys[] should be in map
240         T funcResult = mappingFunction.apply(keys[0], keys[0]);
241         int expectedSize1 = 0;
242         removeThirdKeys(map, keys);
243 
244         for (int i = 0; i < keys.length; i++) {
245             T retVal = map.computeIfPresent(keys[i], mappingFunction);
246             if (i % 3 != 2) { // key present
247                 if (funcResult == null) { // was removed
248                     assertFalse(map.containsKey(keys[i]),
249                             String.format("replaceIfMapped: containsKey(%s[%d])", desc, i));
250                 } else { // value was replaced
251                     assertTrue(map.containsKey(keys[i]),
252                             String.format("replaceIfMapped: containsKey(%s[%d])", desc, i));
253                     expectedSize1++;
254                 }
255                 assertEquals(retVal, funcResult,
256                         String.format("computeIfPresent: retVal(%s[%s])", desc, i));
257                 assertEquals(funcResult, map.get(keys[i]),
258                         String.format("replaceIfMapped: get(%s[%d])", desc, i));
259 
260             } else { // odd: was removed, should not be replaced
261                 assertNull(retVal,
262                         String.format("replaceIfMapped: retVal(%s[%d])", desc, i));
263                 assertNull(map.get(keys[i]),
264                         String.format("replaceIfMapped: get(%s[%d])", desc, i));
265                 assertFalse(map.containsKey(keys[i]),
266                         String.format("replaceIfMapped: containsKey(%s[%d])", desc, i));
267             }
268             assertFalse(map.containsValue(keys[i]),
269                     String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i));
270         }
271         assertEquals(map.size(), expectedSize1,
272                 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1));
273     }
274 
275     @Test(dataProvider = "mapsWithObjectsAndStrings")
testComputeIfPresentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val)276     public void testComputeIfPresentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val) {
277         Map<Object, Object> map = ms.get();
278         Object[] keys = map.keySet().toArray();
279         testComputeIfPresent(map, desc, keys, (k, v) -> val);
280     }
281 
282     @Test(dataProvider = "mapsWithObjectsAndStrings")
testComputeIfPresentNull(String desc, Supplier<Map<Object, Object>> ms, Object val)283     public void testComputeIfPresentNull(String desc, Supplier<Map<Object, Object>> ms, Object val) {
284         Map<Object, Object> map = ms.get();
285         Object[] keys = map.keySet().toArray();
286         testComputeIfPresent(map, desc, keys, (k, v) -> null);
287     }
288 
289     @Test(dataProvider = "hashMapsWithObjects")
testComputeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val)290     public void testComputeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val) {
291         // remove a third of the keys
292         // call compute() for all keys[]
293         // all keys should be present: removed keys -> EXTRA, others to k-1
294         Map<IntKey, IntKey> map = ms.get();
295         IntKey[] keys = map.keySet().stream().sorted().toArray(IntKey[]::new);
296         BiFunction<IntKey, IntKey, IntKey> mappingFunction = (k, v) -> {
297             if (v == null) {
298                 return val;
299             } else {
300                 return keys[k.getValue() - 1];
301             }
302         };
303         removeThirdKeys(map, keys);
304         for (int i = 1; i < keys.length; i++) {
305             IntKey retVal = map.compute(keys[i], mappingFunction);
306             if (i % 3 != 2) { // key present, should be mapped to k-1
307                 assertEquals(retVal, keys[i - 1],
308                         String.format("compute: retVal(%s[%d])", desc, i));
309                 assertEquals(keys[i - 1], map.get(keys[i]),
310                         String.format("compute: get(%s[%d])", desc, i));
311             } else { // odd: was removed, should be replaced with EXTRA
312                 assertEquals(retVal, val,
313                         String.format("compute: retVal(%s[%d])", desc, i));
314                 assertEquals(val, map.get(keys[i]),
315                         String.format("compute: get(%s[%d])", desc, i));
316             }
317             assertTrue(map.containsKey(keys[i]),
318                     String.format("compute: containsKey(%s[%d])", desc, i));
319         }
320         assertEquals(map.size(), keys.length,
321                 String.format("map expected size#1 m%d != k%d", map.size(), keys.length));
322         assertTrue(map.containsValue(val),
323                 String.format("compute: containsValue(%s[%s])", desc, val));
324         assertFalse(map.containsValue(null),
325                 String.format("compute: !containsValue(%s,[null])", desc));
326     }
327 
328     @Test(dataProvider = "mapsWithObjectsAndStrings")
testComputeNull(String desc, Supplier<Map<Object, Object>> ms, Object val)329     public void testComputeNull(String desc, Supplier<Map<Object, Object>> ms, Object val) {
330         // remove a third of the keys
331         // call compute() for all keys[]
332         // removed keys should -> EXTRA
333         // for other keys: func returns null, should have no mapping
334         Map<Object, Object> map = ms.get();
335         Object[] keys = map.keySet().toArray();
336         BiFunction<Object, Object, Object> mappingFunction = (k, v) -> {
337             // if absent/null -> EXTRA
338             // if present -> null
339             if (v == null) {
340                 return val;
341             } else {
342                 return null;
343             }
344         };
345         int expectedSize = 0;
346         removeThirdKeys(map, keys);
347         for (int i = 0; i < keys.length; i++) {
348             Object retVal = map.compute(keys[i], mappingFunction);
349             if (i % 3 != 2) { // key present, func returned null, should be absent from map
350                 assertNull(retVal,
351                         String.format("compute: retVal(%s[%d])", desc, i));
352                 assertNull(map.get(keys[i]),
353                         String.format("compute: get(%s[%d])", desc, i));
354                 assertFalse(map.containsKey(keys[i]),
355                         String.format("compute: containsKey(%s[%d])", desc, i));
356                 assertFalse(map.containsValue(keys[i]),
357                         String.format("compute: containsValue(%s[%s])", desc, i));
358             } else { // odd: was removed, should now be mapped to EXTRA
359                 assertEquals(retVal, val,
360                         String.format("compute: retVal(%s[%d])", desc, i));
361                 assertEquals(val, map.get(keys[i]),
362                         String.format("compute: get(%s[%d])", desc, i));
363                 assertTrue(map.containsKey(keys[i]),
364                         String.format("compute: containsKey(%s[%d])", desc, i));
365                 expectedSize++;
366             }
367         }
368         assertTrue(map.containsValue(val),
369                 String.format("compute: containsValue(%s[%s])", desc, val));
370         assertEquals(map.size(), expectedSize,
371                 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize));
372     }
373 
374     @Test(dataProvider = "hashMapsWithObjects")
testMergeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val)375     public void testMergeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val) {
376         // remove a third of the keys
377         // call merge() for all keys[]
378         // all keys should be present: removed keys now -> EXTRA, other keys -> k-1
379         Map<IntKey, IntKey> map = ms.get();
380         IntKey[] keys = map.keySet().stream().sorted().toArray(IntKey[]::new);
381 
382         // Map to preceding key
383         BiFunction<IntKey, IntKey, IntKey> mappingFunction
384                 = (k, v) -> keys[k.getValue() - 1];
385         removeThirdKeys(map, keys);
386         for (int i = 1; i < keys.length; i++) {
387             IntKey retVal = map.merge(keys[i], val, mappingFunction);
388             if (i % 3 != 2) { // key present, should be mapped to k-1
389                 assertEquals(retVal, keys[i - 1],
390                         String.format("compute: retVal(%s[%d])", desc, i));
391                 assertEquals(keys[i - 1], map.get(keys[i]),
392                         String.format("compute: get(%s[%d])", desc, i));
393             } else { // odd: was removed, should be replaced with EXTRA
394                 assertEquals(retVal, val,
395                         String.format("compute: retVal(%s[%d])", desc, i));
396                 assertEquals(val, map.get(keys[i]),
397                         String.format("compute: get(%s[%d])", desc, i));
398             }
399             assertTrue(map.containsKey(keys[i]),
400                     String.format("compute: containsKey(%s[%d])", desc, i));
401         }
402 
403         assertEquals(map.size(), keys.length,
404                 String.format("map expected size#1 m%d != k%d", map.size(), keys.length));
405         assertTrue(map.containsValue(val),
406                 String.format("compute: containsValue(%s[%s])", desc, val));
407         assertFalse(map.containsValue(null),
408                 String.format("compute: !containsValue(%s,[null])", desc));
409     }
410 
411     @Test(dataProvider = "mapsWithObjectsAndStrings")
testMergeNull(String desc, Supplier<Map<Object, Object>> ms, Object val)412     public void testMergeNull(String desc, Supplier<Map<Object, Object>> ms, Object val) {
413         // remove a third of the keys
414         // call merge() for all keys[]
415         // result: removed keys -> EXTRA, other keys absent
416 
417         Map<Object, Object> map = ms.get();
418         Object[] keys = map.keySet().toArray();
419         BiFunction<Object, Object, Object> mappingFunction = (k, v) -> null;
420         int expectedSize = 0;
421         removeThirdKeys(map, keys);
422         for (int i = 0; i < keys.length; i++) {
423             Object retVal = map.merge(keys[i], val, mappingFunction);
424             if (i % 3 != 2) { // key present, func returned null, should be absent from map
425                 assertNull(retVal,
426                         String.format("compute: retVal(%s[%d])", desc, i));
427                 assertNull(map.get(keys[i]),
428                         String.format("compute: get(%s[%d])", desc, i));
429                 assertFalse(map.containsKey(keys[i]),
430                         String.format("compute: containsKey(%s[%d])", desc, i));
431             } else { // odd: was removed, should now be mapped to EXTRA
432                 assertEquals(retVal, val,
433                         String.format("compute: retVal(%s[%d])", desc, i));
434                 assertEquals(val, map.get(keys[i]),
435                         String.format("compute: get(%s[%d])", desc, i));
436                 assertTrue(map.containsKey(keys[i]),
437                         String.format("compute: containsKey(%s[%d])", desc, i));
438                 expectedSize++;
439             }
440             assertFalse(map.containsValue(keys[i]),
441                     String.format("compute: containsValue(%s[%s])", desc, i));
442         }
443         assertTrue(map.containsValue(val),
444                 String.format("compute: containsValue(%s[%s])", desc, val));
445         assertEquals(map.size(), expectedSize,
446                 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize));
447     }
448 
449     /*
450      * Remove half of the keys
451      */
removeOddKeys(Map<T, T> map, T[] keys)452     private static <T> void removeOddKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) {
453         int removes = 0;
454         for (int i = 0; i < keys.length; i++) {
455             if (i % 2 != 0) {
456                 map.remove(keys[i]);
457                 removes++;
458             }
459         }
460         assertEquals(map.size(), keys.length - removes,
461                 String.format("map expected size m%d != k%d", map.size(), keys.length - removes));
462     }
463 
464     /*
465      * Remove every third key
466      * This will hopefully leave some removed keys in TreeBins for, e.g., computeIfAbsent
467      * w/ a func that returns null.
468      *
469      * TODO: consider using this in other tests (and maybe adding a remapThirdKeys)
470      */
removeThirdKeys(Map<T, T> map, T[] keys)471     private static <T> void removeThirdKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) {
472         int removes = 0;
473         for (int i = 0; i < keys.length; i++) {
474             if (i % 3 == 2) {
475                 map.remove(keys[i]);
476                 removes++;
477             }
478         }
479         assertEquals(map.size(), keys.length - removes,
480                 String.format("map expected size m%d != k%d", map.size(), keys.length - removes));
481     }
482 
483     /*
484      * Re-map the odd-numbered keys to map to the EXTRA value
485      */
remapOddKeys(Map<T, T> map, T[] keys, T val)486     private static <T> void remapOddKeys(Map<T, T> map, T[] keys, T val) {
487         for (int i = 0; i < keys.length; i++) {
488             if (i % 2 != 0) {
489                 map.put(keys[i], val);
490             }
491         }
492     }
493 
494 }