1 /*
2 * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.io.*;
29 import java.lang.reflect.Array;
30 import java.util.function.BiConsumer;
31 import java.util.function.BiFunction;
32 import java.util.function.Consumer;
33
34 /**
35 * This class implements the <tt>Map</tt> interface with a hash table, using
36 * reference-equality in place of object-equality when comparing keys (and
37 * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
38 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
39 * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
40 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
41 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
42 *
43 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
44 * implementation! While this class implements the <tt>Map</tt> interface, it
45 * intentionally violates <tt>Map's</tt> general contract, which mandates the
46 * use of the <tt>equals</tt> method when comparing objects. This class is
47 * designed for use only in the rare cases wherein reference-equality
48 * semantics are required.</b>
57 * each object in the program being debugged.
58 *
59 * <p>This class provides all of the optional map operations, and permits
60 * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
61 * guarantees as to the order of the map; in particular, it does not guarantee
62 * that the order will remain constant over time.
63 *
64 * <p>This class provides constant-time performance for the basic
65 * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
66 * identity hash function ({@link System#identityHashCode(Object)})
67 * disperses elements properly among the buckets.
68 *
69 * <p>This class has one tuning parameter (which affects performance but not
70 * semantics): <i>expected maximum size</i>. This parameter is the maximum
71 * number of key-value mappings that the map is expected to hold. Internally,
72 * this parameter is used to determine the number of buckets initially
73 * comprising the hash table. The precise relationship between the expected
74 * maximum size and the number of buckets is unspecified.
75 *
76 * <p>If the size of the map (the number of key-value mappings) sufficiently
77 * exceeds the expected maximum size, the number of buckets is increased
78 * Increasing the number of buckets ("rehashing") may be fairly expensive, so
79 * it pays to create identity hash maps with a sufficiently large expected
80 * maximum size. On the other hand, iteration over collection views requires
81 * time proportional to the number of buckets in the hash table, so it
82 * pays not to set the expected maximum size too high if you are especially
83 * concerned with iteration performance or memory usage.
84 *
85 * <p><strong>Note that this implementation is not synchronized.</strong>
86 * If multiple threads access an identity hash map concurrently, and at
87 * least one of the threads modifies the map structurally, it <i>must</i>
88 * be synchronized externally. (A structural modification is any operation
89 * that adds or deletes one or more mappings; merely changing the value
90 * associated with a key that an instance already contains is not a
91 * structural modification.) This is typically accomplished by
92 * synchronizing on some object that naturally encapsulates the map.
93 *
94 * If no such object exists, the map should be "wrapped" using the
95 * {@link Collections#synchronizedMap Collections.synchronizedMap}
96 * method. This is best done at creation time, to prevent accidental
97 * unsynchronized access to the map:<pre>
143 /**
144 * The initial capacity used by the no-args constructor.
145 * MUST be a power of two. The value 32 corresponds to the
146 * (specified) expected maximum size of 21, given a load factor
147 * of 2/3.
148 */
149 private static final int DEFAULT_CAPACITY = 32;
150
151 /**
152 * The minimum capacity, used if a lower value is implicitly specified
153 * by either of the constructors with arguments. The value 4 corresponds
154 * to an expected maximum size of 2, given a load factor of 2/3.
155 * MUST be a power of two.
156 */
157 private static final int MINIMUM_CAPACITY = 4;
158
159 /**
160 * The maximum capacity, used if a higher value is implicitly specified
161 * by either of the constructors with arguments.
162 * MUST be a power of two <= 1<<29.
163 */
164 private static final int MAXIMUM_CAPACITY = 1 << 29;
165
166 /**
167 * The table, resized as necessary. Length MUST always be a power of two.
168 */
169 transient Object[] table; // non-private to simplify nested class access
170
171 /**
172 * The number of key-value mappings contained in this identity hash map.
173 *
174 * @serial
175 */
176 int size;
177
178 /**
179 * The number of modifications, to support fast-fail iterators
180 */
181 transient int modCount;
182
183 /**
184 * The next size value at which to resize (capacity * load factor).
185 */
186 private transient int threshold;
187
188 /**
189 * Value representing null keys inside tables.
190 */
191 static final Object NULL_KEY = new Object();
192
193 /**
194 * Use NULL_KEY for key if it is null.
195 */
196 private static Object maskNull(Object key) {
197 return (key == null ? NULL_KEY : key);
198 }
199
200 /**
201 * Returns internal representation of null key back to caller as null.
202 */
203 static final Object unmaskNull(Object key) {
204 return (key == NULL_KEY ? null : key);
205 }
206
207 /**
208 * Constructs a new, empty identity hash map with a default expected
212 init(DEFAULT_CAPACITY);
213 }
214
215 /**
216 * Constructs a new, empty map with the specified expected maximum size.
217 * Putting more than the expected number of key-value mappings into
218 * the map may cause the internal data structure to grow, which may be
219 * somewhat time-consuming.
220 *
221 * @param expectedMaxSize the expected maximum size of the map
222 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
223 */
224 public IdentityHashMap(int expectedMaxSize) {
225 if (expectedMaxSize < 0)
226 throw new IllegalArgumentException("expectedMaxSize is negative: "
227 + expectedMaxSize);
228 init(capacity(expectedMaxSize));
229 }
230
231 /**
232 * Returns the appropriate capacity for the specified expected maximum
233 * size. Returns the smallest power of two between MINIMUM_CAPACITY
234 * and MAXIMUM_CAPACITY, inclusive, that is greater than
235 * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
236 * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
237 * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
238 */
239 private int capacity(int expectedMaxSize) {
240 // Compute min capacity for expectedMaxSize given a load factor of 2/3
241 int minCapacity = (3 * expectedMaxSize)/2;
242
243 // Compute the appropriate capacity
244 int result;
245 if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
246 result = MAXIMUM_CAPACITY;
247 } else {
248 result = MINIMUM_CAPACITY;
249 while (result < minCapacity)
250 result <<= 1;
251 }
252 return result;
253 }
254
255 /**
256 * Initializes object to be an empty map with the specified initial
257 * capacity, which is assumed to be a power of two between
258 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
259 */
260 private void init(int initCapacity) {
261 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
262 // assert initCapacity >= MINIMUM_CAPACITY;
263 // assert initCapacity <= MAXIMUM_CAPACITY;
264
265 threshold = (initCapacity * 2)/3;
266 table = new Object[2 * initCapacity];
267 }
268
269 /**
270 * Constructs a new identity hash map containing the keys-value mappings
271 * in the specified map.
272 *
273 * @param m the map whose mappings are to be placed into this map
274 * @throws NullPointerException if the specified map is null
275 */
276 public IdentityHashMap(Map<? extends K, ? extends V> m) {
277 // Allow for a bit of growth
278 this((int) ((1 + m.size()) * 1.1));
279 putAll(m);
280 }
281
282 /**
283 * Returns the number of key-value mappings in this identity hash map.
284 *
285 * @return the number of key-value mappings in this map
412 i = nextKeyIndex(i, len);
413 }
414 }
415
416 /**
417 * Associates the specified value with the specified key in this identity
418 * hash map. If the map previously contained a mapping for the key, the
419 * old value is replaced.
420 *
421 * @param key the key with which the specified value is to be associated
422 * @param value the value to be associated with the specified key
423 * @return the previous value associated with <tt>key</tt>, or
424 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
425 * (A <tt>null</tt> return can also indicate that the map
426 * previously associated <tt>null</tt> with <tt>key</tt>.)
427 * @see Object#equals(Object)
428 * @see #get(Object)
429 * @see #containsKey(Object)
430 */
431 public V put(K key, V value) {
432 Object k = maskNull(key);
433 Object[] tab = table;
434 int len = tab.length;
435 int i = hash(k, len);
436
437 Object item;
438 while ( (item = tab[i]) != null) {
439 if (item == k) {
440 @SuppressWarnings("unchecked")
441 V oldValue = (V) tab[i + 1];
442 tab[i + 1] = value;
443 return oldValue;
444 }
445 i = nextKeyIndex(i, len);
446 }
447
448 modCount++;
449 tab[i] = k;
450 tab[i + 1] = value;
451 if (++size >= threshold)
452 resize(len); // len == 2 * current capacity.
453 return null;
454 }
455
456 /**
457 * Resize the table to hold given capacity.
458 *
459 * @param newCapacity the new capacity, must be a power of two.
460 */
461 private void resize(int newCapacity) {
462 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
463 int newLength = newCapacity * 2;
464
465 Object[] oldTable = table;
466 int oldLength = oldTable.length;
467 if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
468 if (threshold == MAXIMUM_CAPACITY-1)
469 throw new IllegalStateException("Capacity exhausted.");
470 threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
471 return;
472 }
473 if (oldLength >= newLength)
474 return;
475
476 Object[] newTable = new Object[newLength];
477 threshold = newLength / 3;
478
479 for (int j = 0; j < oldLength; j += 2) {
480 Object key = oldTable[j];
481 if (key != null) {
482 Object value = oldTable[j+1];
483 oldTable[j] = null;
484 oldTable[j+1] = null;
485 int i = hash(key, newLength);
486 while (newTable[i] != null)
487 i = nextKeyIndex(i, newLength);
488 newTable[i] = key;
489 newTable[i + 1] = value;
490 }
491 }
492 table = newTable;
493 }
494
495 /**
496 * Copies all of the mappings from the specified map to this map.
497 * These mappings will replace any mappings that this map had for
498 * any of the keys currently in the specified map.
499 *
500 * @param m mappings to be stored in this map
501 * @throws NullPointerException if the specified map is null
502 */
503 public void putAll(Map<? extends K, ? extends V> m) {
504 int n = m.size();
505 if (n == 0)
506 return;
507 if (n > threshold) // conservatively pre-expand
508 resize(capacity(n));
509
510 for (Entry<? extends K, ? extends V> e : m.entrySet())
511 put(e.getKey(), e.getValue());
512 }
513
514 /**
515 * Removes the mapping for this key from this map if present.
516 *
517 * @param key key whose mapping is to be removed from the map
518 * @return the previous value associated with <tt>key</tt>, or
519 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
520 * (A <tt>null</tt> return can also indicate that the map
521 * previously associated <tt>null</tt> with <tt>key</tt>.)
522 */
523 public V remove(Object key) {
524 Object k = maskNull(key);
525 Object[] tab = table;
526 int len = tab.length;
527 int i = hash(k, len);
528
529 while (true) {
530 Object item = tab[i];
531 if (item == k) {
532 modCount++;
533 size--;
534 @SuppressWarnings("unchecked")
535 V oldValue = (V) tab[i + 1];
536 tab[i + 1] = null;
537 tab[i] = null;
538 closeDeletion(i);
539 return oldValue;
540 }
541 if (item == null)
542 return null;
543 i = nextKeyIndex(i, len);
544 }
545
546 }
547
548 /**
549 * Removes the specified key-value mapping from the map if it is present.
550 *
551 * @param key possible key
552 * @param value possible value
553 * @return <code>true</code> if and only if the specified key-value
554 * mapping was in the map
555 */
556 private boolean removeMapping(Object key, Object value) {
557 Object k = maskNull(key);
558 Object[] tab = table;
559 int len = tab.length;
560 int i = hash(k, len);
561
562 while (true) {
563 Object item = tab[i];
564 if (item == k) {
565 if (tab[i + 1] != value)
1249 // fewer elements than expected or concurrent modification from other thread detected
1250 if (ti < size || expectedModCount != modCount) {
1251 throw new ConcurrentModificationException();
1252 }
1253 // final null marker as per spec
1254 if (ti < a.length) {
1255 a[ti] = null;
1256 }
1257 return a;
1258 }
1259
1260 public Spliterator<Map.Entry<K,V>> spliterator() {
1261 return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1262 }
1263 }
1264
1265
1266 private static final long serialVersionUID = 8188218128353913216L;
1267
1268 /**
1269 * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1270 * (i.e., serialize it).
1271 *
1272 * @serialData The <i>size</i> of the HashMap (the number of key-value
1273 * mappings) (<tt>int</tt>), followed by the key (Object) and
1274 * value (Object) for each key-value mapping represented by the
1275 * IdentityHashMap. The key-value mappings are emitted in no
1276 * particular order.
1277 */
1278 private void writeObject(java.io.ObjectOutputStream s)
1279 throws java.io.IOException {
1280 // Write out and any hidden stuff
1281 s.defaultWriteObject();
1282
1283 // Write out size (number of Mappings)
1284 s.writeInt(size);
1285
1286 // Write out keys and values (alternating)
1287 Object[] tab = table;
1288 for (int i = 0; i < tab.length; i += 2) {
1289 Object key = tab[i];
1290 if (key != null) {
1291 s.writeObject(unmaskNull(key));
1292 s.writeObject(tab[i + 1]);
1293 }
1294 }
1295 }
1296
1297 /**
1298 * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1299 * deserialize it).
1300 */
1301 private void readObject(java.io.ObjectInputStream s)
1302 throws java.io.IOException, ClassNotFoundException {
1303 // Read in any hidden stuff
1304 s.defaultReadObject();
1305
1306 // Read in size (number of Mappings)
1307 int size = s.readInt();
1308
1309 // Allow for 33% growth (i.e., capacity is >= 2* size()).
1310 init(capacity((size*4)/3));
1311
1312 // Read the keys and values, and put the mappings in the table
1313 for (int i=0; i<size; i++) {
1314 @SuppressWarnings("unchecked")
1315 K key = (K) s.readObject();
1316 @SuppressWarnings("unchecked")
1317 V value = (V) s.readObject();
1318 putForCreate(key, value);
1319 }
1320 }
1321
1322 /**
1323 * The put method for readObject. It does not resize the table,
1324 * update modCount, etc.
1325 */
1326 private void putForCreate(K key, V value)
1327 throws IOException
1328 {
1329 Object k = maskNull(key);
1330 Object[] tab = table;
1331 int len = tab.length;
1332 int i = hash(k, len);
1333
1334 Object item;
1335 while ( (item = tab[i]) != null) {
1336 if (item == k)
1337 throw new java.io.StreamCorruptedException();
1338 i = nextKeyIndex(i, len);
1339 }
1340 tab[i] = k;
1341 tab[i + 1] = value;
1342 }
1343
1344 @SuppressWarnings("unchecked")
1345 @Override
1346 public void forEach(BiConsumer<? super K, ? super V> action) {
1347 Objects.requireNonNull(action);
|
1 /*
2 * Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.lang.reflect.Array;
29 import java.util.function.BiConsumer;
30 import java.util.function.BiFunction;
31 import java.util.function.Consumer;
32
33 /**
34 * This class implements the <tt>Map</tt> interface with a hash table, using
35 * reference-equality in place of object-equality when comparing keys (and
36 * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
37 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
38 * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
39 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
40 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
41 *
42 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
43 * implementation! While this class implements the <tt>Map</tt> interface, it
44 * intentionally violates <tt>Map's</tt> general contract, which mandates the
45 * use of the <tt>equals</tt> method when comparing objects. This class is
46 * designed for use only in the rare cases wherein reference-equality
47 * semantics are required.</b>
56 * each object in the program being debugged.
57 *
58 * <p>This class provides all of the optional map operations, and permits
59 * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
60 * guarantees as to the order of the map; in particular, it does not guarantee
61 * that the order will remain constant over time.
62 *
63 * <p>This class provides constant-time performance for the basic
64 * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
65 * identity hash function ({@link System#identityHashCode(Object)})
66 * disperses elements properly among the buckets.
67 *
68 * <p>This class has one tuning parameter (which affects performance but not
69 * semantics): <i>expected maximum size</i>. This parameter is the maximum
70 * number of key-value mappings that the map is expected to hold. Internally,
71 * this parameter is used to determine the number of buckets initially
72 * comprising the hash table. The precise relationship between the expected
73 * maximum size and the number of buckets is unspecified.
74 *
75 * <p>If the size of the map (the number of key-value mappings) sufficiently
76 * exceeds the expected maximum size, the number of buckets is increased.
77 * Increasing the number of buckets ("rehashing") may be fairly expensive, so
78 * it pays to create identity hash maps with a sufficiently large expected
79 * maximum size. On the other hand, iteration over collection views requires
80 * time proportional to the number of buckets in the hash table, so it
81 * pays not to set the expected maximum size too high if you are especially
82 * concerned with iteration performance or memory usage.
83 *
84 * <p><strong>Note that this implementation is not synchronized.</strong>
85 * If multiple threads access an identity hash map concurrently, and at
86 * least one of the threads modifies the map structurally, it <i>must</i>
87 * be synchronized externally. (A structural modification is any operation
88 * that adds or deletes one or more mappings; merely changing the value
89 * associated with a key that an instance already contains is not a
90 * structural modification.) This is typically accomplished by
91 * synchronizing on some object that naturally encapsulates the map.
92 *
93 * If no such object exists, the map should be "wrapped" using the
94 * {@link Collections#synchronizedMap Collections.synchronizedMap}
95 * method. This is best done at creation time, to prevent accidental
96 * unsynchronized access to the map:<pre>
142 /**
143 * The initial capacity used by the no-args constructor.
144 * MUST be a power of two. The value 32 corresponds to the
145 * (specified) expected maximum size of 21, given a load factor
146 * of 2/3.
147 */
148 private static final int DEFAULT_CAPACITY = 32;
149
150 /**
151 * The minimum capacity, used if a lower value is implicitly specified
152 * by either of the constructors with arguments. The value 4 corresponds
153 * to an expected maximum size of 2, given a load factor of 2/3.
154 * MUST be a power of two.
155 */
156 private static final int MINIMUM_CAPACITY = 4;
157
158 /**
159 * The maximum capacity, used if a higher value is implicitly specified
160 * by either of the constructors with arguments.
161 * MUST be a power of two <= 1<<29.
162 *
163 * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
164 * because it has to have at least one slot with the key == null
165 * in order to avoid infinite loops in get(), put(), remove()
166 */
167 private static final int MAXIMUM_CAPACITY = 1 << 29;
168
169 /**
170 * The table, resized as necessary. Length MUST always be a power of two.
171 */
172 transient Object[] table; // non-private to simplify nested class access
173
174 /**
175 * The number of key-value mappings contained in this identity hash map.
176 *
177 * @serial
178 */
179 int size;
180
181 /**
182 * The number of modifications, to support fast-fail iterators
183 */
184 transient int modCount;
185
186 /**
187 * Value representing null keys inside tables.
188 */
189 static final Object NULL_KEY = new Object();
190
191 /**
192 * Use NULL_KEY for key if it is null.
193 */
194 private static Object maskNull(Object key) {
195 return (key == null ? NULL_KEY : key);
196 }
197
198 /**
199 * Returns internal representation of null key back to caller as null.
200 */
201 static final Object unmaskNull(Object key) {
202 return (key == NULL_KEY ? null : key);
203 }
204
205 /**
206 * Constructs a new, empty identity hash map with a default expected
210 init(DEFAULT_CAPACITY);
211 }
212
213 /**
214 * Constructs a new, empty map with the specified expected maximum size.
215 * Putting more than the expected number of key-value mappings into
216 * the map may cause the internal data structure to grow, which may be
217 * somewhat time-consuming.
218 *
219 * @param expectedMaxSize the expected maximum size of the map
220 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
221 */
222 public IdentityHashMap(int expectedMaxSize) {
223 if (expectedMaxSize < 0)
224 throw new IllegalArgumentException("expectedMaxSize is negative: "
225 + expectedMaxSize);
226 init(capacity(expectedMaxSize));
227 }
228
229 /**
230 * Returns the appropriate capacity for the given expected maximum size.
231 * Returns the smallest power of two between MINIMUM_CAPACITY and
232 * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
233 * expectedMaxSize)/2, if such a number exists. Otherwise returns
234 * MAXIMUM_CAPACITY.
235 */
236 private static int capacity(int expectedMaxSize) {
237 // assert expectedMaxSize >= 0;
238 return
239 (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
240 (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
241 Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
242 }
243
244 /**
245 * Initializes object to be an empty map with the specified initial
246 * capacity, which is assumed to be a power of two between
247 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
248 */
249 private void init(int initCapacity) {
250 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
251 // assert initCapacity >= MINIMUM_CAPACITY;
252 // assert initCapacity <= MAXIMUM_CAPACITY;
253
254 table = new Object[2 * initCapacity];
255 }
256
257 /**
258 * Constructs a new identity hash map containing the keys-value mappings
259 * in the specified map.
260 *
261 * @param m the map whose mappings are to be placed into this map
262 * @throws NullPointerException if the specified map is null
263 */
264 public IdentityHashMap(Map<? extends K, ? extends V> m) {
265 // Allow for a bit of growth
266 this((int) ((1 + m.size()) * 1.1));
267 putAll(m);
268 }
269
270 /**
271 * Returns the number of key-value mappings in this identity hash map.
272 *
273 * @return the number of key-value mappings in this map
400 i = nextKeyIndex(i, len);
401 }
402 }
403
404 /**
405 * Associates the specified value with the specified key in this identity
406 * hash map. If the map previously contained a mapping for the key, the
407 * old value is replaced.
408 *
409 * @param key the key with which the specified value is to be associated
410 * @param value the value to be associated with the specified key
411 * @return the previous value associated with <tt>key</tt>, or
412 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
413 * (A <tt>null</tt> return can also indicate that the map
414 * previously associated <tt>null</tt> with <tt>key</tt>.)
415 * @see Object#equals(Object)
416 * @see #get(Object)
417 * @see #containsKey(Object)
418 */
419 public V put(K key, V value) {
420 final Object k = maskNull(key);
421
422 retryAfterResize: for (;;) {
423 final Object[] tab = table;
424 final int len = tab.length;
425 int i = hash(k, len);
426
427 for (Object item; (item = tab[i]) != null;
428 i = nextKeyIndex(i, len)) {
429 if (item == k) {
430 @SuppressWarnings("unchecked")
431 V oldValue = (V) tab[i + 1];
432 tab[i + 1] = value;
433 return oldValue;
434 }
435 }
436
437 final int s = size + 1;
438 // Use optimized form of 3 * s.
439 // Next capacity is len, 2 * current capacity.
440 if (s + (s << 1) > len && resize(len))
441 continue retryAfterResize;
442
443 modCount++;
444 tab[i] = k;
445 tab[i + 1] = value;
446 size = s;
447 return null;
448 }
449 }
450
451 /**
452 * Resizes the table if necessary to hold given capacity.
453 *
454 * @param newCapacity the new capacity, must be a power of two.
455 * @return whether a resize did in fact take place
456 */
457 private boolean resize(int newCapacity) {
458 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
459 int newLength = newCapacity * 2;
460
461 Object[] oldTable = table;
462 int oldLength = oldTable.length;
463 if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
464 if (size == MAXIMUM_CAPACITY - 1)
465 throw new IllegalStateException("Capacity exhausted.");
466 return false;
467 }
468 if (oldLength >= newLength)
469 return false;
470
471 Object[] newTable = new Object[newLength];
472
473 for (int j = 0; j < oldLength; j += 2) {
474 Object key = oldTable[j];
475 if (key != null) {
476 Object value = oldTable[j+1];
477 oldTable[j] = null;
478 oldTable[j+1] = null;
479 int i = hash(key, newLength);
480 while (newTable[i] != null)
481 i = nextKeyIndex(i, newLength);
482 newTable[i] = key;
483 newTable[i + 1] = value;
484 }
485 }
486 table = newTable;
487 return true;
488 }
489
490 /**
491 * Copies all of the mappings from the specified map to this map.
492 * These mappings will replace any mappings that this map had for
493 * any of the keys currently in the specified map.
494 *
495 * @param m mappings to be stored in this map
496 * @throws NullPointerException if the specified map is null
497 */
498 public void putAll(Map<? extends K, ? extends V> m) {
499 int n = m.size();
500 if (n == 0)
501 return;
502 if (n > size)
503 resize(capacity(n)); // conservatively pre-expand
504
505 for (Entry<? extends K, ? extends V> e : m.entrySet())
506 put(e.getKey(), e.getValue());
507 }
508
509 /**
510 * Removes the mapping for this key from this map if present.
511 *
512 * @param key key whose mapping is to be removed from the map
513 * @return the previous value associated with <tt>key</tt>, or
514 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
515 * (A <tt>null</tt> return can also indicate that the map
516 * previously associated <tt>null</tt> with <tt>key</tt>.)
517 */
518 public V remove(Object key) {
519 Object k = maskNull(key);
520 Object[] tab = table;
521 int len = tab.length;
522 int i = hash(k, len);
523
524 while (true) {
525 Object item = tab[i];
526 if (item == k) {
527 modCount++;
528 size--;
529 @SuppressWarnings("unchecked")
530 V oldValue = (V) tab[i + 1];
531 tab[i + 1] = null;
532 tab[i] = null;
533 closeDeletion(i);
534 return oldValue;
535 }
536 if (item == null)
537 return null;
538 i = nextKeyIndex(i, len);
539 }
540 }
541
542 /**
543 * Removes the specified key-value mapping from the map if it is present.
544 *
545 * @param key possible key
546 * @param value possible value
547 * @return <code>true</code> if and only if the specified key-value
548 * mapping was in the map
549 */
550 private boolean removeMapping(Object key, Object value) {
551 Object k = maskNull(key);
552 Object[] tab = table;
553 int len = tab.length;
554 int i = hash(k, len);
555
556 while (true) {
557 Object item = tab[i];
558 if (item == k) {
559 if (tab[i + 1] != value)
1243 // fewer elements than expected or concurrent modification from other thread detected
1244 if (ti < size || expectedModCount != modCount) {
1245 throw new ConcurrentModificationException();
1246 }
1247 // final null marker as per spec
1248 if (ti < a.length) {
1249 a[ti] = null;
1250 }
1251 return a;
1252 }
1253
1254 public Spliterator<Map.Entry<K,V>> spliterator() {
1255 return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1256 }
1257 }
1258
1259
1260 private static final long serialVersionUID = 8188218128353913216L;
1261
1262 /**
1263 * Saves the state of the <tt>IdentityHashMap</tt> instance to a stream
1264 * (i.e., serializes it).
1265 *
1266 * @serialData The <i>size</i> of the HashMap (the number of key-value
1267 * mappings) (<tt>int</tt>), followed by the key (Object) and
1268 * value (Object) for each key-value mapping represented by the
1269 * IdentityHashMap. The key-value mappings are emitted in no
1270 * particular order.
1271 */
1272 private void writeObject(java.io.ObjectOutputStream s)
1273 throws java.io.IOException {
1274 // Write out and any hidden stuff
1275 s.defaultWriteObject();
1276
1277 // Write out size (number of Mappings)
1278 s.writeInt(size);
1279
1280 // Write out keys and values (alternating)
1281 Object[] tab = table;
1282 for (int i = 0; i < tab.length; i += 2) {
1283 Object key = tab[i];
1284 if (key != null) {
1285 s.writeObject(unmaskNull(key));
1286 s.writeObject(tab[i + 1]);
1287 }
1288 }
1289 }
1290
1291 /**
1292 * Reconstitutes the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1293 * deserializes it).
1294 */
1295 private void readObject(java.io.ObjectInputStream s)
1296 throws java.io.IOException, ClassNotFoundException {
1297 // Read in any hidden stuff
1298 s.defaultReadObject();
1299
1300 // Read in size (number of Mappings)
1301 int size = s.readInt();
1302 if (size < 0)
1303 throw new java.io.StreamCorruptedException
1304 ("Illegal mappings count: " + size);
1305 init(capacity(size));
1306
1307 // Read the keys and values, and put the mappings in the table
1308 for (int i=0; i<size; i++) {
1309 @SuppressWarnings("unchecked")
1310 K key = (K) s.readObject();
1311 @SuppressWarnings("unchecked")
1312 V value = (V) s.readObject();
1313 putForCreate(key, value);
1314 }
1315 }
1316
1317 /**
1318 * The put method for readObject. It does not resize the table,
1319 * update modCount, etc.
1320 */
1321 private void putForCreate(K key, V value)
1322 throws java.io.StreamCorruptedException
1323 {
1324 Object k = maskNull(key);
1325 Object[] tab = table;
1326 int len = tab.length;
1327 int i = hash(k, len);
1328
1329 Object item;
1330 while ( (item = tab[i]) != null) {
1331 if (item == k)
1332 throw new java.io.StreamCorruptedException();
1333 i = nextKeyIndex(i, len);
1334 }
1335 tab[i] = k;
1336 tab[i + 1] = value;
1337 }
1338
1339 @SuppressWarnings("unchecked")
1340 @Override
1341 public void forEach(BiConsumer<? super K, ? super V> action) {
1342 Objects.requireNonNull(action);
|