Java > Open Source Codes > java > util > IdentityHashMap


1 /*
2  * @(#)IdentityHashMap.java 1.23 05/09/02
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package java.util;
9
10 import java.io.*;
11
12 /**
13  * This class implements the <tt>Map</tt> interface with a hash table, using
14  * reference-equality in place of object-equality when comparing keys (and
15  * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
16  * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
17  * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
18  * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
19  * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
20  *
21  * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
22  * implementation! While this class implements the <tt>Map</tt> interface, it
23  * intentionally violates <tt>Map's</tt> general contract, which mandates the
24  * use of the <tt>equals</tt> method when comparing objects. This class is
25  * designed for use only in the rare cases wherein reference-equality
26  * semantics are required.</b>
27  *
28  * <p>A typical use of this class is <i>topology-preserving object graph
29  * transformations</i>, such as serialization or deep-copying. To perform such
30  * a transformation, a program must maintain a "node table" that keeps track
31  * of all the object references that have already been processed. The node
32  * table must not equate distinct objects even if they happen to be equal.
33  * Another typical use of this class is to maintain <i>proxy objects</i>. For
34  * example, a debugging facility might wish to maintain a proxy object for
35  * each object in the program being debugged.
36  *
37  * <p>This class provides all of the optional map operations, and permits
38  * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
39  * guarantees as to the order of the map; in particular, it does not guarantee
40  * that the order will remain constant over time.
41  *
42  * <p>This class provides constant-time performance for the basic
43  * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
44  * identity hash function ({@link System#identityHashCode(Object)})
45  * disperses elements properly among the buckets.
46  *
47  * <p>This class has one tuning parameter (which affects performance but not
48  * semantics): <i>expected maximum size</i>. This parameter is the maximum
49  * number of key-value mappings that the map is expected to hold. Internally,
50  * this parameter is used to determine the number of buckets initially
51  * comprising the hash table. The precise relationship between the expected
52  * maximum size and the number of buckets is unspecified.
53  *
54  * <p>If the size of the map (the number of key-value mappings) sufficiently
55  * exceeds the expected maximum size, the number of buckets is increased
56  * Increasing the number of buckets ("rehashing") may be fairly expensive, so
57  * it pays to create identity hash maps with a sufficiently large expected
58  * maximum size. On the other hand, iteration over collection views requires
59  * time proportional to the number of buckets in the hash table, so it
60  * pays not to set the expected maximum size too high if you are especially
61  * concerned with iteration performance or memory usage.
62  *
63  * <p><b>Note that this implementation is not synchronized.</b> If multiple
64  * threads access this map concurrently, and at least one of the threads
65  * modifies the map structurally, it <i>must</i> be synchronized externally.
66  * (A structural modification is any operation that adds or deletes one or
67  * more mappings; merely changing the value associated with a key that an
68  * instance already contains is not a structural modification.) This is
69  * typically accomplished by synchronizing on some object that naturally
70  * encapsulates the map. If no such object exists, the map should be
71  * "wrapped" using the <tt>Collections.synchronizedMap</tt> method. This is
72  * best done at creation time, to prevent accidental unsynchronized access to
73  * the map: <pre>
74  * Map m = Collections.synchronizedMap(new HashMap(...));
75  * </pre>
76  *
77  * <p>The iterators returned by all of this class's "collection view methods"
78  * are <i>fail-fast</i>: if the map is structurally modified at any time after
79  * the iterator is created, in any way except through the iterator's own
80  * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
81  * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
82  * modification, the iterator fails quickly and cleanly, rather than risking
83  * arbitrary, non-deterministic behavior at an undetermined time in the
84  * future.
85  *
86  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
87  * as it is, generally speaking, impossible to make any hard guarantees in the
88  * presence of unsynchronized concurrent modification. Fail-fast iterators
89  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
90  * Therefore, it would be wrong to write a program that depended on this
91  * exception for its correctness: <i>fail-fast iterators should be used only
92  * to detect bugs.</i>
93  *
94  * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
95  * as described for example in texts by Sedgewick and Knuth. The array
96  * alternates holding keys and values. (This has better locality for large
97  * tables than does using separate arrays.) For many JRE implementations
98  * and operation mixes, this class will yield better performance than
99  * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
100  *
101  * <p>This class is a member of the
102  * <a HREF="{@docRoot}/../guide/collections/index.html">
103  * Java Collections Framework</a>.
104  *
105  * @see System#identityHashCode(Object)
106  * @see Object#hashCode()
107  * @see Collection
108  * @see Map
109  * @see HashMap
110  * @see TreeMap
111  * @author Doug Lea and Josh Bloch
112  * @since 1.4
113  */
114
115 public class IdentityHashMap<K,V>
116     extends AbstractMap <K,V>
117     implements Map <K,V>, java.io.Serializable , Cloneable
118 {
119     /**
120      * The initial capacity used by the no-args constructor.
121      * MUST be a power of two. The value 32 corresponds to the
122      * (specified) expected maximum size of 21, given a load factor
123      * of 2/3.
124      */
125     private static final int DEFAULT_CAPACITY = 32;
126
127     /**
128      * The minimum capacity, used if a lower value is implicitly specified
129      * by either of the constructors with arguments. The value 4 corresponds
130      * to an expected maximum size of 2, given a load factor of 2/3.
131      * MUST be a power of two.
132      */
133     private static final int MINIMUM_CAPACITY = 4;
134
135     /**
136      * The maximum capacity, used if a higher value is implicitly specified
137      * by either of the constructors with arguments.
138      * MUST be a power of two <= 1<<29.
139      */
140     private static final int MAXIMUM_CAPACITY = 1 << 29;
141
142     /**
143      * The table, resized as necessary. Length MUST always be a power of two.
144      */
145     private transient Object [] table;
146
147     /**
148      * The number of key-value mappings contained in this identity hash map.
149      *
150      * @serial
151      */
152     private int size;
153
154     /**
155      * The number of modifications, to support fast-fail iterators
156      */
157     private transient volatile int modCount;
158
159     /**
160      * The next size value at which to resize (capacity * load factor).
161      */
162     private transient int threshold;
163
164     /**
165      * Value representing null keys inside tables.
166      */
167     private static final Object NULL_KEY = new Object ();
168
169     /**
170      * Use NULL_KEY for key if it is null.
171      */
172
173     private static Object maskNull(Object key) {
174         return (key == null ? NULL_KEY : key);
175     }
176
177     /**
178      * Return internal representation of null key back to caller as null
179      */
180     private static Object unmaskNull(Object key) {
181         return (key == NULL_KEY ? null : key);
182     }
183
184     /**
185      * Constructs a new, empty identity hash map with a default expected
186      * maximum size (21).
187      */
188     public IdentityHashMap() {
189         init(DEFAULT_CAPACITY);
190     }
191
192     /**
193      * Constructs a new, empty map with the specified expected maximum size.
194      * Putting more than the expected number of key-value mappings into
195      * the map may cause the internal data structure to grow, which may be
196      * somewhat time-consuming.
197      *
198      * @param expectedMaxSize the expected maximum size of the map.
199      * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
200      */
201     public IdentityHashMap(int expectedMaxSize) {
202         if (expectedMaxSize < 0)
203             throw new IllegalArgumentException ("expectedMaxSize is negative: "
204                                                + expectedMaxSize);
205         init(capacity(expectedMaxSize));
206     }
207
208     /**
209      * Returns the appropriate capacity for the specified expected maximum
210      * size. Returns the smallest power of two between MINIMUM_CAPACITY
211      * and MAXIMUM_CAPACITY, inclusive, that is greater than
212      * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
213      * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
214      * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
215      */
216     private int capacity(int expectedMaxSize) {
217         // Compute min capacity for expectedMaxSize given a load factor of 2/3
218 int minCapacity = (3 * expectedMaxSize)/2;
219
220         // Compute the appropriate capacity
221 int result;
222         if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
223             result = MAXIMUM_CAPACITY;
224         } else {
225             result = MINIMUM_CAPACITY;
226             while (result < minCapacity)
227                 result <<= 1;
228         }
229         return result;
230     }
231
232     /**
233      * Initialize object to be an empty map with the specified initial
234      * capacity, which is assumed to be a power of two between
235      * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
236      */
237     private void init(int initCapacity) {
238         // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
239 // assert initCapacity >= MINIMUM_CAPACITY;
240 // assert initCapacity <= MAXIMUM_CAPACITY;
241
242         threshold = (initCapacity * 2)/3;
243         table = new Object [2 * initCapacity];
244     }
245
246     /**
247      * Constructs a new identity hash map containing the keys-value mappings
248      * in the specified map.
249      *
250      * @param m the map whose mappings are to be placed into this map.
251      * @throws NullPointerException if the specified map is null.
252      */
253     public IdentityHashMap(Map <? extends K, ? extends V> m) {
254         // Allow for a bit of growth
255 this((int) ((1 + m.size()) * 1.1));
256         putAll(m);
257     }
258
259     /**
260      * Returns the number of key-value mappings in this identity hash map.
261      *
262      * @return the number of key-value mappings in this map.
263      */
264     public int size() {
265         return size;
266     }
267
268     /**
269      * Returns <tt>true</tt> if this identity hash map contains no key-value
270      * mappings.
271      *
272      * @return <tt>true</tt> if this identity hash map contains no key-value
273      * mappings.
274      */
275     public boolean isEmpty() {
276         return size == 0;
277     }
278
279     /**
280      * Return index for Object x.
281      */
282     private static int hash(Object x, int length) {
283         int h = System.identityHashCode(x);
284         // Multiply by -127, and left-shift to use least bit as part of hash
285 return ((h << 1) - (h << 8)) & (length - 1);
286     }
287
288     /**
289      * Circularly traverse table of size len.
290      **/
291     private static int nextKeyIndex(int i, int len) {
292         return (i + 2 < len ? i + 2 : 0);
293     }
294
295     /**
296      * Returns the value to which the specified key is mapped in this identity
297      * hash map, or <tt>null</tt> if the map contains no mapping for
298      * this key. A return value of <tt>null</tt> does not <i>necessarily</i>
299      * indicate that the map contains no mapping for the key; it is also
300      * possible that the map explicitly maps the key to <tt>null</tt>. The
301      * <tt>containsKey</tt> method may be used to distinguish these two
302      * cases.
303      *
304      * @param key the key whose associated value is to be returned.
305      * @return the value to which this map maps the specified key, or
306      * <tt>null</tt> if the map contains no mapping for this key.
307      * @see #put(Object, Object)
308      */
309     public V get(Object key) {
310         Object k = maskNull(key);
311     Object [] tab = table;
312         int len = tab.length;
313         int i = hash(k, len);
314         while (true) {
315         Object item = tab[i];
316             if (item == k)
317                 return (V) tab[i + 1];
318             if (item == null)
319                 return null;
320             i = nextKeyIndex(i, len);
321         }
322     }
323
324     /**
325      * Tests whether the specified object reference is a key in this identity
326      * hash map.
327      *
328      * @param key possible key.
329      * @return <code>true</code> if the specified object reference is a key
330      * in this map.
331      * @see #containsValue(Object)
332      */
333     public boolean containsKey(Object key) {
334         Object k = maskNull(key);
335         Object [] tab = table;
336         int len = tab.length;
337         int i = hash(k, len);
338         while (true) {
339             Object item = tab[i];
340             if (item == k)
341                 return true;
342             if (item == null)
343                 return false;
344             i = nextKeyIndex(i, len);
345         }
346     }
347
348     /**
349      * Tests whether the specified object reference is a value in this identity
350      * hash map.
351      *
352      * @param value value whose presence in this map is to be tested.
353      * @return <tt>true</tt> if this map maps one or more keys to the
354      * specified object reference.
355      * @see #containsKey(Object)
356      */
357     public boolean containsValue(Object value) {
358         Object [] tab = table;
359         for (int i = 1; i < tab.length; i+= 2)
360             if (tab[i] == value)
361                 return true;
362
363         return false;
364     }
365
366     /**
367      * Tests if the specified key-value mapping is in the map.
368      *
369      * @param key possible key.
370      * @param value possible value.
371      * @return <code>true</code> if and only if the specified key-value
372      * mapping is in map.
373      */
374     private boolean containsMapping(Object key, Object value) {
375         Object k = maskNull(key);
376         Object [] tab = table;
377         int len = tab.length;
378         int i = hash(k, len);
379         while (true) {
380             Object item = tab[i];
381             if (item == k)
382                 return tab[i + 1] == value;
383             if (item == null)
384                 return false;
385             i = nextKeyIndex(i, len);
386         }
387     }
388
389     /**
390      * Associates the specified value with the specified key in this identity
391      * hash map. If the map previously contained a mapping for this key, the
392      * old value is replaced.
393      *
394      * @param key the key with which the specified value is to be associated.
395      * @param value the value to be associated with the specified key.
396      * @return the previous value associated with <tt>key</tt>, or
397      * <tt>null</tt> if there was no mapping for <tt>key</tt>. (A
398      * <tt>null</tt> return can also indicate that the map previously
399      * associated <tt>null</tt> with the specified key.)
400      * @see Object#equals(Object)
401      * @see #get(Object)
402      * @see #containsKey(Object)
403      */
404     public V put(K key, V value) {
405         Object k = maskNull(key);
406         Object [] tab = table;
407         int len = tab.length;
408         int i = hash(k, len);
409
410         Object item;
411         while ( (item = tab[i]) != null) {
412             if (item == k) {
413         V oldValue = (V) tab[i + 1];
414                 tab[i + 1] = value;
415                 return oldValue;
416             }
417             i = nextKeyIndex(i, len);
418         }
419
420         modCount++;
421         tab[i] = k;
422         tab[i + 1] = value;
423         if (++size >= threshold)
424             resize(len); // len == 2 * current capacity.
425 return null;
426     }
427
428     /**
429      * Resize the table to hold given capacity.
430      *
431      * @param newCapacity the new capacity, must be a power of two.
432      */
433     private void resize(int newCapacity) {
434         // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
435 int newLength = newCapacity * 2;
436
437     Object [] oldTable = table;
438         int oldLength = oldTable.length;
439         if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
440 if (threshold == MAXIMUM_CAPACITY-1)
441                 throw new IllegalStateException ("Capacity exhausted.");
442             threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
443 return;
444         }
445         if (oldLength >= newLength)
446             return;
447
448     Object [] newTable = new Object [newLength];
449         threshold = newLength / 3;
450
451         for (int j = 0; j < oldLength; j += 2) {
452             Object key = oldTable[j];
453             if (key != null) {
454                 Object value = oldTable[j+1];
455                 oldTable[j] = null;
456                 oldTable[j+1] = null;
457                 int i = hash(key, newLength);
458                 while (newTable[i] != null)
459                     i = nextKeyIndex(i, newLength);
460                 newTable[i] = key;
461                 newTable[i + 1] = value;
462             }
463         }
464         table = newTable;
465     }
466
467     /**
468      * Copies all of the mappings from the specified map to this map
469      * These mappings will replace any mappings that
470      * this map had for any of the keys currently in the specified map.<p>
471      *
472      * @param t mappings to be stored in this map.
473      * @throws NullPointerException if the specified map is null.
474      */
475     public void putAll(Map <? extends K, ? extends V> t) {
476         int n = t.size();
477         if (n == 0)
478             return;
479         if (n > threshold) // conservatively pre-expand
480 resize(capacity(n));
481
482     for (Entry<? extends K, ? extends V> e : t.entrySet())
483             put(e.getKey(), e.getValue());
484     }
485
486     /**
487      * Removes the mapping for this key from this map if present.
488      *
489      * @param key key whose mapping is to be removed from the map.
490      * @return previous value associated with specified key, or <tt>null</tt>
491      * if there was no entry for key. (A <tt>null</tt> return can
492      * also indicate that the map previously associated <tt>null</tt>
493      * with the specified key.)
494      */
495     public V remove(Object key) {
496         Object k = maskNull(key);
497         Object [] tab = table;
498         int len = tab.length;
499         int i = hash(k, len);
500
501         while (true) {
502             Object item = tab[i];
503             if (item == k) {
504                 modCount++;
505                 size--;
506                 V oldValue = (V) tab[i + 1];
507                 tab[i + 1] = null;
508                 tab[i] = null;
509                 closeDeletion(i);
510                 return oldValue;
511             }
512             if (item == null)
513                 return null;
514             i = nextKeyIndex(i, len);
515         }
516
517     }
518
519     /**
520      * Removes the specified key-value mapping from the map if it is present.
521      *
522      * @param key possible key.
523      * @param value possible value.
524      * @return <code>true</code> if and only if the specified key-value
525      * mapping was in map.
526      */
527     private boolean removeMapping(Object key, Object value) {
528         Object k = maskNull(key);
529         Object [] tab = table;
530         int len = tab.length;
531         int i = hash(k, len);
532
533         while (true) {
534             Object item = tab[i];
535             if (item == k) {
536                 if (tab[i + 1] != value)
537                     return false;
538                 modCount++;
539                 size--;
540                 tab[i] = null;
541                 tab[i + 1] = null;
542                 closeDeletion(i);
543                 return true;
544             }
545             if (item == null)
546                 return false;
547             i = nextKeyIndex(i, len);
548         }
549     }
550
551     /**
552      * Rehash all possibly-colliding entries following a
553      * deletion. This preserves the linear-probe
554      * collision properties required by get, put, etc.
555      *
556      * @param d the index of a newly empty deleted slot
557      */
558     private void closeDeletion(int d) {
559         // Adapted from Knuth Section 6.4 Algorithm R
560 Object [] tab = table;
561         int len = tab.length;
562
563         // Look for items to swap into newly vacated slot
564 // starting at index immediately following deletion,
565 // and continuing until a null slot is seen, indicating
566 // the end of a run of possibly-colliding keys.
567 Object item;
568         for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
569              i = nextKeyIndex(i, len) ) {
570             // The following test triggers if the item at slot i (which
571 // hashes to be at slot r) should take the spot vacated by d.
572 // If so, we swap it in, and then continue with d now at the
573 // newly vacated i. This process will terminate when we hit
574 // the null slot at the end of this run.
575 // The test is messy because we are using a circular table.
576 int r = hash(item, len);
577             if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
578                 tab[d] = item;
579                 tab[d + 1] = tab[i + 1];
580                 tab[i] = null;
581                 tab[i + 1] = null;
582                 d = i;
583             }
584         }
585     }
586
587     /**
588      * Removes all mappings from this map.
589      */
590     public void clear() {
591         modCount++;
592         Object [] tab = table;
593         for (int i = 0; i < tab.length; i++)
594             tab[i] = null;
595         size = 0;
596     }
597
598     /**
599      * Compares the specified object with this map for equality. Returns
600      * <tt>true</tt> if the given object is also a map and the two maps
601      * represent identical object-reference mappings. More formally, this
602      * map is equal to another map <tt>m</tt> if and only if
603      * map <tt>this.entrySet().equals(m.entrySet())</tt>.
604      *
605      * <p><b>Owing to the reference-equality-based semantics of this map it is
606      * possible that the symmetry and transitivity requirements of the
607      * <tt>Object.equals</tt> contract may be violated if this map is compared
608      * to a normal map. However, the <tt>Object.equals</tt> contract is
609      * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
610      *
611      * @param o object to be compared for equality with this map.
612      * @return <tt>true</tt> if the specified object is equal to this map.
613      * @see Object#equals(Object)
614      */
615     public boolean equals(Object o) {
616         if (o == this) {
617             return true;
618         } else if (o instanceof IdentityHashMap ) {
619             IdentityHashMap m = (IdentityHashMap ) o;
620             if (m.size() != size)
621                 return false;
622
623             Object [] tab = m.table;
624             for (int i = 0; i < tab.length; i+=2) {
625                 Object k = tab[i];
626                 if (k != null && !containsMapping(k, tab[i + 1]))
627                     return false;
628             }
629             return true;
630         } else if (o instanceof Map ) {
631             Map m = (Map )o;
632             return entrySet().equals(m.entrySet());
633         } else {
634             return false; // o is not a Map
635 }
636     }
637
638     /**
639      * Returns the hash code value for this map. The hash code of a map
640      * is defined to be the sum of the hashcode of each entry in the map's
641      * entrySet view. This ensures that <tt>t1.equals(t2)</tt> implies
642      * that <tt>t1.hashCode()==t2.hashCode()</tt> for any two
643      * <tt>IdentityHashMap</tt> instances <tt>t1</tt> and <tt>t2</tt>, as
644      * required by the general contract of {@link Object#hashCode()}.
645      *
646      * <p><b>Owing to the reference-equality-based semantics of the
647      * <tt>Map.Entry</tt> instances in the set returned by this map's
648      * <tt>entrySet</tt> method, it is possible that the contractual
649      * requirement of <tt>Object.hashCode</tt> mentioned in the previous
650      * paragraph will be violated if one of the two objects being compared is
651      * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
652      *
653      * @return the hash code value for this map.
654      * @see Object#hashCode()
655      * @see Object#equals(Object)
656      * @see #equals(Object)
657      */
658     public int hashCode() {
659         int result = 0;
660         Object [] tab = table;
661         for (int i = 0; i < tab.length; i +=2) {
662             Object key = tab[i];
663             if (key != null) {
664                 Object k = unmaskNull(key);
665                 result += System.identityHashCode(k) ^
666                           System.identityHashCode(tab[i + 1]);
667             }
668         }
669         return result;
670     }
671
672     /**
673      * Returns a shallow copy of this identity hash map: the keys and values
674      * themselves are not cloned.
675      *
676      * @return a shallow copy of this map.
677      */
678     public Object clone() {
679         try {
680             IdentityHashMap <K,V> t = (IdentityHashMap <K,V>) super.clone();
681             t.entrySet = null;
682             t.table = (Object [])table.clone();
683             return t;
684         } catch (CloneNotSupportedException e) {
685             throw new InternalError ();
686         }
687     }
688
689     private abstract class IdentityHashMapIterator<T> implements Iterator <T> {
690         int index = (size != 0 ? 0 : table.length); // current slot.
691 int expectedModCount = modCount; // to support fast-fail
692 int lastReturnedIndex = -1; // to allow remove()
693 boolean indexValid; // To avoid unnecessary next computation
694 Object [] traversalTable = table; // reference to main table or copy
695
696         public boolean hasNext() {
697             Object [] tab = traversalTable;
698             for (int i = index; i < tab.length; i+=2) {
699                 Object key = tab[i];
700                 if (key != null) {
701                     index = i;
702                     return indexValid = true;
703                 }
704             }
705             index = tab.length;
706             return false;
707         }
708
709         protected int nextIndex() {
710             if (modCount != expectedModCount)
711                 throw new ConcurrentModificationException ();
712             if (!indexValid && !hasNext())
713                 throw new NoSuchElementException ();
714
715             indexValid = false;
716             lastReturnedIndex = index;
717             index += 2;
718             return lastReturnedIndex;
719         }
720
721         public void remove() {
722             if (lastReturnedIndex == -1)
723                 throw new IllegalStateException ();
724             if (modCount != expectedModCount)
725                 throw new ConcurrentModificationException ();
726
727             expectedModCount = ++modCount;
728             int deletedSlot = lastReturnedIndex;
729             lastReturnedIndex = -1;
730             size--;
731             // back up index to revisit new contents after deletion
732 index = deletedSlot;
733             indexValid = false;
734
735             // Removal code proceeds as in closeDeletion except that
736 // it must catch the rare case where an element already
737 // seen is swapped into a vacant slot that will be later
738 // traversed by this iterator. We cannot allow future
739 // next() calls to return it again. The likelihood of
740 // this occurring under 2/3 load factor is very slim, but
741 // when it does happen, we must make a copy of the rest of
742 // the table to use for the rest of the traversal. Since
743 // this can only happen when we are near the end of the table,
744 // even in these rare cases, this is not very expensive in
745 // time or space.
746
747             Object [] tab = traversalTable;
748             int len = tab.length;
749
750             int d = deletedSlot;
751             K key = (K) tab[d];
752             tab[d] = null; // vacate the slot
753 tab[d + 1] = null;
754
755             // If traversing a copy, remove in real table.
756 // We can skip gap-closure on copy.
757 if (tab != IdentityHashMap.this.table) {
758                 IdentityHashMap.this.remove(key);
759                 expectedModCount = modCount;
760                 return;
761             }
762
763             Object item;
764             for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
765                  i = nextKeyIndex(i, len)) {
766                 int r = hash(item, len);
767                 // See closeDeletion for explanation of this conditional
768 if ((i < r && (r <= d || d <= i)) ||
769                     (r <= d && d <= i)) {
770
771                     // If we are about to swap an already-seen element
772 // into a slot that may later be returned by next(),
773 // then clone the rest of table for use in future
774 // next() calls. It is OK that our copy will have
775 // a gap in the "wrong" place, since it will never
776 // be used for searching anyway.
777
778                     if (i < deletedSlot && d >= deletedSlot &&
779                         traversalTable == IdentityHashMap.this.table) {
780                         int remaining = len - deletedSlot;
781                         Object [] newTable = new Object [remaining];
782                         System.arraycopy(tab, deletedSlot,
783                                          newTable, 0, remaining);
784                         traversalTable = newTable;
785                         index = 0;
786                     }
787
788                     tab[d] = item;
789                     tab[d + 1] = tab[i + 1];
790                     tab[i] = null;
791                     tab[i + 1] = null;
792                     d = i;
793                 }
794             }
795         }
796     }
797
798     private class KeyIterator extends IdentityHashMapIterator<K> {
799         public K next() {
800             return (K) unmaskNull(traversalTable[nextIndex()]);
801         }
802     }
803
804     private class ValueIterator extends IdentityHashMapIterator<V> {
805         public V next() {
806             return (V) traversalTable[nextIndex() + 1];
807         }
808     }
809
810     /**
811      * Since we don't use Entry objects, we use the Iterator
812      * itself as an entry.
813      */
814     private class EntryIterator
815     extends IdentityHashMapIterator<Map.Entry <K,V>>
816     implements Map.Entry <K,V>
817     {
818         public Map.Entry <K,V> next() {
819             nextIndex();
820             return this;
821         }
822
823         public K getKey() {
824             // Provide a better exception than out of bounds index
825 if (lastReturnedIndex < 0)
826                 throw new IllegalStateException ("Entry was removed");
827
828             return (K) unmaskNull(traversalTable[lastReturnedIndex]);
829         }
830
831         public V getValue() {
832             // Provide a better exception than out of bounds index
833 if (lastReturnedIndex < 0)
834                 throw new IllegalStateException ("Entry was removed");
835
836             return (V) traversalTable[lastReturnedIndex+1];
837         }
838
839         public V setValue(V value) {
840             // It would be mean-spirited to proceed here if remove() called
841 if (lastReturnedIndex < 0)
842                 throw new IllegalStateException ("Entry was removed");
843         V oldValue = (V) traversalTable[lastReturnedIndex+1];
844             traversalTable[lastReturnedIndex+1] = value;
845             // if shadowing, force into main table
846 if (traversalTable != IdentityHashMap.this.table)
847                 put((K) traversalTable[lastReturnedIndex], value);
848             return oldValue;
849         }
850
851         public boolean equals(Object o) {
852             if (lastReturnedIndex < 0)
853                 return super.equals(o);
854
855             if (!(o instanceof Map.Entry ))
856                 return false;
857             Map.Entry e = (Map.Entry )o;
858             return e.getKey() == getKey() &&
859                    e.getValue() == getValue();
860         }
861
862         public int hashCode() {
863