Print this page
| Split |
Close |
| Expand all |
| Collapse all |
--- old/src/share/classes/java/util/IdentityHashMap.java
+++ new/src/share/classes/java/util/IdentityHashMap.java
1 1 /*
2 2 * Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
3 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 4 *
5 5 * This code is free software; you can redistribute it and/or modify it
6 6 * under the terms of the GNU General Public License version 2 only, as
7 7 * published by the Free Software Foundation. Oracle designates this
8 8 * particular file as subject to the "Classpath" exception as provided
9 9 * by Oracle in the LICENSE file that accompanied this code.
10 10 *
11 11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 14 * version 2 for more details (a copy is included in the LICENSE file that
15 15 * accompanied this code).
16 16 *
17 17 * You should have received a copy of the GNU General Public License version
18 18 * 2 along with this work; if not, write to the Free Software Foundation,
19 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 20 *
21 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 22 * or visit www.oracle.com if you need additional information or have any
23 23 * questions.
24 24 */
25 25
26 26 package java.util;
27 27 import java.io.*;
28 28
29 29 /**
30 30 * This class implements the <tt>Map</tt> interface with a hash table, using
31 31 * reference-equality in place of object-equality when comparing keys (and
32 32 * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
33 33 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
34 34 * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
35 35 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
36 36 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
37 37 *
38 38 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
39 39 * implementation! While this class implements the <tt>Map</tt> interface, it
40 40 * intentionally violates <tt>Map's</tt> general contract, which mandates the
41 41 * use of the <tt>equals</tt> method when comparing objects. This class is
42 42 * designed for use only in the rare cases wherein reference-equality
43 43 * semantics are required.</b>
44 44 *
45 45 * <p>A typical use of this class is <i>topology-preserving object graph
46 46 * transformations</i>, such as serialization or deep-copying. To perform such
47 47 * a transformation, a program must maintain a "node table" that keeps track
48 48 * of all the object references that have already been processed. The node
49 49 * table must not equate distinct objects even if they happen to be equal.
50 50 * Another typical use of this class is to maintain <i>proxy objects</i>. For
51 51 * example, a debugging facility might wish to maintain a proxy object for
52 52 * each object in the program being debugged.
53 53 *
54 54 * <p>This class provides all of the optional map operations, and permits
55 55 * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
56 56 * guarantees as to the order of the map; in particular, it does not guarantee
57 57 * that the order will remain constant over time.
58 58 *
59 59 * <p>This class provides constant-time performance for the basic
60 60 * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
61 61 * identity hash function ({@link System#identityHashCode(Object)})
62 62 * disperses elements properly among the buckets.
63 63 *
64 64 * <p>This class has one tuning parameter (which affects performance but not
65 65 * semantics): <i>expected maximum size</i>. This parameter is the maximum
66 66 * number of key-value mappings that the map is expected to hold. Internally,
67 67 * this parameter is used to determine the number of buckets initially
68 68 * comprising the hash table. The precise relationship between the expected
69 69 * maximum size and the number of buckets is unspecified.
70 70 *
71 71 * <p>If the size of the map (the number of key-value mappings) sufficiently
72 72 * exceeds the expected maximum size, the number of buckets is increased
73 73 * Increasing the number of buckets ("rehashing") may be fairly expensive, so
74 74 * it pays to create identity hash maps with a sufficiently large expected
75 75 * maximum size. On the other hand, iteration over collection views requires
76 76 * time proportional to the number of buckets in the hash table, so it
77 77 * pays not to set the expected maximum size too high if you are especially
78 78 * concerned with iteration performance or memory usage.
79 79 *
80 80 * <p><strong>Note that this implementation is not synchronized.</strong>
81 81 * If multiple threads access an identity hash map concurrently, and at
82 82 * least one of the threads modifies the map structurally, it <i>must</i>
83 83 * be synchronized externally. (A structural modification is any operation
84 84 * that adds or deletes one or more mappings; merely changing the value
85 85 * associated with a key that an instance already contains is not a
86 86 * structural modification.) This is typically accomplished by
87 87 * synchronizing on some object that naturally encapsulates the map.
88 88 *
89 89 * If no such object exists, the map should be "wrapped" using the
90 90 * {@link Collections#synchronizedMap Collections.synchronizedMap}
91 91 * method. This is best done at creation time, to prevent accidental
92 92 * unsynchronized access to the map:<pre>
93 93 * Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
94 94 *
95 95 * <p>The iterators returned by the <tt>iterator</tt> method of the
96 96 * collections returned by all of this class's "collection view
97 97 * methods" are <i>fail-fast</i>: if the map is structurally modified
98 98 * at any time after the iterator is created, in any way except
99 99 * through the iterator's own <tt>remove</tt> method, the iterator
100 100 * will throw a {@link ConcurrentModificationException}. Thus, in the
101 101 * face of concurrent modification, the iterator fails quickly and
102 102 * cleanly, rather than risking arbitrary, non-deterministic behavior
103 103 * at an undetermined time in the future.
104 104 *
105 105 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
106 106 * as it is, generally speaking, impossible to make any hard guarantees in the
107 107 * presence of unsynchronized concurrent modification. Fail-fast iterators
108 108 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
109 109 * Therefore, it would be wrong to write a program that depended on this
110 110 * exception for its correctness: <i>fail-fast iterators should be used only
111 111 * to detect bugs.</i>
112 112 *
113 113 * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
114 114 * as described for example in texts by Sedgewick and Knuth. The array
115 115 * alternates holding keys and values. (This has better locality for large
116 116 * tables than does using separate arrays.) For many JRE implementations
117 117 * and operation mixes, this class will yield better performance than
118 118 * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
119 119 *
120 120 * <p>This class is a member of the
121 121 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
122 122 * Java Collections Framework</a>.
123 123 *
124 124 * @see System#identityHashCode(Object)
125 125 * @see Object#hashCode()
126 126 * @see Collection
127 127 * @see Map
128 128 * @see HashMap
129 129 * @see TreeMap
130 130 * @author Doug Lea and Josh Bloch
131 131 * @since 1.4
132 132 */
133 133
134 134 public class IdentityHashMap<K,V>
135 135 extends AbstractMap<K,V>
136 136 implements Map<K,V>, java.io.Serializable, Cloneable
137 137 {
138 138 /**
139 139 * The initial capacity used by the no-args constructor.
140 140 * MUST be a power of two. The value 32 corresponds to the
141 141 * (specified) expected maximum size of 21, given a load factor
142 142 * of 2/3.
143 143 */
144 144 private static final int DEFAULT_CAPACITY = 32;
145 145
146 146 /**
147 147 * The minimum capacity, used if a lower value is implicitly specified
148 148 * by either of the constructors with arguments. The value 4 corresponds
149 149 * to an expected maximum size of 2, given a load factor of 2/3.
150 150 * MUST be a power of two.
151 151 */
152 152 private static final int MINIMUM_CAPACITY = 4;
153 153
154 154 /**
155 155 * The maximum capacity, used if a higher value is implicitly specified
156 156 * by either of the constructors with arguments.
157 157 * MUST be a power of two <= 1<<29.
158 158 */
159 159 private static final int MAXIMUM_CAPACITY = 1 << 29;
160 160
161 161 /**
162 162 * The table, resized as necessary. Length MUST always be a power of two.
163 163 */
164 164 private transient Object[] table;
165 165
166 166 /**
167 167 * The number of key-value mappings contained in this identity hash map.
168 168 *
169 169 * @serial
170 170 */
171 171 private int size;
172 172
173 173 /**
174 174 * The number of modifications, to support fast-fail iterators
175 175 */
176 176 private transient int modCount;
177 177
178 178 /**
179 179 * The next size value at which to resize (capacity * load factor).
180 180 */
181 181 private transient int threshold;
182 182
183 183 /**
184 184 * Value representing null keys inside tables.
185 185 */
186 186 private static final Object NULL_KEY = new Object();
187 187
188 188 /**
189 189 * Use NULL_KEY for key if it is null.
190 190 */
191 191 private static Object maskNull(Object key) {
192 192 return (key == null ? NULL_KEY : key);
193 193 }
194 194
195 195 /**
196 196 * Returns internal representation of null key back to caller as null.
197 197 */
198 198 private static Object unmaskNull(Object key) {
199 199 return (key == NULL_KEY ? null : key);
200 200 }
201 201
202 202 /**
203 203 * Constructs a new, empty identity hash map with a default expected
204 204 * maximum size (21).
205 205 */
206 206 public IdentityHashMap() {
207 207 init(DEFAULT_CAPACITY);
208 208 }
209 209
210 210 /**
211 211 * Constructs a new, empty map with the specified expected maximum size.
212 212 * Putting more than the expected number of key-value mappings into
213 213 * the map may cause the internal data structure to grow, which may be
214 214 * somewhat time-consuming.
215 215 *
216 216 * @param expectedMaxSize the expected maximum size of the map
217 217 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
218 218 */
219 219 public IdentityHashMap(int expectedMaxSize) {
220 220 if (expectedMaxSize < 0)
221 221 throw new IllegalArgumentException("expectedMaxSize is negative: "
222 222 + expectedMaxSize);
223 223 init(capacity(expectedMaxSize));
224 224 }
225 225
226 226 /**
227 227 * Returns the appropriate capacity for the specified expected maximum
228 228 * size. Returns the smallest power of two between MINIMUM_CAPACITY
229 229 * and MAXIMUM_CAPACITY, inclusive, that is greater than
230 230 * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
231 231 * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
232 232 * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
233 233 */
234 234 private int capacity(int expectedMaxSize) {
235 235 // Compute min capacity for expectedMaxSize given a load factor of 2/3
236 236 int minCapacity = (3 * expectedMaxSize)/2;
237 237
238 238 // Compute the appropriate capacity
239 239 int result;
240 240 if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
241 241 result = MAXIMUM_CAPACITY;
242 242 } else {
243 243 result = MINIMUM_CAPACITY;
244 244 while (result < minCapacity)
245 245 result <<= 1;
246 246 }
247 247 return result;
248 248 }
249 249
250 250 /**
251 251 * Initializes object to be an empty map with the specified initial
252 252 * capacity, which is assumed to be a power of two between
253 253 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
254 254 */
255 255 private void init(int initCapacity) {
256 256 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
257 257 // assert initCapacity >= MINIMUM_CAPACITY;
258 258 // assert initCapacity <= MAXIMUM_CAPACITY;
259 259
260 260 threshold = (initCapacity * 2)/3;
261 261 table = new Object[2 * initCapacity];
262 262 }
263 263
264 264 /**
265 265 * Constructs a new identity hash map containing the keys-value mappings
266 266 * in the specified map.
267 267 *
268 268 * @param m the map whose mappings are to be placed into this map
269 269 * @throws NullPointerException if the specified map is null
270 270 */
271 271 public IdentityHashMap(Map<? extends K, ? extends V> m) {
272 272 // Allow for a bit of growth
273 273 this((int) ((1 + m.size()) * 1.1));
274 274 putAll(m);
275 275 }
276 276
277 277 /**
278 278 * Returns the number of key-value mappings in this identity hash map.
279 279 *
280 280 * @return the number of key-value mappings in this map
281 281 */
282 282 public int size() {
283 283 return size;
284 284 }
285 285
286 286 /**
287 287 * Returns <tt>true</tt> if this identity hash map contains no key-value
288 288 * mappings.
289 289 *
290 290 * @return <tt>true</tt> if this identity hash map contains no key-value
291 291 * mappings
292 292 */
293 293 public boolean isEmpty() {
294 294 return size == 0;
295 295 }
296 296
297 297 /**
298 298 * Returns index for Object x.
299 299 */
300 300 private static int hash(Object x, int length) {
301 301 int h = System.identityHashCode(x);
302 302 // Multiply by -127, and left-shift to use least bit as part of hash
303 303 return ((h << 1) - (h << 8)) & (length - 1);
304 304 }
305 305
306 306 /**
307 307 * Circularly traverses table of size len.
308 308 */
309 309 private static int nextKeyIndex(int i, int len) {
310 310 return (i + 2 < len ? i + 2 : 0);
311 311 }
312 312
313 313 /**
314 314 * Returns the value to which the specified key is mapped,
315 315 * or {@code null} if this map contains no mapping for the key.
316 316 *
317 317 * <p>More formally, if this map contains a mapping from a key
318 318 * {@code k} to a value {@code v} such that {@code (key == k)},
319 319 * then this method returns {@code v}; otherwise it returns
|
↓ open down ↓ |
319 lines elided |
↑ open up ↑ |
320 320 * {@code null}. (There can be at most one such mapping.)
321 321 *
322 322 * <p>A return value of {@code null} does not <i>necessarily</i>
323 323 * indicate that the map contains no mapping for the key; it's also
324 324 * possible that the map explicitly maps the key to {@code null}.
325 325 * The {@link #containsKey containsKey} operation may be used to
326 326 * distinguish these two cases.
327 327 *
328 328 * @see #put(Object, Object)
329 329 */
330 + @SuppressWarnings("unchecked")
330 331 public V get(Object key) {
331 332 Object k = maskNull(key);
332 333 Object[] tab = table;
333 334 int len = tab.length;
334 335 int i = hash(k, len);
335 336 while (true) {
336 337 Object item = tab[i];
337 338 if (item == k)
338 339 return (V) tab[i + 1];
339 340 if (item == null)
340 341 return null;
341 342 i = nextKeyIndex(i, len);
342 343 }
343 344 }
344 345
345 346 /**
346 347 * Tests whether the specified object reference is a key in this identity
347 348 * hash map.
348 349 *
349 350 * @param key possible key
350 351 * @return <code>true</code> if the specified object reference is a key
351 352 * in this map
352 353 * @see #containsValue(Object)
353 354 */
354 355 public boolean containsKey(Object key) {
355 356 Object k = maskNull(key);
356 357 Object[] tab = table;
357 358 int len = tab.length;
358 359 int i = hash(k, len);
359 360 while (true) {
360 361 Object item = tab[i];
361 362 if (item == k)
362 363 return true;
363 364 if (item == null)
364 365 return false;
365 366 i = nextKeyIndex(i, len);
366 367 }
367 368 }
368 369
369 370 /**
370 371 * Tests whether the specified object reference is a value in this identity
371 372 * hash map.
372 373 *
373 374 * @param value value whose presence in this map is to be tested
374 375 * @return <tt>true</tt> if this map maps one or more keys to the
375 376 * specified object reference
376 377 * @see #containsKey(Object)
377 378 */
378 379 public boolean containsValue(Object value) {
379 380 Object[] tab = table;
380 381 for (int i = 1; i < tab.length; i += 2)
381 382 if (tab[i] == value && tab[i - 1] != null)
382 383 return true;
383 384
384 385 return false;
385 386 }
386 387
387 388 /**
388 389 * Tests if the specified key-value mapping is in the map.
389 390 *
390 391 * @param key possible key
391 392 * @param value possible value
392 393 * @return <code>true</code> if and only if the specified key-value
393 394 * mapping is in the map
394 395 */
395 396 private boolean containsMapping(Object key, Object value) {
396 397 Object k = maskNull(key);
397 398 Object[] tab = table;
398 399 int len = tab.length;
399 400 int i = hash(k, len);
400 401 while (true) {
401 402 Object item = tab[i];
402 403 if (item == k)
403 404 return tab[i + 1] == value;
404 405 if (item == null)
405 406 return false;
406 407 i = nextKeyIndex(i, len);
407 408 }
408 409 }
409 410
410 411 /**
411 412 * Associates the specified value with the specified key in this identity
412 413 * hash map. If the map previously contained a mapping for the key, the
413 414 * old value is replaced.
414 415 *
415 416 * @param key the key with which the specified value is to be associated
416 417 * @param value the value to be associated with the specified key
417 418 * @return the previous value associated with <tt>key</tt>, or
418 419 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
419 420 * (A <tt>null</tt> return can also indicate that the map
420 421 * previously associated <tt>null</tt> with <tt>key</tt>.)
421 422 * @see Object#equals(Object)
422 423 * @see #get(Object)
423 424 * @see #containsKey(Object)
|
↓ open down ↓ |
84 lines elided |
↑ open up ↑ |
424 425 */
425 426 public V put(K key, V value) {
426 427 Object k = maskNull(key);
427 428 Object[] tab = table;
428 429 int len = tab.length;
429 430 int i = hash(k, len);
430 431
431 432 Object item;
432 433 while ( (item = tab[i]) != null) {
433 434 if (item == k) {
434 - V oldValue = (V) tab[i + 1];
435 + @SuppressWarnings("unchecked")
436 + V oldValue = (V) tab[i + 1];
435 437 tab[i + 1] = value;
436 438 return oldValue;
437 439 }
438 440 i = nextKeyIndex(i, len);
439 441 }
440 442
441 443 modCount++;
442 444 tab[i] = k;
443 445 tab[i + 1] = value;
444 446 if (++size >= threshold)
445 447 resize(len); // len == 2 * current capacity.
446 448 return null;
447 449 }
448 450
449 451 /**
450 452 * Resize the table to hold given capacity.
451 453 *
452 454 * @param newCapacity the new capacity, must be a power of two.
453 455 */
454 456 private void resize(int newCapacity) {
455 457 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
456 458 int newLength = newCapacity * 2;
457 459
458 460 Object[] oldTable = table;
459 461 int oldLength = oldTable.length;
460 462 if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
461 463 if (threshold == MAXIMUM_CAPACITY-1)
462 464 throw new IllegalStateException("Capacity exhausted.");
463 465 threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
464 466 return;
465 467 }
466 468 if (oldLength >= newLength)
467 469 return;
468 470
469 471 Object[] newTable = new Object[newLength];
470 472 threshold = newLength / 3;
471 473
472 474 for (int j = 0; j < oldLength; j += 2) {
473 475 Object key = oldTable[j];
474 476 if (key != null) {
475 477 Object value = oldTable[j+1];
476 478 oldTable[j] = null;
477 479 oldTable[j+1] = null;
478 480 int i = hash(key, newLength);
479 481 while (newTable[i] != null)
480 482 i = nextKeyIndex(i, newLength);
481 483 newTable[i] = key;
482 484 newTable[i + 1] = value;
483 485 }
484 486 }
485 487 table = newTable;
486 488 }
487 489
488 490 /**
489 491 * Copies all of the mappings from the specified map to this map.
490 492 * These mappings will replace any mappings that this map had for
491 493 * any of the keys currently in the specified map.
492 494 *
493 495 * @param m mappings to be stored in this map
494 496 * @throws NullPointerException if the specified map is null
495 497 */
496 498 public void putAll(Map<? extends K, ? extends V> m) {
497 499 int n = m.size();
498 500 if (n == 0)
499 501 return;
500 502 if (n > threshold) // conservatively pre-expand
501 503 resize(capacity(n));
502 504
503 505 for (Entry<? extends K, ? extends V> e : m.entrySet())
504 506 put(e.getKey(), e.getValue());
505 507 }
506 508
507 509 /**
508 510 * Removes the mapping for this key from this map if present.
509 511 *
510 512 * @param key key whose mapping is to be removed from the map
511 513 * @return the previous value associated with <tt>key</tt>, or
512 514 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
513 515 * (A <tt>null</tt> return can also indicate that the map
514 516 * previously associated <tt>null</tt> with <tt>key</tt>.)
515 517 */
516 518 public V remove(Object key) {
|
↓ open down ↓ |
72 lines elided |
↑ open up ↑ |
517 519 Object k = maskNull(key);
518 520 Object[] tab = table;
519 521 int len = tab.length;
520 522 int i = hash(k, len);
521 523
522 524 while (true) {
523 525 Object item = tab[i];
524 526 if (item == k) {
525 527 modCount++;
526 528 size--;
527 - V oldValue = (V) tab[i + 1];
529 + @SuppressWarnings("unchecked")
530 + V oldValue = (V) tab[i + 1];
528 531 tab[i + 1] = null;
529 532 tab[i] = null;
530 533 closeDeletion(i);
531 534 return oldValue;
532 535 }
533 536 if (item == null)
534 537 return null;
535 538 i = nextKeyIndex(i, len);
536 539 }
537 540
538 541 }
539 542
540 543 /**
541 544 * Removes the specified key-value mapping from the map if it is present.
542 545 *
543 546 * @param key possible key
544 547 * @param value possible value
545 548 * @return <code>true</code> if and only if the specified key-value
546 549 * mapping was in the map
547 550 */
548 551 private boolean removeMapping(Object key, Object value) {
549 552 Object k = maskNull(key);
550 553 Object[] tab = table;
551 554 int len = tab.length;
552 555 int i = hash(k, len);
553 556
554 557 while (true) {
555 558 Object item = tab[i];
556 559 if (item == k) {
557 560 if (tab[i + 1] != value)
558 561 return false;
559 562 modCount++;
560 563 size--;
561 564 tab[i] = null;
562 565 tab[i + 1] = null;
563 566 closeDeletion(i);
564 567 return true;
565 568 }
566 569 if (item == null)
567 570 return false;
568 571 i = nextKeyIndex(i, len);
569 572 }
570 573 }
571 574
572 575 /**
573 576 * Rehash all possibly-colliding entries following a
574 577 * deletion. This preserves the linear-probe
575 578 * collision properties required by get, put, etc.
576 579 *
577 580 * @param d the index of a newly empty deleted slot
578 581 */
579 582 private void closeDeletion(int d) {
580 583 // Adapted from Knuth Section 6.4 Algorithm R
581 584 Object[] tab = table;
582 585 int len = tab.length;
583 586
584 587 // Look for items to swap into newly vacated slot
585 588 // starting at index immediately following deletion,
586 589 // and continuing until a null slot is seen, indicating
587 590 // the end of a run of possibly-colliding keys.
588 591 Object item;
589 592 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
590 593 i = nextKeyIndex(i, len) ) {
591 594 // The following test triggers if the item at slot i (which
592 595 // hashes to be at slot r) should take the spot vacated by d.
593 596 // If so, we swap it in, and then continue with d now at the
594 597 // newly vacated i. This process will terminate when we hit
595 598 // the null slot at the end of this run.
596 599 // The test is messy because we are using a circular table.
597 600 int r = hash(item, len);
598 601 if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
599 602 tab[d] = item;
600 603 tab[d + 1] = tab[i + 1];
601 604 tab[i] = null;
602 605 tab[i + 1] = null;
603 606 d = i;
604 607 }
605 608 }
606 609 }
607 610
608 611 /**
609 612 * Removes all of the mappings from this map.
610 613 * The map will be empty after this call returns.
611 614 */
612 615 public void clear() {
613 616 modCount++;
614 617 Object[] tab = table;
615 618 for (int i = 0; i < tab.length; i++)
616 619 tab[i] = null;
617 620 size = 0;
618 621 }
619 622
620 623 /**
621 624 * Compares the specified object with this map for equality. Returns
622 625 * <tt>true</tt> if the given object is also a map and the two maps
623 626 * represent identical object-reference mappings. More formally, this
624 627 * map is equal to another map <tt>m</tt> if and only if
625 628 * <tt>this.entrySet().equals(m.entrySet())</tt>.
626 629 *
627 630 * <p><b>Owing to the reference-equality-based semantics of this map it is
628 631 * possible that the symmetry and transitivity requirements of the
629 632 * <tt>Object.equals</tt> contract may be violated if this map is compared
630 633 * to a normal map. However, the <tt>Object.equals</tt> contract is
|
↓ open down ↓ |
93 lines elided |
↑ open up ↑ |
631 634 * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
632 635 *
633 636 * @param o object to be compared for equality with this map
634 637 * @return <tt>true</tt> if the specified object is equal to this map
635 638 * @see Object#equals(Object)
636 639 */
637 640 public boolean equals(Object o) {
638 641 if (o == this) {
639 642 return true;
640 643 } else if (o instanceof IdentityHashMap) {
641 - IdentityHashMap m = (IdentityHashMap) o;
644 + IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) o;
642 645 if (m.size() != size)
643 646 return false;
644 647
645 648 Object[] tab = m.table;
646 649 for (int i = 0; i < tab.length; i+=2) {
647 650 Object k = tab[i];
648 651 if (k != null && !containsMapping(k, tab[i + 1]))
649 652 return false;
650 653 }
651 654 return true;
652 655 } else if (o instanceof Map) {
653 - Map m = (Map)o;
656 + Map<?,?> m = (Map<?,?>)o;
654 657 return entrySet().equals(m.entrySet());
655 658 } else {
656 659 return false; // o is not a Map
657 660 }
658 661 }
659 662
660 663 /**
661 664 * Returns the hash code value for this map. The hash code of a map is
662 665 * defined to be the sum of the hash codes of each entry in the map's
663 666 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
664 667 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
665 668 * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
666 669 * required by the general contract of {@link Object#hashCode}.
667 670 *
668 671 * <p><b>Owing to the reference-equality-based semantics of the
669 672 * <tt>Map.Entry</tt> instances in the set returned by this map's
670 673 * <tt>entrySet</tt> method, it is possible that the contractual
671 674 * requirement of <tt>Object.hashCode</tt> mentioned in the previous
672 675 * paragraph will be violated if one of the two objects being compared is
673 676 * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
674 677 *
675 678 * @return the hash code value for this map
676 679 * @see Object#equals(Object)
677 680 * @see #equals(Object)
678 681 */
679 682 public int hashCode() {
680 683 int result = 0;
681 684 Object[] tab = table;
682 685 for (int i = 0; i < tab.length; i +=2) {
683 686 Object key = tab[i];
684 687 if (key != null) {
685 688 Object k = unmaskNull(key);
686 689 result += System.identityHashCode(k) ^
687 690 System.identityHashCode(tab[i + 1]);
688 691 }
689 692 }
690 693 return result;
|
↓ open down ↓ |
27 lines elided |
↑ open up ↑ |
691 694 }
692 695
693 696 /**
694 697 * Returns a shallow copy of this identity hash map: the keys and values
695 698 * themselves are not cloned.
696 699 *
697 700 * @return a shallow copy of this map
698 701 */
699 702 public Object clone() {
700 703 try {
701 - IdentityHashMap<K,V> m = (IdentityHashMap<K,V>) super.clone();
704 + IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) super.clone();
702 705 m.entrySet = null;
703 706 m.table = table.clone();
704 707 return m;
705 708 } catch (CloneNotSupportedException e) {
706 709 throw new InternalError(e);
707 710 }
708 711 }
709 712
710 713 private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
711 714 int index = (size != 0 ? 0 : table.length); // current slot.
712 715 int expectedModCount = modCount; // to support fast-fail
713 716 int lastReturnedIndex = -1; // to allow remove()
714 717 boolean indexValid; // To avoid unnecessary next computation
715 718 Object[] traversalTable = table; // reference to main table or copy
716 719
717 720 public boolean hasNext() {
718 721 Object[] tab = traversalTable;
719 722 for (int i = index; i < tab.length; i+=2) {
720 723 Object key = tab[i];
721 724 if (key != null) {
722 725 index = i;
723 726 return indexValid = true;
724 727 }
725 728 }
726 729 index = tab.length;
727 730 return false;
728 731 }
729 732
730 733 protected int nextIndex() {
731 734 if (modCount != expectedModCount)
732 735 throw new ConcurrentModificationException();
733 736 if (!indexValid && !hasNext())
734 737 throw new NoSuchElementException();
735 738
736 739 indexValid = false;
737 740 lastReturnedIndex = index;
738 741 index += 2;
739 742 return lastReturnedIndex;
740 743 }
741 744
742 745 public void remove() {
743 746 if (lastReturnedIndex == -1)
744 747 throw new IllegalStateException();
745 748 if (modCount != expectedModCount)
746 749 throw new ConcurrentModificationException();
747 750
748 751 expectedModCount = ++modCount;
749 752 int deletedSlot = lastReturnedIndex;
750 753 lastReturnedIndex = -1;
751 754 // back up index to revisit new contents after deletion
752 755 index = deletedSlot;
753 756 indexValid = false;
754 757
755 758 // Removal code proceeds as in closeDeletion except that
756 759 // it must catch the rare case where an element already
757 760 // seen is swapped into a vacant slot that will be later
758 761 // traversed by this iterator. We cannot allow future
759 762 // next() calls to return it again. The likelihood of
760 763 // this occurring under 2/3 load factor is very slim, but
|
↓ open down ↓ |
49 lines elided |
↑ open up ↑ |
761 764 // when it does happen, we must make a copy of the rest of
762 765 // the table to use for the rest of the traversal. Since
763 766 // this can only happen when we are near the end of the table,
764 767 // even in these rare cases, this is not very expensive in
765 768 // time or space.
766 769
767 770 Object[] tab = traversalTable;
768 771 int len = tab.length;
769 772
770 773 int d = deletedSlot;
771 - K key = (K) tab[d];
774 + Object key = tab[d];
772 775 tab[d] = null; // vacate the slot
773 776 tab[d + 1] = null;
774 777
775 778 // If traversing a copy, remove in real table.
776 779 // We can skip gap-closure on copy.
777 780 if (tab != IdentityHashMap.this.table) {
778 781 IdentityHashMap.this.remove(key);
779 782 expectedModCount = modCount;
780 783 return;
781 784 }
782 785
783 786 size--;
784 787
785 788 Object item;
786 789 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
787 790 i = nextKeyIndex(i, len)) {
788 791 int r = hash(item, len);
789 792 // See closeDeletion for explanation of this conditional
790 793 if ((i < r && (r <= d || d <= i)) ||
791 794 (r <= d && d <= i)) {
792 795
793 796 // If we are about to swap an already-seen element
794 797 // into a slot that may later be returned by next(),
795 798 // then clone the rest of table for use in future
796 799 // next() calls. It is OK that our copy will have
797 800 // a gap in the "wrong" place, since it will never
798 801 // be used for searching anyway.
799 802
800 803 if (i < deletedSlot && d >= deletedSlot &&
801 804 traversalTable == IdentityHashMap.this.table) {
802 805 int remaining = len - deletedSlot;
803 806 Object[] newTable = new Object[remaining];
804 807 System.arraycopy(tab, deletedSlot,
805 808 newTable, 0, remaining);
806 809 traversalTable = newTable;
807 810 index = 0;
808 811 }
809 812
810 813 tab[d] = item;
|
↓ open down ↓ |
29 lines elided |
↑ open up ↑ |
811 814 tab[d + 1] = tab[i + 1];
812 815 tab[i] = null;
813 816 tab[i + 1] = null;
814 817 d = i;
815 818 }
816 819 }
817 820 }
818 821 }
819 822
820 823 private class KeyIterator extends IdentityHashMapIterator<K> {
824 + @SuppressWarnings("unchecked")
821 825 public K next() {
822 826 return (K) unmaskNull(traversalTable[nextIndex()]);
823 827 }
824 828 }
825 829
826 830 private class ValueIterator extends IdentityHashMapIterator<V> {
831 + @SuppressWarnings("unchecked")
827 832 public V next() {
828 833 return (V) traversalTable[nextIndex() + 1];
829 834 }
830 835 }
831 836
832 837 private class EntryIterator
833 838 extends IdentityHashMapIterator<Map.Entry<K,V>>
834 839 {
835 840 private Entry lastReturnedEntry = null;
836 841
837 842 public Map.Entry<K,V> next() {
838 843 lastReturnedEntry = new Entry(nextIndex());
839 844 return lastReturnedEntry;
840 845 }
841 846
842 847 public void remove() {
843 848 lastReturnedIndex =
844 849 ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
845 850 super.remove();
846 851 lastReturnedEntry.index = lastReturnedIndex;
|
↓ open down ↓ |
10 lines elided |
↑ open up ↑ |
847 852 lastReturnedEntry = null;
848 853 }
849 854
850 855 private class Entry implements Map.Entry<K,V> {
851 856 private int index;
852 857
853 858 private Entry(int index) {
854 859 this.index = index;
855 860 }
856 861
862 + @SuppressWarnings("unchecked")
857 863 public K getKey() {
858 864 checkIndexForEntryUse();
859 865 return (K) unmaskNull(traversalTable[index]);
860 866 }
861 867
868 + @SuppressWarnings("unchecked")
862 869 public V getValue() {
863 870 checkIndexForEntryUse();
864 871 return (V) traversalTable[index+1];
865 872 }
866 873
874 + @SuppressWarnings("unchecked")
867 875 public V setValue(V value) {
868 876 checkIndexForEntryUse();
869 877 V oldValue = (V) traversalTable[index+1];
870 878 traversalTable[index+1] = value;
871 879 // if shadowing, force into main table
872 880 if (traversalTable != IdentityHashMap.this.table)
873 881 put((K) traversalTable[index], value);
874 882 return oldValue;
875 883 }
876 884
877 885 public boolean equals(Object o) {
878 886 if (index < 0)
879 887 return super.equals(o);
880 888
881 889 if (!(o instanceof Map.Entry))
882 890 return false;
883 - Map.Entry e = (Map.Entry)o;
891 + Map.Entry<?,?> e = (Map.Entry<?,?>)o;
884 892 return (e.getKey() == unmaskNull(traversalTable[index]) &&
885 893 e.getValue() == traversalTable[index+1]);
886 894 }
887 895
888 896 public int hashCode() {
889 897 if (lastReturnedIndex < 0)
890 898 return super.hashCode();
891 899
892 900 return (System.identityHashCode(unmaskNull(traversalTable[index])) ^
893 901 System.identityHashCode(traversalTable[index+1]));
894 902 }
895 903
896 904 public String toString() {
897 905 if (index < 0)
898 906 return super.toString();
899 907
900 908 return (unmaskNull(traversalTable[index]) + "="
901 909 + traversalTable[index+1]);
902 910 }
903 911
904 912 private void checkIndexForEntryUse() {
905 913 if (index < 0)
906 914 throw new IllegalStateException("Entry was removed");
907 915 }
908 916 }
909 917 }
910 918
911 919 // Views
912 920
913 921 /**
914 922 * This field is initialized to contain an instance of the entry set
915 923 * view the first time this view is requested. The view is stateless,
916 924 * so there's no reason to create more than one.
917 925 */
918 926 private transient Set<Map.Entry<K,V>> entrySet = null;
919 927
920 928 /**
921 929 * Returns an identity-based set view of the keys contained in this map.
922 930 * The set is backed by the map, so changes to the map are reflected in
923 931 * the set, and vice-versa. If the map is modified while an iteration
924 932 * over the set is in progress, the results of the iteration are
925 933 * undefined. The set supports element removal, which removes the
926 934 * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
927 935 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
928 936 * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
929 937 * <tt>addAll</tt> methods.
930 938 *
931 939 * <p><b>While the object returned by this method implements the
932 940 * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
933 941 * contract. Like its backing map, the set returned by this method
934 942 * defines element equality as reference-equality rather than
935 943 * object-equality. This affects the behavior of its <tt>contains</tt>,
936 944 * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
937 945 * <tt>hashCode</tt> methods.</b>
938 946 *
939 947 * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
940 948 * only if the specified object is a set containing exactly the same
941 949 * object references as the returned set. The symmetry and transitivity
942 950 * requirements of the <tt>Object.equals</tt> contract may be violated if
943 951 * the set returned by this method is compared to a normal set. However,
944 952 * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
945 953 * returned by this method.</b>
946 954 *
947 955 * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
948 956 * the <i>identity hashcodes</i> of the elements in the set, rather than
949 957 * the sum of their hashcodes. This is mandated by the change in the
950 958 * semantics of the <tt>equals</tt> method, in order to enforce the
951 959 * general contract of the <tt>Object.hashCode</tt> method among sets
952 960 * returned by this method.
953 961 *
954 962 * @return an identity-based set view of the keys contained in this map
955 963 * @see Object#equals(Object)
956 964 * @see System#identityHashCode(Object)
957 965 */
958 966 public Set<K> keySet() {
959 967 Set<K> ks = keySet;
960 968 if (ks != null)
961 969 return ks;
962 970 else
963 971 return keySet = new KeySet();
964 972 }
965 973
966 974 private class KeySet extends AbstractSet<K> {
967 975 public Iterator<K> iterator() {
968 976 return new KeyIterator();
969 977 }
970 978 public int size() {
971 979 return size;
972 980 }
973 981 public boolean contains(Object o) {
974 982 return containsKey(o);
975 983 }
976 984 public boolean remove(Object o) {
977 985 int oldSize = size;
978 986 IdentityHashMap.this.remove(o);
979 987 return size != oldSize;
980 988 }
981 989 /*
982 990 * Must revert from AbstractSet's impl to AbstractCollection's, as
983 991 * the former contains an optimization that results in incorrect
984 992 * behavior when c is a smaller "normal" (non-identity-based) Set.
985 993 */
986 994 public boolean removeAll(Collection<?> c) {
987 995 boolean modified = false;
988 996 for (Iterator<K> i = iterator(); i.hasNext(); ) {
989 997 if (c.contains(i.next())) {
990 998 i.remove();
991 999 modified = true;
992 1000 }
993 1001 }
994 1002 return modified;
995 1003 }
996 1004 public void clear() {
997 1005 IdentityHashMap.this.clear();
998 1006 }
999 1007 public int hashCode() {
1000 1008 int result = 0;
1001 1009 for (K key : this)
1002 1010 result += System.identityHashCode(key);
1003 1011 return result;
1004 1012 }
1005 1013 }
1006 1014
1007 1015 /**
1008 1016 * Returns a {@link Collection} view of the values contained in this map.
1009 1017 * The collection is backed by the map, so changes to the map are
1010 1018 * reflected in the collection, and vice-versa. If the map is
1011 1019 * modified while an iteration over the collection is in progress,
1012 1020 * the results of the iteration are undefined. The collection
1013 1021 * supports element removal, which removes the corresponding
1014 1022 * mapping from the map, via the <tt>Iterator.remove</tt>,
1015 1023 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1016 1024 * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not
1017 1025 * support the <tt>add</tt> or <tt>addAll</tt> methods.
1018 1026 *
1019 1027 * <p><b>While the object returned by this method implements the
1020 1028 * <tt>Collection</tt> interface, it does <i>not</i> obey
1021 1029 * <tt>Collection's</tt> general contract. Like its backing map,
1022 1030 * the collection returned by this method defines element equality as
1023 1031 * reference-equality rather than object-equality. This affects the
1024 1032 * behavior of its <tt>contains</tt>, <tt>remove</tt> and
1025 1033 * <tt>containsAll</tt> methods.</b>
1026 1034 */
1027 1035 public Collection<V> values() {
1028 1036 Collection<V> vs = values;
1029 1037 if (vs != null)
1030 1038 return vs;
1031 1039 else
1032 1040 return values = new Values();
1033 1041 }
1034 1042
1035 1043 private class Values extends AbstractCollection<V> {
1036 1044 public Iterator<V> iterator() {
1037 1045 return new ValueIterator();
1038 1046 }
1039 1047 public int size() {
1040 1048 return size;
1041 1049 }
1042 1050 public boolean contains(Object o) {
1043 1051 return containsValue(o);
1044 1052 }
1045 1053 public boolean remove(Object o) {
1046 1054 for (Iterator<V> i = iterator(); i.hasNext(); ) {
1047 1055 if (i.next() == o) {
1048 1056 i.remove();
1049 1057 return true;
1050 1058 }
1051 1059 }
1052 1060 return false;
1053 1061 }
1054 1062 public void clear() {
1055 1063 IdentityHashMap.this.clear();
1056 1064 }
1057 1065 }
1058 1066
1059 1067 /**
1060 1068 * Returns a {@link Set} view of the mappings contained in this map.
1061 1069 * Each element in the returned set is a reference-equality-based
1062 1070 * <tt>Map.Entry</tt>. The set is backed by the map, so changes
1063 1071 * to the map are reflected in the set, and vice-versa. If the
1064 1072 * map is modified while an iteration over the set is in progress,
1065 1073 * the results of the iteration are undefined. The set supports
1066 1074 * element removal, which removes the corresponding mapping from
1067 1075 * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1068 1076 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1069 1077 * methods. It does not support the <tt>add</tt> or
1070 1078 * <tt>addAll</tt> methods.
1071 1079 *
1072 1080 * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1073 1081 * returned by this method define key and value equality as
1074 1082 * reference-equality rather than object-equality. This affects the
1075 1083 * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1076 1084 * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
1077 1085 * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1078 1086 * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
1079 1087 * e.getValue()==o.getValue()</tt>. To accommodate these equals
1080 1088 * semantics, the <tt>hashCode</tt> method returns
1081 1089 * <tt>System.identityHashCode(e.getKey()) ^
1082 1090 * System.identityHashCode(e.getValue())</tt>.
1083 1091 *
1084 1092 * <p><b>Owing to the reference-equality-based semantics of the
1085 1093 * <tt>Map.Entry</tt> instances in the set returned by this method,
1086 1094 * it is possible that the symmetry and transitivity requirements of
1087 1095 * the {@link Object#equals(Object)} contract may be violated if any of
1088 1096 * the entries in the set is compared to a normal map entry, or if
1089 1097 * the set returned by this method is compared to a set of normal map
1090 1098 * entries (such as would be returned by a call to this method on a normal
1091 1099 * map). However, the <tt>Object.equals</tt> contract is guaranteed to
1092 1100 * hold among identity-based map entries, and among sets of such entries.
1093 1101 * </b>
1094 1102 *
1095 1103 * @return a set view of the identity-mappings contained in this map
1096 1104 */
1097 1105 public Set<Map.Entry<K,V>> entrySet() {
1098 1106 Set<Map.Entry<K,V>> es = entrySet;
1099 1107 if (es != null)
1100 1108 return es;
1101 1109 else
|
↓ open down ↓ |
208 lines elided |
↑ open up ↑ |
1102 1110 return entrySet = new EntrySet();
1103 1111 }
1104 1112
1105 1113 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1106 1114 public Iterator<Map.Entry<K,V>> iterator() {
1107 1115 return new EntryIterator();
1108 1116 }
1109 1117 public boolean contains(Object o) {
1110 1118 if (!(o instanceof Map.Entry))
1111 1119 return false;
1112 - Map.Entry entry = (Map.Entry)o;
1120 + Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1113 1121 return containsMapping(entry.getKey(), entry.getValue());
1114 1122 }
1115 1123 public boolean remove(Object o) {
1116 1124 if (!(o instanceof Map.Entry))
1117 1125 return false;
1118 - Map.Entry entry = (Map.Entry)o;
1126 + Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1119 1127 return removeMapping(entry.getKey(), entry.getValue());
1120 1128 }
1121 1129 public int size() {
1122 1130 return size;
1123 1131 }
1124 1132 public void clear() {
1125 1133 IdentityHashMap.this.clear();
1126 1134 }
1127 1135 /*
1128 1136 * Must revert from AbstractSet's impl to AbstractCollection's, as
1129 1137 * the former contains an optimization that results in incorrect
1130 1138 * behavior when c is a smaller "normal" (non-identity-based) Set.
1131 1139 */
1132 1140 public boolean removeAll(Collection<?> c) {
1133 1141 boolean modified = false;
1134 1142 for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
1135 1143 if (c.contains(i.next())) {
1136 1144 i.remove();
1137 1145 modified = true;
1138 1146 }
1139 1147 }
1140 1148 return modified;
1141 1149 }
1142 1150
1143 1151 public Object[] toArray() {
1144 1152 int size = size();
1145 1153 Object[] result = new Object[size];
1146 1154 Iterator<Map.Entry<K,V>> it = iterator();
1147 1155 for (int i = 0; i < size; i++)
1148 1156 result[i] = new AbstractMap.SimpleEntry<>(it.next());
1149 1157 return result;
1150 1158 }
1151 1159
1152 1160 @SuppressWarnings("unchecked")
1153 1161 public <T> T[] toArray(T[] a) {
1154 1162 int size = size();
1155 1163 if (a.length < size)
1156 1164 a = (T[])java.lang.reflect.Array
1157 1165 .newInstance(a.getClass().getComponentType(), size);
1158 1166 Iterator<Map.Entry<K,V>> it = iterator();
1159 1167 for (int i = 0; i < size; i++)
1160 1168 a[i] = (T) new AbstractMap.SimpleEntry<>(it.next());
1161 1169 if (a.length > size)
1162 1170 a[size] = null;
1163 1171 return a;
1164 1172 }
1165 1173 }
1166 1174
1167 1175
1168 1176 private static final long serialVersionUID = 8188218128353913216L;
1169 1177
1170 1178 /**
1171 1179 * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1172 1180 * (i.e., serialize it).
1173 1181 *
1174 1182 * @serialData The <i>size</i> of the HashMap (the number of key-value
1175 1183 * mappings) (<tt>int</tt>), followed by the key (Object) and
1176 1184 * value (Object) for each key-value mapping represented by the
1177 1185 * IdentityHashMap. The key-value mappings are emitted in no
1178 1186 * particular order.
1179 1187 */
1180 1188 private void writeObject(java.io.ObjectOutputStream s)
1181 1189 throws java.io.IOException {
1182 1190 // Write out and any hidden stuff
1183 1191 s.defaultWriteObject();
1184 1192
1185 1193 // Write out size (number of Mappings)
1186 1194 s.writeInt(size);
1187 1195
1188 1196 // Write out keys and values (alternating)
1189 1197 Object[] tab = table;
1190 1198 for (int i = 0; i < tab.length; i += 2) {
1191 1199 Object key = tab[i];
1192 1200 if (key != null) {
1193 1201 s.writeObject(unmaskNull(key));
1194 1202 s.writeObject(tab[i + 1]);
1195 1203 }
1196 1204 }
1197 1205 }
1198 1206
1199 1207 /**
1200 1208 * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1201 1209 * deserialize it).
1202 1210 */
1203 1211 private void readObject(java.io.ObjectInputStream s)
1204 1212 throws java.io.IOException, ClassNotFoundException {
1205 1213 // Read in any hidden stuff
|
↓ open down ↓ |
77 lines elided |
↑ open up ↑ |
1206 1214 s.defaultReadObject();
1207 1215
1208 1216 // Read in size (number of Mappings)
1209 1217 int size = s.readInt();
1210 1218
1211 1219 // Allow for 33% growth (i.e., capacity is >= 2* size()).
1212 1220 init(capacity((size*4)/3));
1213 1221
1214 1222 // Read the keys and values, and put the mappings in the table
1215 1223 for (int i=0; i<size; i++) {
1216 - K key = (K) s.readObject();
1217 - V value = (V) s.readObject();
1224 + @SuppressWarnings("unchecked")
1225 + K key = (K) s.readObject();
1226 + @SuppressWarnings("unchecked")
1227 + V value = (V) s.readObject();
1218 1228 putForCreate(key, value);
1219 1229 }
1220 1230 }
1221 1231
1222 1232 /**
1223 1233 * The put method for readObject. It does not resize the table,
1224 1234 * update modCount, etc.
1225 1235 */
1226 1236 private void putForCreate(K key, V value)
1227 1237 throws IOException
1228 1238 {
1229 - K k = (K)maskNull(key);
1239 + Object k = maskNull(key);
1230 1240 Object[] tab = table;
1231 1241 int len = tab.length;
1232 1242 int i = hash(k, len);
1233 1243
1234 1244 Object item;
1235 1245 while ( (item = tab[i]) != null) {
1236 1246 if (item == k)
1237 1247 throw new java.io.StreamCorruptedException();
1238 1248 i = nextKeyIndex(i, len);
1239 1249 }
1240 1250 tab[i] = k;
1241 1251 tab[i + 1] = value;
1242 1252 }
1243 1253 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX