Back to index...

	/*
	* Copyright (c) 2000, 2020, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package java.util;

	import java.lang.reflect.Array;
	import java.util.function.BiConsumer;
	import java.util.function.BiFunction;
	import java.util.function.Consumer;
	import jdk.internal.access.SharedSecrets;

	/**
	* This class implements the {@code Map} interface with a hash table, using
	* reference-equality in place of object-equality when comparing keys (and
	* values). In other words, in an {@code IdentityHashMap}, two keys
	* {@code k1} and {@code k2} are considered equal if and only if
	* {@code (k1==k2)}. (In normal {@code Map} implementations (like
	* {@code HashMap}) two keys {@code k1} and {@code k2} are considered equal
	* if and only if {@code (k1==null ? k2==null : k1.equals(k2))}.)
	*
	* <p><b>This class is <i>not</i> a general-purpose {@code Map}
	* implementation! While this class implements the {@code Map} interface, it
	* intentionally violates {@code Map's} general contract, which mandates the
	* use of the {@code equals} method when comparing objects. This class is
	* designed for use only in the rare cases wherein reference-equality
	* semantics are required.</b>
	*
	* <p>A typical use of this class is <i>topology-preserving object graph
	* transformations</i>, such as serialization or deep-copying. To perform such
	* a transformation, a program must maintain a "node table" that keeps track
	* of all the object references that have already been processed. The node
	* table must not equate distinct objects even if they happen to be equal.
	* Another typical use of this class is to maintain <i>proxy objects</i>. For
	* example, a debugging facility might wish to maintain a proxy object for
	* each object in the program being debugged.
	*
	* <p>This class provides all of the optional map operations, and permits
	* {@code null} values and the {@code null} key. This class makes no
	* guarantees as to the order of the map; in particular, it does not guarantee
	* that the order will remain constant over time.
	*
	* <p>This class provides constant-time performance for the basic
	* operations ({@code get} and {@code put}), assuming the system
	* identity hash function ({@link System#identityHashCode(Object)})
	* disperses elements properly among the buckets.
	*
	* <p>This class has one tuning parameter (which affects performance but not
	* semantics): <i>expected maximum size</i>. This parameter is the maximum
	* number of key-value mappings that the map is expected to hold. Internally,
	* this parameter is used to determine the number of buckets initially
	* comprising the hash table. The precise relationship between the expected
	* maximum size and the number of buckets is unspecified.
	*
	* <p>If the size of the map (the number of key-value mappings) sufficiently
	* exceeds the expected maximum size, the number of buckets is increased.
	* Increasing the number of buckets ("rehashing") may be fairly expensive, so
	* it pays to create identity hash maps with a sufficiently large expected
	* maximum size. On the other hand, iteration over collection views requires
	* time proportional to the number of buckets in the hash table, so it
	* pays not to set the expected maximum size too high if you are especially
	* concerned with iteration performance or memory usage.
	*
	* <p><strong>Note that this implementation is not synchronized.</strong>
	* If multiple threads access an identity hash map concurrently, and at
	* least one of the threads modifies the map structurally, it <i>must</i>
	* be synchronized externally. (A structural modification is any operation
	* that adds or deletes one or more mappings; merely changing the value
	* associated with a key that an instance already contains is not a
	* structural modification.) This is typically accomplished by
	* synchronizing on some object that naturally encapsulates the map.
	*
	* If no such object exists, the map should be "wrapped" using the
	* {@link Collections#synchronizedMap Collections.synchronizedMap}
	* method. This is best done at creation time, to prevent accidental
	* unsynchronized access to the map:<pre>
	* Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
	*
	* <p>The iterators returned by the {@code iterator} method of the
	* collections returned by all of this class's "collection view
	* methods" are <i>fail-fast</i>: if the map is structurally modified
	* at any time after the iterator is created, in any way except
	* through the iterator's own {@code remove} method, the iterator
	* will throw a {@link ConcurrentModificationException}. Thus, in the
	* face of concurrent modification, the iterator fails quickly and
	* cleanly, rather than risking arbitrary, non-deterministic behavior
	* at an undetermined time in the future.
	*
	* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
	* as it is, generally speaking, impossible to make any hard guarantees in the
	* presence of unsynchronized concurrent modification. Fail-fast iterators
	* throw {@code ConcurrentModificationException} on a best-effort basis.
	* Therefore, it would be wrong to write a program that depended on this
	* exception for its correctness: <i>fail-fast iterators should be used only
	* to detect bugs.</i>
	*
	* <p>This class is a member of the
	* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
	* Java Collections Framework</a>.
	*
	* @implNote
	* <p>This is a simple <i>linear-probe</i> hash table,
	* as described for example in texts by Sedgewick and Knuth. The array
	* contains alternating keys and values, with keys at even indexes and values
	* at odd indexes. (This arrangement has better locality for large
	* tables than does using separate arrays.) For many Java implementations
	* and operation mixes, this class will yield better performance than
	* {@link HashMap}, which uses <i>chaining</i> rather than linear-probing.
	*
	* @see System#identityHashCode(Object)
	* @see Object#hashCode()
	* @see Collection
	* @see Map
	* @see HashMap
	* @see TreeMap
	* @author Doug Lea and Josh Bloch
	* @since 1.4
	*/

	public class IdentityHashMap<K,V>
	extends AbstractMap<K,V>
	implements Map<K,V>, java.io.Serializable, Cloneable
	{
	/**
	* The initial capacity used by the no-args constructor.
	* MUST be a power of two. The value 32 corresponds to the
	* (specified) expected maximum size of 21, given a load factor
	* of 2/3.
	*/
	private static final int DEFAULT_CAPACITY = 32;

	/**
	* The minimum capacity, used if a lower value is implicitly specified
	* by either of the constructors with arguments. The value 4 corresponds
	* to an expected maximum size of 2, given a load factor of 2/3.
	* MUST be a power of two.
	*/
	private static final int MINIMUM_CAPACITY = 4;

	/**
	* The maximum capacity, used if a higher value is implicitly specified
	* by either of the constructors with arguments.
	* MUST be a power of two <= 1<<29.
	*
	* In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
	* because it has to have at least one slot with the key == null
	* in order to avoid infinite loops in get(), put(), remove()
	*/
	private static final int MAXIMUM_CAPACITY = 1 << 29;

	/**
	* The table, resized as necessary. Length MUST always be a power of two.
	*/
	transient Object[] table; // non-private to simplify nested class access

	/**
	* The number of key-value mappings contained in this identity hash map.
	*
	* @serial
	*/
	int size;

	/**
	* The number of modifications, to support fast-fail iterators
	*/
	transient int modCount;

	/**
	* Value representing null keys inside tables.
	*/
	static final Object NULL_KEY = new Object();

	/**
	* Use NULL_KEY for key if it is null.
	*/
	private static Object maskNull(Object key) {
	return (key == null ? NULL_KEY : key);
	}

	/**
	* Returns internal representation of null key back to caller as null.
	*/
	static final Object unmaskNull(Object key) {
	return (key == NULL_KEY ? null : key);
	}

	/**
	* Constructs a new, empty identity hash map with a default expected
	* maximum size (21).
	*/
	public IdentityHashMap() {
	init(DEFAULT_CAPACITY);
	}

	/**
	* Constructs a new, empty map with the specified expected maximum size.
	* Putting more than the expected number of key-value mappings into
	* the map may cause the internal data structure to grow, which may be
	* somewhat time-consuming.
	*
	* @param expectedMaxSize the expected maximum size of the map
	* @throws IllegalArgumentException if {@code expectedMaxSize} is negative
	*/
	public IdentityHashMap(int expectedMaxSize) {
	if (expectedMaxSize < 0)
	throw new IllegalArgumentException("expectedMaxSize is negative: "
	+ expectedMaxSize);
	init(capacity(expectedMaxSize));
	}

	/**
	* Returns the appropriate capacity for the given expected maximum size.
	* Returns the smallest power of two between MINIMUM_CAPACITY and
	* MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
	* expectedMaxSize)/2, if such a number exists. Otherwise returns
	* MAXIMUM_CAPACITY.
	*/
	private static int capacity(int expectedMaxSize) {
	// assert expectedMaxSize >= 0;
	return
	(expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
	(expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
	Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
	}

	/**
	* Initializes object to be an empty map with the specified initial
	* capacity, which is assumed to be a power of two between
	* MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
	*/
	private void init(int initCapacity) {
	// assert (initCapacity & -initCapacity) == initCapacity; // power of 2
	// assert initCapacity >= MINIMUM_CAPACITY;
	// assert initCapacity <= MAXIMUM_CAPACITY;

	table = new Object[2 * initCapacity];
	}

	/**
	* Constructs a new identity hash map containing the keys-value mappings
	* in the specified map.
	*
	* @param m the map whose mappings are to be placed into this map
	* @throws NullPointerException if the specified map is null
	*/
	public IdentityHashMap(Map<? extends K, ? extends V> m) {
	// Allow for a bit of growth
	this((int) ((1 + m.size()) * 1.1));
	putAll(m);
	}

	/**
	* Returns the number of key-value mappings in this identity hash map.
	*
	* @return the number of key-value mappings in this map
	*/
	public int size() {
	return size;
	}

	/**
	* Returns {@code true} if this identity hash map contains no key-value
	* mappings.
	*
	* @return {@code true} if this identity hash map contains no key-value
	* mappings
	*/
	public boolean isEmpty() {
	return size == 0;
	}

	/**
	* Returns index for Object x.
	*/
	private static int hash(Object x, int length) {
	int h = System.identityHashCode(x);
	// Multiply by -254 to use the hash LSB and to ensure index is even
	return ((h << 1) - (h << 8)) & (length - 1);
	}

	/**
	* Circularly traverses table of size len.
	*/
	private static int nextKeyIndex(int i, int len) {
	return (i + 2 < len ? i + 2 : 0);
	}

	/**
	* Returns the value to which the specified key is mapped,
	* or {@code null} if this map contains no mapping for the key.
	*
	* <p>More formally, if this map contains a mapping from a key
	* {@code k} to a value {@code v} such that {@code (key == k)},
	* then this method returns {@code v}; otherwise it returns
	* {@code null}. (There can be at most one such mapping.)
	*
	* <p>A return value of {@code null} does not <i>necessarily</i>
	* indicate that the map contains no mapping for the key; it's also
	* possible that the map explicitly maps the key to {@code null}.
	* The {@link #containsKey containsKey} operation may be used to
	* distinguish these two cases.
	*
	* @see #put(Object, Object)
	*/
	@SuppressWarnings("unchecked")
	public V get(Object key) {
	Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);
	while (true) {
	Object item = tab[i];
	if (item == k)
	return (V) tab[i + 1];
	if (item == null)
	return null;
	i = nextKeyIndex(i, len);
	}
	}

	/**
	* Tests whether the specified object reference is a key in this identity
	* hash map.
	*
	* @param key possible key
	* @return {@code true} if the specified object reference is a key
	* in this map
	* @see #containsValue(Object)
	*/
	public boolean containsKey(Object key) {
	Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);
	while (true) {
	Object item = tab[i];
	if (item == k)
	return true;
	if (item == null)
	return false;
	i = nextKeyIndex(i, len);
	}
	}

	/**
	* Tests whether the specified object reference is a value in this identity
	* hash map.
	*
	* @param value value whose presence in this map is to be tested
	* @return {@code true} if this map maps one or more keys to the
	* specified object reference
	* @see #containsKey(Object)
	*/
	public boolean containsValue(Object value) {
	Object[] tab = table;
	for (int i = 1; i < tab.length; i += 2)
	if (tab[i] == value && tab[i - 1] != null)
	return true;

	return false;
	}

	/**
	* Tests if the specified key-value mapping is in the map.
	*
	* @param key possible key
	* @param value possible value
	* @return {@code true} if and only if the specified key-value
	* mapping is in the map
	*/
	private boolean containsMapping(Object key, Object value) {
	Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);
	while (true) {
	Object item = tab[i];
	if (item == k)
	return tab[i + 1] == value;
	if (item == null)
	return false;
	i = nextKeyIndex(i, len);
	}
	}

	/**
	* Associates the specified value with the specified key in this identity
	* hash map. If the map previously contained a mapping for the key, the
	* old value is replaced.
	*
	* @param key the key with which the specified value is to be associated
	* @param value the value to be associated with the specified key
	* @return the previous value associated with {@code key}, or
	* {@code null} if there was no mapping for {@code key}.
	* (A {@code null} return can also indicate that the map
	* previously associated {@code null} with {@code key}.)
	* @see Object#equals(Object)
	* @see #get(Object)
	* @see #containsKey(Object)
	*/
	public V put(K key, V value) {
	final Object k = maskNull(key);

	retryAfterResize: for (;;) {
	final Object[] tab = table;
	final int len = tab.length;
	int i = hash(k, len);

	for (Object item; (item = tab[i]) != null;
	i = nextKeyIndex(i, len)) {
	if (item == k) {
	@SuppressWarnings("unchecked")
	V oldValue = (V) tab[i + 1];
	tab[i + 1] = value;
	return oldValue;
	}
	}

	final int s = size + 1;
	// Use optimized form of 3 * s.
	// Next capacity is len, 2 * current capacity.
	if (s + (s << 1) > len && resize(len))
	continue retryAfterResize;

	modCount++;
	tab[i] = k;
	tab[i + 1] = value;
	size = s;
	return null;
	}
	}

	/**
	* Resizes the table if necessary to hold given capacity.
	*
	* @param newCapacity the new capacity, must be a power of two.
	* @return whether a resize did in fact take place
	*/
	private boolean resize(int newCapacity) {
	// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
	int newLength = newCapacity * 2;

	Object[] oldTable = table;
	int oldLength = oldTable.length;
	if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
	if (size == MAXIMUM_CAPACITY - 1)
	throw new IllegalStateException("Capacity exhausted.");
	return false;
	}
	if (oldLength >= newLength)
	return false;

	Object[] newTable = new Object[newLength];

	for (int j = 0; j < oldLength; j += 2) {
	Object key = oldTable[j];
	if (key != null) {
	Object value = oldTable[j+1];
	oldTable[j] = null;
	oldTable[j+1] = null;
	int i = hash(key, newLength);
	while (newTable[i] != null)
	i = nextKeyIndex(i, newLength);
	newTable[i] = key;
	newTable[i + 1] = value;
	}
	}
	table = newTable;
	return true;
	}

	/**
	* Copies all of the mappings from the specified map to this map.
	* These mappings will replace any mappings that this map had for
	* any of the keys currently in the specified map.
	*
	* @param m mappings to be stored in this map
	* @throws NullPointerException if the specified map is null
	*/
	public void putAll(Map<? extends K, ? extends V> m) {
	int n = m.size();
	if (n == 0)
	return;
	if (n > size)
	resize(capacity(n)); // conservatively pre-expand

	for (Entry<? extends K, ? extends V> e : m.entrySet())
	put(e.getKey(), e.getValue());
	}

	/**
	* Removes the mapping for this key from this map if present.
	*
	* @param key key whose mapping is to be removed from the map
	* @return the previous value associated with {@code key}, or
	* {@code null} if there was no mapping for {@code key}.
	* (A {@code null} return can also indicate that the map
	* previously associated {@code null} with {@code key}.)
	*/
	public V remove(Object key) {
	Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);

	while (true) {
	Object item = tab[i];
	if (item == k) {
	modCount++;
	size--;
	@SuppressWarnings("unchecked")
	V oldValue = (V) tab[i + 1];
	tab[i + 1] = null;
	tab[i] = null;
	closeDeletion(i);
	return oldValue;
	}
	if (item == null)
	return null;
	i = nextKeyIndex(i, len);
	}
	}

	/**
	* Removes the specified key-value mapping from the map if it is present.
	*
	* @param key possible key
	* @param value possible value
	* @return {@code true} if and only if the specified key-value
	* mapping was in the map
	*/
	private boolean removeMapping(Object key, Object value) {
	Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);

	while (true) {
	Object item = tab[i];
	if (item == k) {
	if (tab[i + 1] != value)
	return false;
	modCount++;
	size--;
	tab[i] = null;
	tab[i + 1] = null;
	closeDeletion(i);
	return true;
	}
	if (item == null)
	return false;
	i = nextKeyIndex(i, len);
	}
	}

	/**
	* Rehash all possibly-colliding entries following a
	* deletion. This preserves the linear-probe
	* collision properties required by get, put, etc.
	*
	* @param d the index of a newly empty deleted slot
	*/
	private void closeDeletion(int d) {
	// Adapted from Knuth Section 6.4 Algorithm R
	Object[] tab = table;
	int len = tab.length;

	// Look for items to swap into newly vacated slot
	// starting at index immediately following deletion,
	// and continuing until a null slot is seen, indicating
	// the end of a run of possibly-colliding keys.
	Object item;
	for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
	i = nextKeyIndex(i, len) ) {
	// The following test triggers if the item at slot i (which
	// hashes to be at slot r) should take the spot vacated by d.
	// If so, we swap it in, and then continue with d now at the
	// newly vacated i. This process will terminate when we hit
	// the null slot at the end of this run.
	// The test is messy because we are using a circular table.
	int r = hash(item, len);
	if ((i < r && (r <= d \|\| d <= i)) \|\| (r <= d && d <= i)) {
	tab[d] = item;
	tab[d + 1] = tab[i + 1];
	tab[i] = null;
	tab[i + 1] = null;
	d = i;
	}
	}
	}

	/**
	* Removes all of the mappings from this map.
	* The map will be empty after this call returns.
	*/
	public void clear() {
	modCount++;
	Object[] tab = table;
	for (int i = 0; i < tab.length; i++)
	tab[i] = null;
	size = 0;
	}

	/**
	* Compares the specified object with this map for equality. Returns
	* {@code true} if the given object is also a map and the two maps
	* represent identical object-reference mappings. More formally, this
	* map is equal to another map {@code m} if and only if
	* {@code this.entrySet().equals(m.entrySet())}.
	*
	* <p><b>Owing to the reference-equality-based semantics of this map it is
	* possible that the symmetry and transitivity requirements of the
	* {@code Object.equals} contract may be violated if this map is compared
	* to a normal map. However, the {@code Object.equals} contract is
	* guaranteed to hold among {@code IdentityHashMap} instances.</b>
	*
	* @param o object to be compared for equality with this map
	* @return {@code true} if the specified object is equal to this map
	* @see Object#equals(Object)
	*/
	public boolean equals(Object o) {
	if (o == this) {
	return true;
	} else if (o instanceof IdentityHashMap<?, ?> m) {
	if (m.size() != size)
	return false;

	Object[] tab = m.table;
	for (int i = 0; i < tab.length; i+=2) {
	Object k = tab[i];
	if (k != null && !containsMapping(k, tab[i + 1]))
	return false;
	}
	return true;
	} else if (o instanceof Map<?, ?> m) {
	return entrySet().equals(m.entrySet());
	} else {
	return false; // o is not a Map
	}
	}

	/**
	* Returns the hash code value for this map. The hash code of a map is
	* defined to be the sum of the hash codes of each entry in the map's
	* {@code entrySet()} view. This ensures that {@code m1.equals(m2)}
	* implies that {@code m1.hashCode()==m2.hashCode()} for any two
	* {@code IdentityHashMap} instances {@code m1} and {@code m2}, as
	* required by the general contract of {@link Object#hashCode}.
	*
	* <p><b>Owing to the reference-equality-based semantics of the
	* {@code Map.Entry} instances in the set returned by this map's
	* {@code entrySet} method, it is possible that the contractual
	* requirement of {@code Object.hashCode} mentioned in the previous
	* paragraph will be violated if one of the two objects being compared is
	* an {@code IdentityHashMap} instance and the other is a normal map.</b>
	*
	* @return the hash code value for this map
	* @see Object#equals(Object)
	* @see #equals(Object)
	*/
	public int hashCode() {
	int result = 0;
	Object[] tab = table;
	for (int i = 0; i < tab.length; i +=2) {
	Object key = tab[i];
	if (key != null) {
	Object k = unmaskNull(key);
	result += System.identityHashCode(k) ^
	System.identityHashCode(tab[i + 1]);
	}
	}
	return result;
	}

	/**
	* Returns a shallow copy of this identity hash map: the keys and values
	* themselves are not cloned.
	*
	* @return a shallow copy of this map
	*/
	public Object clone() {
	try {
	IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) super.clone();
	m.entrySet = null;
	m.table = table.clone();
	return m;
	} catch (CloneNotSupportedException e) {
	throw new InternalError(e);
	}
	}

	private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
	int index = (size != 0 ? 0 : table.length); // current slot.
	int expectedModCount = modCount; // to support fast-fail
	int lastReturnedIndex = -1; // to allow remove()
	boolean indexValid; // To avoid unnecessary next computation
	Object[] traversalTable = table; // reference to main table or copy

	public boolean hasNext() {
	Object[] tab = traversalTable;
	for (int i = index; i < tab.length; i+=2) {
	Object key = tab[i];
	if (key != null) {
	index = i;
	return indexValid = true;
	}
	}
	index = tab.length;
	return false;
	}

	protected int nextIndex() {
	if (modCount != expectedModCount)
	throw new ConcurrentModificationException();
	if (!indexValid && !hasNext())
	throw new NoSuchElementException();

	indexValid = false;
	lastReturnedIndex = index;
	index += 2;
	return lastReturnedIndex;
	}

	public void remove() {
	if (lastReturnedIndex == -1)
	throw new IllegalStateException();
	if (modCount != expectedModCount)
	throw new ConcurrentModificationException();

	expectedModCount = ++modCount;
	int deletedSlot = lastReturnedIndex;
	lastReturnedIndex = -1;
	// back up index to revisit new contents after deletion
	index = deletedSlot;
	indexValid = false;

	// Removal code proceeds as in closeDeletion except that
	// it must catch the rare case where an element already
	// seen is swapped into a vacant slot that will be later
	// traversed by this iterator. We cannot allow future
	// next() calls to return it again. The likelihood of
	// this occurring under 2/3 load factor is very slim, but
	// when it does happen, we must make a copy of the rest of
	// the table to use for the rest of the traversal. Since
	// this can only happen when we are near the end of the table,
	// even in these rare cases, this is not very expensive in
	// time or space.

	Object[] tab = traversalTable;
	int len = tab.length;

	int d = deletedSlot;
	Object key = tab[d];
	tab[d] = null; // vacate the slot
	tab[d + 1] = null;

	// If traversing a copy, remove in real table.
	// We can skip gap-closure on copy.
	if (tab != IdentityHashMap.this.table) {
	IdentityHashMap.this.remove(key);
	expectedModCount = modCount;
	return;
	}

	size--;

	Object item;
	for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
	i = nextKeyIndex(i, len)) {
	int r = hash(item, len);
	// See closeDeletion for explanation of this conditional
	if ((i < r && (r <= d \|\| d <= i)) \|\|
	(r <= d && d <= i)) {

	// If we are about to swap an already-seen element
	// into a slot that may later be returned by next(),
	// then clone the rest of table for use in future
	// next() calls. It is OK that our copy will have
	// a gap in the "wrong" place, since it will never
	// be used for searching anyway.

	if (i < deletedSlot && d >= deletedSlot &&
	traversalTable == IdentityHashMap.this.table) {
	int remaining = len - deletedSlot;
	Object[] newTable = new Object[remaining];
	System.arraycopy(tab, deletedSlot,
	newTable, 0, remaining);
	traversalTable = newTable;
	index = 0;
	}

	tab[d] = item;
	tab[d + 1] = tab[i + 1];
	tab[i] = null;
	tab[i + 1] = null;
	d = i;
	}
	}
	}
	}

	private class KeyIterator extends IdentityHashMapIterator<K> {
	@SuppressWarnings("unchecked")
	public K next() {
	return (K) unmaskNull(traversalTable[nextIndex()]);
	}
	}

	private class ValueIterator extends IdentityHashMapIterator<V> {
	@SuppressWarnings("unchecked")
	public V next() {
	return (V) traversalTable[nextIndex() + 1];
	}
	}

	private class EntryIterator
	extends IdentityHashMapIterator<Map.Entry<K,V>>
	{
	private Entry lastReturnedEntry;

	public Map.Entry<K,V> next() {
	lastReturnedEntry = new Entry(nextIndex());
	return lastReturnedEntry;
	}

	public void remove() {
	lastReturnedIndex =
	((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
	super.remove();
	lastReturnedEntry.index = lastReturnedIndex;
	lastReturnedEntry = null;
	}

	private class Entry implements Map.Entry<K,V> {
	private int index;

	private Entry(int index) {
	this.index = index;
	}

	@SuppressWarnings("unchecked")
	public K getKey() {
	checkIndexForEntryUse();
	return (K) unmaskNull(traversalTable[index]);
	}

	@SuppressWarnings("unchecked")
	public V getValue() {
	checkIndexForEntryUse();
	return (V) traversalTable[index+1];
	}

	@SuppressWarnings("unchecked")
	public V setValue(V value) {
	checkIndexForEntryUse();
	V oldValue = (V) traversalTable[index+1];
	traversalTable[index+1] = value;
	// if shadowing, force into main table
	if (traversalTable != IdentityHashMap.this.table)
	put((K) traversalTable[index], value);
	return oldValue;
	}

	public boolean equals(Object o) {
	if (index < 0)
	return super.equals(o);

	return o instanceof Map.Entry<?, ?> e
	&& e.getKey() == unmaskNull(traversalTable[index])
	&& e.getValue() == traversalTable[index+1];
	}

	public int hashCode() {
	if (lastReturnedIndex < 0)
	return super.hashCode();

	return (System.identityHashCode(unmaskNull(traversalTable[index])) ^
	System.identityHashCode(traversalTable[index+1]));
	}

	public String toString() {
	if (index < 0)
	return super.toString();

	return (unmaskNull(traversalTable[index]) + "="
	+ traversalTable[index+1]);
	}

	private void checkIndexForEntryUse() {
	if (index < 0)
	throw new IllegalStateException("Entry was removed");
	}
	}
	}

	// Views

	/**
	* This field is initialized to contain an instance of the entry set
	* view the first time this view is requested. The view is stateless,
	* so there's no reason to create more than one.
	*/
	private transient Set<Map.Entry<K,V>> entrySet;

	/**
	* Returns an identity-based set view of the keys contained in this map.
	* The set is backed by the map, so changes to the map are reflected in
	* the set, and vice-versa. If the map is modified while an iteration
	* over the set is in progress, the results of the iteration are
	* undefined. The set supports element removal, which removes the
	* corresponding mapping from the map, via the {@code Iterator.remove},
	* {@code Set.remove}, {@code removeAll}, {@code retainAll}, and
	* {@code clear} methods. It does not support the {@code add} or
	* {@code addAll} methods.
	*
	* <p><b>While the object returned by this method implements the
	* {@code Set} interface, it does <i>not</i> obey {@code Set's} general
	* contract. Like its backing map, the set returned by this method
	* defines element equality as reference-equality rather than
	* object-equality. This affects the behavior of its {@code contains},
	* {@code remove}, {@code containsAll}, {@code equals}, and
	* {@code hashCode} methods.</b>
	*
	* <p><b>The {@code equals} method of the returned set returns {@code true}
	* only if the specified object is a set containing exactly the same
	* object references as the returned set. The symmetry and transitivity
	* requirements of the {@code Object.equals} contract may be violated if
	* the set returned by this method is compared to a normal set. However,
	* the {@code Object.equals} contract is guaranteed to hold among sets
	* returned by this method.</b>
	*
	* <p>The {@code hashCode} method of the returned set returns the sum of
	* the <i>identity hashcodes</i> of the elements in the set, rather than
	* the sum of their hashcodes. This is mandated by the change in the
	* semantics of the {@code equals} method, in order to enforce the
	* general contract of the {@code Object.hashCode} method among sets
	* returned by this method.
	*
	* @return an identity-based set view of the keys contained in this map
	* @see Object#equals(Object)
	* @see System#identityHashCode(Object)
	*/
	public Set<K> keySet() {
	Set<K> ks = keySet;
	if (ks == null) {
	ks = new KeySet();
	keySet = ks;
	}
	return ks;
	}

	private class KeySet extends AbstractSet<K> {
	public Iterator<K> iterator() {
	return new KeyIterator();
	}
	public int size() {
	return size;
	}
	public boolean contains(Object o) {
	return containsKey(o);
	}
	public boolean remove(Object o) {
	int oldSize = size;
	IdentityHashMap.this.remove(o);
	return size != oldSize;
	}
	/*
	* Must revert from AbstractSet's impl to AbstractCollection's, as
	* the former contains an optimization that results in incorrect
	* behavior when c is a smaller "normal" (non-identity-based) Set.
	*/
	public boolean removeAll(Collection<?> c) {
	Objects.requireNonNull(c);
	boolean modified = false;
	for (Iterator<K> i = iterator(); i.hasNext(); ) {
	if (c.contains(i.next())) {
	i.remove();
	modified = true;
	}
	}
	return modified;
	}
	public void clear() {
	IdentityHashMap.this.clear();
	}
	public int hashCode() {
	int result = 0;
	for (K key : this)
	result += System.identityHashCode(key);
	return result;
	}
	public Object[] toArray() {
	return toArray(new Object[0]);
	}
	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
	int expectedModCount = modCount;
	int size = size();
	if (a.length < size)
	a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
	Object[] tab = table;
	int ti = 0;
	for (int si = 0; si < tab.length; si += 2) {
	Object key;
	if ((key = tab[si]) != null) { // key present ?
	// more elements than expected -> concurrent modification from other thread
	if (ti >= size) {
	throw new ConcurrentModificationException();
	}
	a[ti++] = (T) unmaskNull(key); // unmask key
	}
	}
	// fewer elements than expected or concurrent modification from other thread detected
	if (ti < size \|\| expectedModCount != modCount) {
	throw new ConcurrentModificationException();
	}
	// final null marker as per spec
	if (ti < a.length) {
	a[ti] = null;
	}
	return a;
	}

	public Spliterator<K> spliterator() {
	return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
	}
	}

	/**
	* Returns a {@link Collection} view of the values contained in this map.
	* The collection is backed by the map, so changes to the map are
	* reflected in the collection, and vice-versa. If the map is
	* modified while an iteration over the collection is in progress,
	* the results of the iteration are undefined. The collection
	* supports element removal, which removes the corresponding
	* mapping from the map, via the {@code Iterator.remove},
	* {@code Collection.remove}, {@code removeAll},
	* {@code retainAll} and {@code clear} methods. It does not
	* support the {@code add} or {@code addAll} methods.
	*
	* <p><b>While the object returned by this method implements the
	* {@code Collection} interface, it does <i>not</i> obey
	* {@code Collection's} general contract. Like its backing map,
	* the collection returned by this method defines element equality as
	* reference-equality rather than object-equality. This affects the
	* behavior of its {@code contains}, {@code remove} and
	* {@code containsAll} methods.</b>
	*/
	public Collection<V> values() {
	Collection<V> vs = values;
	if (vs == null) {
	vs = new Values();
	values = vs;
	}
	return vs;
	}

	private class Values extends AbstractCollection<V> {
	public Iterator<V> iterator() {
	return new ValueIterator();
	}
	public int size() {
	return size;
	}
	public boolean contains(Object o) {
	return containsValue(o);
	}
	public boolean remove(Object o) {
	for (Iterator<V> i = iterator(); i.hasNext(); ) {
	if (i.next() == o) {
	i.remove();
	return true;
	}
	}
	return false;
	}
	public void clear() {
	IdentityHashMap.this.clear();
	}
	public Object[] toArray() {
	return toArray(new Object[0]);
	}
	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
	int expectedModCount = modCount;
	int size = size();
	if (a.length < size)
	a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
	Object[] tab = table;
	int ti = 0;
	for (int si = 0; si < tab.length; si += 2) {
	if (tab[si] != null) { // key present ?
	// more elements than expected -> concurrent modification from other thread
	if (ti >= size) {
	throw new ConcurrentModificationException();
	}
	a[ti++] = (T) tab[si+1]; // copy value
	}
	}
	// fewer elements than expected or concurrent modification from other thread detected
	if (ti < size \|\| expectedModCount != modCount) {
	throw new ConcurrentModificationException();
	}
	// final null marker as per spec
	if (ti < a.length) {
	a[ti] = null;
	}
	return a;
	}

	public Spliterator<V> spliterator() {
	return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
	}
	}

	/**
	* Returns a {@link Set} view of the mappings contained in this map.
	* Each element in the returned set is a reference-equality-based
	* {@code Map.Entry}. The set is backed by the map, so changes
	* to the map are reflected in the set, and vice-versa. If the
	* map is modified while an iteration over the set is in progress,
	* the results of the iteration are undefined. The set supports
	* element removal, which removes the corresponding mapping from
	* the map, via the {@code Iterator.remove}, {@code Set.remove},
	* {@code removeAll}, {@code retainAll} and {@code clear}
	* methods. It does not support the {@code add} or
	* {@code addAll} methods.
	*
	* <p>Like the backing map, the {@code Map.Entry} objects in the set
	* returned by this method define key and value equality as
	* reference-equality rather than object-equality. This affects the
	* behavior of the {@code equals} and {@code hashCode} methods of these
	* {@code Map.Entry} objects. A reference-equality based {@code Map.Entry
	* e} is equal to an object {@code o} if and only if {@code o} is a
	* {@code Map.Entry} and {@code e.getKey()==o.getKey() &&
	* e.getValue()==o.getValue()}. To accommodate these equals
	* semantics, the {@code hashCode} method returns
	* {@code System.identityHashCode(e.getKey()) ^
	* System.identityHashCode(e.getValue())}.
	*
	* <p><b>Owing to the reference-equality-based semantics of the
	* {@code Map.Entry} instances in the set returned by this method,
	* it is possible that the symmetry and transitivity requirements of
	* the {@link Object#equals(Object)} contract may be violated if any of
	* the entries in the set is compared to a normal map entry, or if
	* the set returned by this method is compared to a set of normal map
	* entries (such as would be returned by a call to this method on a normal
	* map). However, the {@code Object.equals} contract is guaranteed to
	* hold among identity-based map entries, and among sets of such entries.
	* </b>
	*
	* @return a set view of the identity-mappings contained in this map
	*/
	public Set<Map.Entry<K,V>> entrySet() {
	Set<Map.Entry<K,V>> es = entrySet;
	if (es != null)
	return es;
	else
	return entrySet = new EntrySet();
	}

	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
	public Iterator<Map.Entry<K,V>> iterator() {
	return new EntryIterator();
	}
	public boolean contains(Object o) {
	return o instanceof Entry<?, ?> entry
	&& containsMapping(entry.getKey(), entry.getValue());
	}
	public boolean remove(Object o) {
	return o instanceof Entry<?, ?> entry
	&& removeMapping(entry.getKey(), entry.getValue());
	}
	public int size() {
	return size;
	}
	public void clear() {
	IdentityHashMap.this.clear();
	}
	/*
	* Must revert from AbstractSet's impl to AbstractCollection's, as
	* the former contains an optimization that results in incorrect
	* behavior when c is a smaller "normal" (non-identity-based) Set.
	*/
	public boolean removeAll(Collection<?> c) {
	Objects.requireNonNull(c);
	boolean modified = false;
	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
	if (c.contains(i.next())) {
	i.remove();
	modified = true;
	}
	}
	return modified;
	}

	public Object[] toArray() {
	return toArray(new Object[0]);
	}

	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
	int expectedModCount = modCount;
	int size = size();
	if (a.length < size)
	a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
	Object[] tab = table;
	int ti = 0;
	for (int si = 0; si < tab.length; si += 2) {
	Object key;
	if ((key = tab[si]) != null) { // key present ?
	// more elements than expected -> concurrent modification from other thread
	if (ti >= size) {
	throw new ConcurrentModificationException();
	}
	a[ti++] = (T) new AbstractMap.SimpleEntry<>(unmaskNull(key), tab[si + 1]);
	}
	}
	// fewer elements than expected or concurrent modification from other thread detected
	if (ti < size \|\| expectedModCount != modCount) {
	throw new ConcurrentModificationException();
	}
	// final null marker as per spec
	if (ti < a.length) {
	a[ti] = null;
	}
	return a;
	}

	public Spliterator<Map.Entry<K,V>> spliterator() {
	return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
	}
	}

	@java.io.Serial
	private static final long serialVersionUID = 8188218128353913216L;

	/**
	* Saves the state of the {@code IdentityHashMap} instance to a stream
	* (i.e., serializes it).
	*
	* @serialData The <i>size</i> of the HashMap (the number of key-value
	* mappings) ({@code int}), followed by the key (Object) and
	* value (Object) for each key-value mapping represented by the
	* IdentityHashMap. The key-value mappings are emitted in no
	* particular order.
	*/
	@java.io.Serial
	private void writeObject(java.io.ObjectOutputStream s)
	throws java.io.IOException {
	// Write out and any hidden stuff
	s.defaultWriteObject();

	// Write out size (number of Mappings)
	s.writeInt(size);

	// Write out keys and values (alternating)
	Object[] tab = table;
	for (int i = 0; i < tab.length; i += 2) {
	Object key = tab[i];
	if (key != null) {
	s.writeObject(unmaskNull(key));
	s.writeObject(tab[i + 1]);
	}
	}
	}

	/**
	* Reconstitutes the {@code IdentityHashMap} instance from a stream (i.e.,
	* deserializes it).
	*/
	@java.io.Serial
	private void readObject(java.io.ObjectInputStream s)
	throws java.io.IOException, ClassNotFoundException {
	// Read in any hidden stuff
	s.defaultReadObject();

	// Read in size (number of Mappings)
	int size = s.readInt();
	if (size < 0)
	throw new java.io.StreamCorruptedException
	("Illegal mappings count: " + size);
	int cap = capacity(size);
	SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, cap);
	init(cap);

	// Read the keys and values, and put the mappings in the table
	for (int i=0; i<size; i++) {
	@SuppressWarnings("unchecked")
	K key = (K) s.readObject();
	@SuppressWarnings("unchecked")
	V value = (V) s.readObject();
	putForCreate(key, value);
	}
	}

	/**
	* The put method for readObject. It does not resize the table,
	* update modCount, etc.
	*/
	private void putForCreate(K key, V value)
	throws java.io.StreamCorruptedException
	{
	Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);

	Object item;
	while ( (item = tab[i]) != null) {
	if (item == k)
	throw new java.io.StreamCorruptedException();
	i = nextKeyIndex(i, len);
	}
	tab[i] = k;
	tab[i + 1] = value;
	}

	@SuppressWarnings("unchecked")
	@Override
	public void forEach(BiConsumer<? super K, ? super V> action) {
	Objects.requireNonNull(action);
	int expectedModCount = modCount;

	Object[] t = table;
	for (int index = 0; index < t.length; index += 2) {
	Object k = t[index];
	if (k != null) {
	action.accept((K) unmaskNull(k), (V) t[index + 1]);
	}

	if (modCount != expectedModCount) {
	throw new ConcurrentModificationException();
	}
	}
	}

	@SuppressWarnings("unchecked")
	@Override
	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
	Objects.requireNonNull(function);
	int expectedModCount = modCount;

	Object[] t = table;
	for (int index = 0; index < t.length; index += 2) {
	Object k = t[index];
	if (k != null) {
	t[index + 1] = function.apply((K) unmaskNull(k), (V) t[index + 1]);
	}

	if (modCount != expectedModCount) {
	throw new ConcurrentModificationException();
	}
	}
	}

	/**
	* Similar form as array-based Spliterators, but skips blank elements,
	* and guestimates size as decreasing by half per split.
	*/
	static class IdentityHashMapSpliterator<K,V> {
	final IdentityHashMap<K,V> map;
	int index; // current index, modified on advance/split
	int fence; // -1 until first use; then one past last index
	int est; // size estimate
	int expectedModCount; // initialized when fence set

	IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
	int fence, int est, int expectedModCount) {
	this.map = map;
	this.index = origin;
	this.fence = fence;
	this.est = est;
	this.expectedModCount = expectedModCount;
	}

	final int getFence() { // initialize fence and size on first use
	int hi;
	if ((hi = fence) < 0) {
	est = map.size;
	expectedModCount = map.modCount;
	hi = fence = map.table.length;
	}
	return hi;
	}

	public final long estimateSize() {
	getFence(); // force init
	return (long) est;
	}
	}

	static final class KeySpliterator<K,V>
	extends IdentityHashMapSpliterator<K,V>
	implements Spliterator<K> {
	KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
	int expectedModCount) {
	super(map, origin, fence, est, expectedModCount);
	}

	public KeySpliterator<K,V> trySplit() {
	int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
	return (lo >= mid) ? null :
	new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
	expectedModCount);
	}

	@SuppressWarnings("unchecked")
	public void forEachRemaining(Consumer<? super K> action) {
	if (action == null)
	throw new NullPointerException();
	int i, hi, mc; Object key;
	IdentityHashMap<K,V> m; Object[] a;
	if ((m = map) != null && (a = m.table) != null &&
	(i = index) >= 0 && (index = hi = getFence()) <= a.length) {
	for (; i < hi; i += 2) {
	if ((key = a[i]) != null)
	action.accept((K)unmaskNull(key));
	}
	if (m.modCount == expectedModCount)
	return;
	}
	throw new ConcurrentModificationException();
	}

	@SuppressWarnings("unchecked")
	public boolean tryAdvance(Consumer<? super K> action) {
	if (action == null)
	throw new NullPointerException();
	Object[] a = map.table;
	int hi = getFence();
	while (index < hi) {
	Object key = a[index];
	index += 2;
	if (key != null) {
	action.accept((K)unmaskNull(key));
	if (map.modCount != expectedModCount)
	throw new ConcurrentModificationException();
	return true;
	}
	}
	return false;
	}

	public int characteristics() {
	return (fence < 0 \|\| est == map.size ? SIZED : 0) \| Spliterator.DISTINCT;
	}
	}

	static final class ValueSpliterator<K,V>
	extends IdentityHashMapSpliterator<K,V>
	implements Spliterator<V> {
	ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
	int expectedModCount) {
	super(m, origin, fence, est, expectedModCount);
	}

	public ValueSpliterator<K,V> trySplit() {
	int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
	return (lo >= mid) ? null :
	new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
	expectedModCount);
	}

	public void forEachRemaining(Consumer<? super V> action) {
	if (action == null)
	throw new NullPointerException();
	int i, hi, mc;
	IdentityHashMap<K,V> m; Object[] a;
	if ((m = map) != null && (a = m.table) != null &&
	(i = index) >= 0 && (index = hi = getFence()) <= a.length) {
	for (; i < hi; i += 2) {
	if (a[i] != null) {
	@SuppressWarnings("unchecked") V v = (V)a[i+1];
	action.accept(v);
	}
	}
	if (m.modCount == expectedModCount)
	return;
	}
	throw new ConcurrentModificationException();
	}

	public boolean tryAdvance(Consumer<? super V> action) {
	if (action == null)
	throw new NullPointerException();
	Object[] a = map.table;
	int hi = getFence();
	while (index < hi) {
	Object key = a[index];
	@SuppressWarnings("unchecked") V v = (V)a[index+1];
	index += 2;
	if (key != null) {
	action.accept(v);
	if (map.modCount != expectedModCount)
	throw new ConcurrentModificationException();
	return true;
	}
	}
	return false;
	}

	public int characteristics() {
	return (fence < 0 \|\| est == map.size ? SIZED : 0);
	}

	}

	static final class EntrySpliterator<K,V>
	extends IdentityHashMapSpliterator<K,V>
	implements Spliterator<Map.Entry<K,V>> {
	EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
	int expectedModCount) {
	super(m, origin, fence, est, expectedModCount);
	}

	public EntrySpliterator<K,V> trySplit() {
	int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
	return (lo >= mid) ? null :
	new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
	expectedModCount);
	}

	public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
	if (action == null)
	throw new NullPointerException();
	int i, hi, mc;
	IdentityHashMap<K,V> m; Object[] a;
	if ((m = map) != null && (a = m.table) != null &&
	(i = index) >= 0 && (index = hi = getFence()) <= a.length) {
	for (; i < hi; i += 2) {
	Object key = a[i];
	if (key != null) {
	@SuppressWarnings("unchecked") K k =
	(K)unmaskNull(key);
	@SuppressWarnings("unchecked") V v = (V)a[i+1];
	action.accept
	(new AbstractMap.SimpleImmutableEntry<>(k, v));

	}
	}
	if (m.modCount == expectedModCount)
	return;
	}
	throw new ConcurrentModificationException();
	}

	public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
	if (action == null)
	throw new NullPointerException();
	Object[] a = map.table;
	int hi = getFence();
	while (index < hi) {
	Object key = a[index];
	@SuppressWarnings("unchecked") V v = (V)a[index+1];
	index += 2;
	if (key != null) {
	@SuppressWarnings("unchecked") K k =
	(K)unmaskNull(key);
	action.accept
	(new AbstractMap.SimpleImmutableEntry<>(k, v));
	if (map.modCount != expectedModCount)
	throw new ConcurrentModificationException();
	return true;
	}
	}
	return false;
	}

	public int characteristics() {
	return (fence < 0 \|\| est == map.size ? SIZED : 0) \| Spliterator.DISTINCT;
	}
	}

	}

Back to index...