Locale.getDefault() reads real value from navigator.language & co.
2 * Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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.
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
30 * This class implements the <tt>Map</tt> interface with a hash table, using
31 * reference-equality in place of object-equality when comparing keys (and
32 * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
33 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
34 * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
35 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
36 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
38 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
39 * implementation! While this class implements the <tt>Map</tt> interface, it
40 * intentionally violates <tt>Map's</tt> general contract, which mandates the
41 * use of the <tt>equals</tt> method when comparing objects. This class is
42 * designed for use only in the rare cases wherein reference-equality
43 * semantics are required.</b>
45 * <p>A typical use of this class is <i>topology-preserving object graph
46 * transformations</i>, such as serialization or deep-copying. To perform such
47 * a transformation, a program must maintain a "node table" that keeps track
48 * of all the object references that have already been processed. The node
49 * table must not equate distinct objects even if they happen to be equal.
50 * Another typical use of this class is to maintain <i>proxy objects</i>. For
51 * example, a debugging facility might wish to maintain a proxy object for
52 * each object in the program being debugged.
54 * <p>This class provides all of the optional map operations, and permits
55 * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
56 * guarantees as to the order of the map; in particular, it does not guarantee
57 * that the order will remain constant over time.
59 * <p>This class provides constant-time performance for the basic
60 * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
61 * identity hash function ({@link System#identityHashCode(Object)})
62 * disperses elements properly among the buckets.
64 * <p>This class has one tuning parameter (which affects performance but not
65 * semantics): <i>expected maximum size</i>. This parameter is the maximum
66 * number of key-value mappings that the map is expected to hold. Internally,
67 * this parameter is used to determine the number of buckets initially
68 * comprising the hash table. The precise relationship between the expected
69 * maximum size and the number of buckets is unspecified.
71 * <p>If the size of the map (the number of key-value mappings) sufficiently
72 * exceeds the expected maximum size, the number of buckets is increased
73 * Increasing the number of buckets ("rehashing") may be fairly expensive, so
74 * it pays to create identity hash maps with a sufficiently large expected
75 * maximum size. On the other hand, iteration over collection views requires
76 * time proportional to the number of buckets in the hash table, so it
77 * pays not to set the expected maximum size too high if you are especially
78 * concerned with iteration performance or memory usage.
80 * <p><strong>Note that this implementation is not synchronized.</strong>
81 * If multiple threads access an identity hash map concurrently, and at
82 * least one of the threads modifies the map structurally, it <i>must</i>
83 * be synchronized externally. (A structural modification is any operation
84 * that adds or deletes one or more mappings; merely changing the value
85 * associated with a key that an instance already contains is not a
86 * structural modification.) This is typically accomplished by
87 * synchronizing on some object that naturally encapsulates the map.
89 * If no such object exists, the map should be "wrapped" using the
90 * {@link Collections#synchronizedMap Collections.synchronizedMap}
91 * method. This is best done at creation time, to prevent accidental
92 * unsynchronized access to the map:<pre>
93 * Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
95 * <p>The iterators returned by the <tt>iterator</tt> method of the
96 * collections returned by all of this class's "collection view
97 * methods" are <i>fail-fast</i>: if the map is structurally modified
98 * at any time after the iterator is created, in any way except
99 * through the iterator's own <tt>remove</tt> method, the iterator
100 * will throw a {@link ConcurrentModificationException}. Thus, in the
101 * face of concurrent modification, the iterator fails quickly and
102 * cleanly, rather than risking arbitrary, non-deterministic behavior
103 * at an undetermined time in the future.
105 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
106 * as it is, generally speaking, impossible to make any hard guarantees in the
107 * presence of unsynchronized concurrent modification. Fail-fast iterators
108 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
109 * Therefore, it would be wrong to write a program that depended on this
110 * exception for its correctness: <i>fail-fast iterators should be used only
111 * to detect bugs.</i>
113 * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
114 * as described for example in texts by Sedgewick and Knuth. The array
115 * alternates holding keys and values. (This has better locality for large
116 * tables than does using separate arrays.) For many JRE implementations
117 * and operation mixes, this class will yield better performance than
118 * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
120 * <p>This class is a member of the
121 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
122 * Java Collections Framework</a>.
124 * @see System#identityHashCode(Object)
125 * @see Object#hashCode()
130 * @author Doug Lea and Josh Bloch
134 public class IdentityHashMap<K,V>
135 extends AbstractMap<K,V>
136 implements Map<K,V>, java.io.Serializable, Cloneable
139 * The initial capacity used by the no-args constructor.
140 * MUST be a power of two. The value 32 corresponds to the
141 * (specified) expected maximum size of 21, given a load factor
144 private static final int DEFAULT_CAPACITY = 32;
147 * The minimum capacity, used if a lower value is implicitly specified
148 * by either of the constructors with arguments. The value 4 corresponds
149 * to an expected maximum size of 2, given a load factor of 2/3.
150 * MUST be a power of two.
152 private static final int MINIMUM_CAPACITY = 4;
155 * The maximum capacity, used if a higher value is implicitly specified
156 * by either of the constructors with arguments.
157 * MUST be a power of two <= 1<<29.
159 private static final int MAXIMUM_CAPACITY = 1 << 29;
162 * The table, resized as necessary. Length MUST always be a power of two.
164 private transient Object[] table;
167 * The number of key-value mappings contained in this identity hash map.
174 * The number of modifications, to support fast-fail iterators
176 private transient int modCount;
179 * The next size value at which to resize (capacity * load factor).
181 private transient int threshold;
184 * Value representing null keys inside tables.
186 private static final Object NULL_KEY = new Object();
189 * Use NULL_KEY for key if it is null.
191 private static Object maskNull(Object key) {
192 return (key == null ? NULL_KEY : key);
196 * Returns internal representation of null key back to caller as null.
198 private static Object unmaskNull(Object key) {
199 return (key == NULL_KEY ? null : key);
203 * Constructs a new, empty identity hash map with a default expected
206 public IdentityHashMap() {
207 init(DEFAULT_CAPACITY);
211 * Constructs a new, empty map with the specified expected maximum size.
212 * Putting more than the expected number of key-value mappings into
213 * the map may cause the internal data structure to grow, which may be
214 * somewhat time-consuming.
216 * @param expectedMaxSize the expected maximum size of the map
217 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
219 public IdentityHashMap(int expectedMaxSize) {
220 if (expectedMaxSize < 0)
221 throw new IllegalArgumentException("expectedMaxSize is negative: "
223 init(capacity(expectedMaxSize));
227 * Returns the appropriate capacity for the specified expected maximum
228 * size. Returns the smallest power of two between MINIMUM_CAPACITY
229 * and MAXIMUM_CAPACITY, inclusive, that is greater than
230 * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
231 * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
232 * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
234 private int capacity(int expectedMaxSize) {
235 // Compute min capacity for expectedMaxSize given a load factor of 2/3
236 int minCapacity = (3 * expectedMaxSize)/2;
238 // Compute the appropriate capacity
240 if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
241 result = MAXIMUM_CAPACITY;
243 result = MINIMUM_CAPACITY;
244 while (result < minCapacity)
251 * Initializes object to be an empty map with the specified initial
252 * capacity, which is assumed to be a power of two between
253 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
255 private void init(int initCapacity) {
256 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
257 // assert initCapacity >= MINIMUM_CAPACITY;
258 // assert initCapacity <= MAXIMUM_CAPACITY;
260 threshold = (initCapacity * 2)/3;
261 table = new Object[2 * initCapacity];
265 * Constructs a new identity hash map containing the keys-value mappings
266 * in the specified map.
268 * @param m the map whose mappings are to be placed into this map
269 * @throws NullPointerException if the specified map is null
271 public IdentityHashMap(Map<? extends K, ? extends V> m) {
272 // Allow for a bit of growth
273 this((int) ((1 + m.size()) * 1.1));
278 * Returns the number of key-value mappings in this identity hash map.
280 * @return the number of key-value mappings in this map
287 * Returns <tt>true</tt> if this identity hash map contains no key-value
290 * @return <tt>true</tt> if this identity hash map contains no key-value
293 public boolean isEmpty() {
298 * Returns index for Object x.
300 private static int hash(Object x, int length) {
301 int h = System.identityHashCode(x);
302 // Multiply by -127, and left-shift to use least bit as part of hash
303 return ((h << 1) - (h << 8)) & (length - 1);
307 * Circularly traverses table of size len.
309 private static int nextKeyIndex(int i, int len) {
310 return (i + 2 < len ? i + 2 : 0);
314 * Returns the value to which the specified key is mapped,
315 * or {@code null} if this map contains no mapping for the key.
317 * <p>More formally, if this map contains a mapping from a key
318 * {@code k} to a value {@code v} such that {@code (key == k)},
319 * then this method returns {@code v}; otherwise it returns
320 * {@code null}. (There can be at most one such mapping.)
322 * <p>A return value of {@code null} does not <i>necessarily</i>
323 * indicate that the map contains no mapping for the key; it's also
324 * possible that the map explicitly maps the key to {@code null}.
325 * The {@link #containsKey containsKey} operation may be used to
326 * distinguish these two cases.
328 * @see #put(Object, Object)
330 public V get(Object key) {
331 Object k = maskNull(key);
332 Object[] tab = table;
333 int len = tab.length;
334 int i = hash(k, len);
336 Object item = tab[i];
338 return (V) tab[i + 1];
341 i = nextKeyIndex(i, len);
346 * Tests whether the specified object reference is a key in this identity
349 * @param key possible key
350 * @return <code>true</code> if the specified object reference is a key
352 * @see #containsValue(Object)
354 public boolean containsKey(Object key) {
355 Object k = maskNull(key);
356 Object[] tab = table;
357 int len = tab.length;
358 int i = hash(k, len);
360 Object item = tab[i];
365 i = nextKeyIndex(i, len);
370 * Tests whether the specified object reference is a value in this identity
373 * @param value value whose presence in this map is to be tested
374 * @return <tt>true</tt> if this map maps one or more keys to the
375 * specified object reference
376 * @see #containsKey(Object)
378 public boolean containsValue(Object value) {
379 Object[] tab = table;
380 for (int i = 1; i < tab.length; i += 2)
381 if (tab[i] == value && tab[i - 1] != null)
388 * Tests if the specified key-value mapping is in the map.
390 * @param key possible key
391 * @param value possible value
392 * @return <code>true</code> if and only if the specified key-value
393 * mapping is in the map
395 private boolean containsMapping(Object key, Object value) {
396 Object k = maskNull(key);
397 Object[] tab = table;
398 int len = tab.length;
399 int i = hash(k, len);
401 Object item = tab[i];
403 return tab[i + 1] == value;
406 i = nextKeyIndex(i, len);
411 * Associates the specified value with the specified key in this identity
412 * hash map. If the map previously contained a mapping for the key, the
413 * old value is replaced.
415 * @param key the key with which the specified value is to be associated
416 * @param value the value to be associated with the specified key
417 * @return the previous value associated with <tt>key</tt>, or
418 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
419 * (A <tt>null</tt> return can also indicate that the map
420 * previously associated <tt>null</tt> with <tt>key</tt>.)
421 * @see Object#equals(Object)
423 * @see #containsKey(Object)
425 public V put(K key, V value) {
426 Object k = maskNull(key);
427 Object[] tab = table;
428 int len = tab.length;
429 int i = hash(k, len);
432 while ( (item = tab[i]) != null) {
434 V oldValue = (V) tab[i + 1];
438 i = nextKeyIndex(i, len);
444 if (++size >= threshold)
445 resize(len); // len == 2 * current capacity.
450 * Resize the table to hold given capacity.
452 * @param newCapacity the new capacity, must be a power of two.
454 private void resize(int newCapacity) {
455 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
456 int newLength = newCapacity * 2;
458 Object[] oldTable = table;
459 int oldLength = oldTable.length;
460 if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
461 if (threshold == MAXIMUM_CAPACITY-1)
462 throw new IllegalStateException("Capacity exhausted.");
463 threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
466 if (oldLength >= newLength)
469 Object[] newTable = new Object[newLength];
470 threshold = newLength / 3;
472 for (int j = 0; j < oldLength; j += 2) {
473 Object key = oldTable[j];
475 Object value = oldTable[j+1];
477 oldTable[j+1] = null;
478 int i = hash(key, newLength);
479 while (newTable[i] != null)
480 i = nextKeyIndex(i, newLength);
482 newTable[i + 1] = value;
489 * Copies all of the mappings from the specified map to this map.
490 * These mappings will replace any mappings that this map had for
491 * any of the keys currently in the specified map.
493 * @param m mappings to be stored in this map
494 * @throws NullPointerException if the specified map is null
496 public void putAll(Map<? extends K, ? extends V> m) {
500 if (n > threshold) // conservatively pre-expand
503 for (Entry<? extends K, ? extends V> e : m.entrySet())
504 put(e.getKey(), e.getValue());
508 * Removes the mapping for this key from this map if present.
510 * @param key key whose mapping is to be removed from the map
511 * @return the previous value associated with <tt>key</tt>, or
512 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
513 * (A <tt>null</tt> return can also indicate that the map
514 * previously associated <tt>null</tt> with <tt>key</tt>.)
516 public V remove(Object key) {
517 Object k = maskNull(key);
518 Object[] tab = table;
519 int len = tab.length;
520 int i = hash(k, len);
523 Object item = tab[i];
527 V oldValue = (V) tab[i + 1];
535 i = nextKeyIndex(i, len);
541 * Removes the specified key-value mapping from the map if it is present.
543 * @param key possible key
544 * @param value possible value
545 * @return <code>true</code> if and only if the specified key-value
546 * mapping was in the map
548 private boolean removeMapping(Object key, Object value) {
549 Object k = maskNull(key);
550 Object[] tab = table;
551 int len = tab.length;
552 int i = hash(k, len);
555 Object item = tab[i];
557 if (tab[i + 1] != value)
568 i = nextKeyIndex(i, len);
573 * Rehash all possibly-colliding entries following a
574 * deletion. This preserves the linear-probe
575 * collision properties required by get, put, etc.
577 * @param d the index of a newly empty deleted slot
579 private void closeDeletion(int d) {
580 // Adapted from Knuth Section 6.4 Algorithm R
581 Object[] tab = table;
582 int len = tab.length;
584 // Look for items to swap into newly vacated slot
585 // starting at index immediately following deletion,
586 // and continuing until a null slot is seen, indicating
587 // the end of a run of possibly-colliding keys.
589 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
590 i = nextKeyIndex(i, len) ) {
591 // The following test triggers if the item at slot i (which
592 // hashes to be at slot r) should take the spot vacated by d.
593 // If so, we swap it in, and then continue with d now at the
594 // newly vacated i. This process will terminate when we hit
595 // the null slot at the end of this run.
596 // The test is messy because we are using a circular table.
597 int r = hash(item, len);
598 if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
600 tab[d + 1] = tab[i + 1];
609 * Removes all of the mappings from this map.
610 * The map will be empty after this call returns.
612 public void clear() {
614 Object[] tab = table;
615 for (int i = 0; i < tab.length; i++)
621 * Compares the specified object with this map for equality. Returns
622 * <tt>true</tt> if the given object is also a map and the two maps
623 * represent identical object-reference mappings. More formally, this
624 * map is equal to another map <tt>m</tt> if and only if
625 * <tt>this.entrySet().equals(m.entrySet())</tt>.
627 * <p><b>Owing to the reference-equality-based semantics of this map it is
628 * possible that the symmetry and transitivity requirements of the
629 * <tt>Object.equals</tt> contract may be violated if this map is compared
630 * to a normal map. However, the <tt>Object.equals</tt> contract is
631 * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
633 * @param o object to be compared for equality with this map
634 * @return <tt>true</tt> if the specified object is equal to this map
635 * @see Object#equals(Object)
637 public boolean equals(Object o) {
640 } else if (o instanceof IdentityHashMap) {
641 IdentityHashMap m = (IdentityHashMap) o;
642 if (m.size() != size)
645 Object[] tab = m.table;
646 for (int i = 0; i < tab.length; i+=2) {
648 if (k != null && !containsMapping(k, tab[i + 1]))
652 } else if (o instanceof Map) {
654 return entrySet().equals(m.entrySet());
656 return false; // o is not a Map
661 * Returns the hash code value for this map. The hash code of a map is
662 * defined to be the sum of the hash codes of each entry in the map's
663 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
664 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
665 * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
666 * required by the general contract of {@link Object#hashCode}.
668 * <p><b>Owing to the reference-equality-based semantics of the
669 * <tt>Map.Entry</tt> instances in the set returned by this map's
670 * <tt>entrySet</tt> method, it is possible that the contractual
671 * requirement of <tt>Object.hashCode</tt> mentioned in the previous
672 * paragraph will be violated if one of the two objects being compared is
673 * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
675 * @return the hash code value for this map
676 * @see Object#equals(Object)
677 * @see #equals(Object)
679 public int hashCode() {
681 Object[] tab = table;
682 for (int i = 0; i < tab.length; i +=2) {
685 Object k = unmaskNull(key);
686 result += System.identityHashCode(k) ^
687 System.identityHashCode(tab[i + 1]);
694 * Returns a shallow copy of this identity hash map: the keys and values
695 * themselves are not cloned.
697 * @return a shallow copy of this map
699 public Object clone() {
701 IdentityHashMap<K,V> m = (IdentityHashMap<K,V>) super.clone();
703 m.table = table.clone();
705 } catch (CloneNotSupportedException e) {
706 throw new InternalError();
710 private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
711 int index = (size != 0 ? 0 : table.length); // current slot.
712 int expectedModCount = modCount; // to support fast-fail
713 int lastReturnedIndex = -1; // to allow remove()
714 boolean indexValid; // To avoid unnecessary next computation
715 Object[] traversalTable = table; // reference to main table or copy
717 public boolean hasNext() {
718 Object[] tab = traversalTable;
719 for (int i = index; i < tab.length; i+=2) {
723 return indexValid = true;
730 protected int nextIndex() {
731 if (modCount != expectedModCount)
732 throw new ConcurrentModificationException();
733 if (!indexValid && !hasNext())
734 throw new NoSuchElementException();
737 lastReturnedIndex = index;
739 return lastReturnedIndex;
742 public void remove() {
743 if (lastReturnedIndex == -1)
744 throw new IllegalStateException();
745 if (modCount != expectedModCount)
746 throw new ConcurrentModificationException();
748 expectedModCount = ++modCount;
749 int deletedSlot = lastReturnedIndex;
750 lastReturnedIndex = -1;
751 // back up index to revisit new contents after deletion
755 // Removal code proceeds as in closeDeletion except that
756 // it must catch the rare case where an element already
757 // seen is swapped into a vacant slot that will be later
758 // traversed by this iterator. We cannot allow future
759 // next() calls to return it again. The likelihood of
760 // this occurring under 2/3 load factor is very slim, but
761 // when it does happen, we must make a copy of the rest of
762 // the table to use for the rest of the traversal. Since
763 // this can only happen when we are near the end of the table,
764 // even in these rare cases, this is not very expensive in
767 Object[] tab = traversalTable;
768 int len = tab.length;
772 tab[d] = null; // vacate the slot
775 // If traversing a copy, remove in real table.
776 // We can skip gap-closure on copy.
777 if (tab != IdentityHashMap.this.table) {
778 IdentityHashMap.this.remove(key);
779 expectedModCount = modCount;
786 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
787 i = nextKeyIndex(i, len)) {
788 int r = hash(item, len);
789 // See closeDeletion for explanation of this conditional
790 if ((i < r && (r <= d || d <= i)) ||
791 (r <= d && d <= i)) {
793 // If we are about to swap an already-seen element
794 // into a slot that may later be returned by next(),
795 // then clone the rest of table for use in future
796 // next() calls. It is OK that our copy will have
797 // a gap in the "wrong" place, since it will never
798 // be used for searching anyway.
800 if (i < deletedSlot && d >= deletedSlot &&
801 traversalTable == IdentityHashMap.this.table) {
802 int remaining = len - deletedSlot;
803 Object[] newTable = new Object[remaining];
804 System.arraycopy(tab, deletedSlot,
805 newTable, 0, remaining);
806 traversalTable = newTable;
811 tab[d + 1] = tab[i + 1];
820 private class KeyIterator extends IdentityHashMapIterator<K> {
822 return (K) unmaskNull(traversalTable[nextIndex()]);
826 private class ValueIterator extends IdentityHashMapIterator<V> {
828 return (V) traversalTable[nextIndex() + 1];
832 private class EntryIterator
833 extends IdentityHashMapIterator<Map.Entry<K,V>>
835 private Entry lastReturnedEntry = null;
837 public Map.Entry<K,V> next() {
838 lastReturnedEntry = new Entry(nextIndex());
839 return lastReturnedEntry;
842 public void remove() {
844 ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
846 lastReturnedEntry.index = lastReturnedIndex;
847 lastReturnedEntry = null;
850 private class Entry implements Map.Entry<K,V> {
853 private Entry(int index) {
858 checkIndexForEntryUse();
859 return (K) unmaskNull(traversalTable[index]);
862 public V getValue() {
863 checkIndexForEntryUse();
864 return (V) traversalTable[index+1];
867 public V setValue(V value) {
868 checkIndexForEntryUse();
869 V oldValue = (V) traversalTable[index+1];
870 traversalTable[index+1] = value;
871 // if shadowing, force into main table
872 if (traversalTable != IdentityHashMap.this.table)
873 put((K) traversalTable[index], value);
877 public boolean equals(Object o) {
879 return super.equals(o);
881 if (!(o instanceof Map.Entry))
883 Map.Entry e = (Map.Entry)o;
884 return (e.getKey() == unmaskNull(traversalTable[index]) &&
885 e.getValue() == traversalTable[index+1]);
888 public int hashCode() {
889 if (lastReturnedIndex < 0)
890 return super.hashCode();
892 return (System.identityHashCode(unmaskNull(traversalTable[index])) ^
893 System.identityHashCode(traversalTable[index+1]));
896 public String toString() {
898 return super.toString();
900 return (unmaskNull(traversalTable[index]) + "="
901 + traversalTable[index+1]);
904 private void checkIndexForEntryUse() {
906 throw new IllegalStateException("Entry was removed");
914 * This field is initialized to contain an instance of the entry set
915 * view the first time this view is requested. The view is stateless,
916 * so there's no reason to create more than one.
918 private transient Set<Map.Entry<K,V>> entrySet = null;
921 * Returns an identity-based set view of the keys contained in this map.
922 * The set is backed by the map, so changes to the map are reflected in
923 * the set, and vice-versa. If the map is modified while an iteration
924 * over the set is in progress, the results of the iteration are
925 * undefined. The set supports element removal, which removes the
926 * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
927 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
928 * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
929 * <tt>addAll</tt> methods.
931 * <p><b>While the object returned by this method implements the
932 * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
933 * contract. Like its backing map, the set returned by this method
934 * defines element equality as reference-equality rather than
935 * object-equality. This affects the behavior of its <tt>contains</tt>,
936 * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
937 * <tt>hashCode</tt> methods.</b>
939 * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
940 * only if the specified object is a set containing exactly the same
941 * object references as the returned set. The symmetry and transitivity
942 * requirements of the <tt>Object.equals</tt> contract may be violated if
943 * the set returned by this method is compared to a normal set. However,
944 * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
945 * returned by this method.</b>
947 * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
948 * the <i>identity hashcodes</i> of the elements in the set, rather than
949 * the sum of their hashcodes. This is mandated by the change in the
950 * semantics of the <tt>equals</tt> method, in order to enforce the
951 * general contract of the <tt>Object.hashCode</tt> method among sets
952 * returned by this method.
954 * @return an identity-based set view of the keys contained in this map
955 * @see Object#equals(Object)
956 * @see System#identityHashCode(Object)
958 public Set<K> keySet() {
963 return keySet = new KeySet();
966 private class KeySet extends AbstractSet<K> {
967 public Iterator<K> iterator() {
968 return new KeyIterator();
973 public boolean contains(Object o) {
974 return containsKey(o);
976 public boolean remove(Object o) {
978 IdentityHashMap.this.remove(o);
979 return size != oldSize;
982 * Must revert from AbstractSet's impl to AbstractCollection's, as
983 * the former contains an optimization that results in incorrect
984 * behavior when c is a smaller "normal" (non-identity-based) Set.
986 public boolean removeAll(Collection<?> c) {
987 boolean modified = false;
988 for (Iterator<K> i = iterator(); i.hasNext(); ) {
989 if (c.contains(i.next())) {
996 public void clear() {
997 IdentityHashMap.this.clear();
999 public int hashCode() {
1002 result += System.identityHashCode(key);
1008 * Returns a {@link Collection} view of the values contained in this map.
1009 * The collection is backed by the map, so changes to the map are
1010 * reflected in the collection, and vice-versa. If the map is
1011 * modified while an iteration over the collection is in progress,
1012 * the results of the iteration are undefined. The collection
1013 * supports element removal, which removes the corresponding
1014 * mapping from the map, via the <tt>Iterator.remove</tt>,
1015 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1016 * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not
1017 * support the <tt>add</tt> or <tt>addAll</tt> methods.
1019 * <p><b>While the object returned by this method implements the
1020 * <tt>Collection</tt> interface, it does <i>not</i> obey
1021 * <tt>Collection's</tt> general contract. Like its backing map,
1022 * the collection returned by this method defines element equality as
1023 * reference-equality rather than object-equality. This affects the
1024 * behavior of its <tt>contains</tt>, <tt>remove</tt> and
1025 * <tt>containsAll</tt> methods.</b>
1027 public Collection<V> values() {
1028 Collection<V> vs = values;
1032 return values = new Values();
1035 private class Values extends AbstractCollection<V> {
1036 public Iterator<V> iterator() {
1037 return new ValueIterator();
1042 public boolean contains(Object o) {
1043 return containsValue(o);
1045 public boolean remove(Object o) {
1046 for (Iterator<V> i = iterator(); i.hasNext(); ) {
1047 if (i.next() == o) {
1054 public void clear() {
1055 IdentityHashMap.this.clear();
1060 * Returns a {@link Set} view of the mappings contained in this map.
1061 * Each element in the returned set is a reference-equality-based
1062 * <tt>Map.Entry</tt>. The set is backed by the map, so changes
1063 * to the map are reflected in the set, and vice-versa. If the
1064 * map is modified while an iteration over the set is in progress,
1065 * the results of the iteration are undefined. The set supports
1066 * element removal, which removes the corresponding mapping from
1067 * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1068 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1069 * methods. It does not support the <tt>add</tt> or
1070 * <tt>addAll</tt> methods.
1072 * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1073 * returned by this method define key and value equality as
1074 * reference-equality rather than object-equality. This affects the
1075 * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1076 * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
1077 * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1078 * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
1079 * e.getValue()==o.getValue()</tt>. To accommodate these equals
1080 * semantics, the <tt>hashCode</tt> method returns
1081 * <tt>System.identityHashCode(e.getKey()) ^
1082 * System.identityHashCode(e.getValue())</tt>.
1084 * <p><b>Owing to the reference-equality-based semantics of the
1085 * <tt>Map.Entry</tt> instances in the set returned by this method,
1086 * it is possible that the symmetry and transitivity requirements of
1087 * the {@link Object#equals(Object)} contract may be violated if any of
1088 * the entries in the set is compared to a normal map entry, or if
1089 * the set returned by this method is compared to a set of normal map
1090 * entries (such as would be returned by a call to this method on a normal
1091 * map). However, the <tt>Object.equals</tt> contract is guaranteed to
1092 * hold among identity-based map entries, and among sets of such entries.
1095 * @return a set view of the identity-mappings contained in this map
1097 public Set<Map.Entry<K,V>> entrySet() {
1098 Set<Map.Entry<K,V>> es = entrySet;
1102 return entrySet = new EntrySet();
1105 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1106 public Iterator<Map.Entry<K,V>> iterator() {
1107 return new EntryIterator();
1109 public boolean contains(Object o) {
1110 if (!(o instanceof Map.Entry))
1112 Map.Entry entry = (Map.Entry)o;
1113 return containsMapping(entry.getKey(), entry.getValue());
1115 public boolean remove(Object o) {
1116 if (!(o instanceof Map.Entry))
1118 Map.Entry entry = (Map.Entry)o;
1119 return removeMapping(entry.getKey(), entry.getValue());
1124 public void clear() {
1125 IdentityHashMap.this.clear();
1128 * Must revert from AbstractSet's impl to AbstractCollection's, as
1129 * the former contains an optimization that results in incorrect
1130 * behavior when c is a smaller "normal" (non-identity-based) Set.
1132 public boolean removeAll(Collection<?> c) {
1133 boolean modified = false;
1134 for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
1135 if (c.contains(i.next())) {
1143 public Object[] toArray() {
1145 Object[] result = new Object[size];
1146 Iterator<Map.Entry<K,V>> it = iterator();
1147 for (int i = 0; i < size; i++)
1148 result[i] = new AbstractMap.SimpleEntry<>(it.next());
1152 @SuppressWarnings("unchecked")
1153 public <T> T[] toArray(T[] a) {
1155 if (a.length < size)
1156 a = (T[])java.lang.reflect.Array
1157 .newInstance(a.getClass().getComponentType(), size);
1158 Iterator<Map.Entry<K,V>> it = iterator();
1159 for (int i = 0; i < size; i++)
1160 a[i] = (T) new AbstractMap.SimpleEntry<>(it.next());
1161 if (a.length > size)
1168 private static final long serialVersionUID = 8188218128353913216L;
1171 * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1172 * (i.e., serialize it).
1174 * @serialData The <i>size</i> of the HashMap (the number of key-value
1175 * mappings) (<tt>int</tt>), followed by the key (Object) and
1176 * value (Object) for each key-value mapping represented by the
1177 * IdentityHashMap. The key-value mappings are emitted in no
1180 private void writeObject(java.io.ObjectOutputStream s)
1181 throws java.io.IOException {
1182 // Write out and any hidden stuff
1183 s.defaultWriteObject();
1185 // Write out size (number of Mappings)
1188 // Write out keys and values (alternating)
1189 Object[] tab = table;
1190 for (int i = 0; i < tab.length; i += 2) {
1191 Object key = tab[i];
1193 s.writeObject(unmaskNull(key));
1194 s.writeObject(tab[i + 1]);
1200 * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1203 private void readObject(java.io.ObjectInputStream s)
1204 throws java.io.IOException, ClassNotFoundException {
1205 // Read in any hidden stuff
1206 s.defaultReadObject();
1208 // Read in size (number of Mappings)
1209 int size = s.readInt();
1211 // Allow for 33% growth (i.e., capacity is >= 2* size()).
1212 init(capacity((size*4)/3));
1214 // Read the keys and values, and put the mappings in the table
1215 for (int i=0; i<size; i++) {
1216 K key = (K) s.readObject();
1217 V value = (V) s.readObject();
1218 putForCreate(key, value);
1223 * The put method for readObject. It does not resize the table,
1224 * update modCount, etc.
1226 private void putForCreate(K key, V value)
1229 K k = (K)maskNull(key);
1230 Object[] tab = table;
1231 int len = tab.length;
1232 int i = hash(k, len);
1235 while ( (item = tab[i]) != null) {
1237 throw new java.io.StreamCorruptedException();
1238 i = nextKeyIndex(i, len);