- * - * WARNING: This is not a general purpose map. Because it uses - * System.identityHashCode and ==, instead of hashCode and equals, for - * comparison, it violated Map's general contract, and may cause - * undefined behavior when compared to other maps which are not - * IdentityHashMaps. This is designed only for the rare cases when - * identity semantics are needed. An example use is - * topology-preserving graph transformations, such as deep cloning, - * or as proxy object mapping such as in debugging. - *
- *
- * This map permits null keys and values, and does not
- * guarantee that elements will stay in the same order over time. The
- * basic operations (get and put) take
- * constant time, provided System.identityHashCode is decent. You can
- * tune the behavior by specifying the expected maximum size. As more
- * elements are added, the map may need to allocate a larger table,
- * which can be expensive.
- *
- *
- * This implementation is unsynchronized. If you want multi-thread
- * access to be consistent, you must synchronize it, perhaps by using
- *
- *
- * The semantics of this set, and of its contained entries, are
- * different from the contract of Set and Map.Entry in order to make
- * IdentityHashMap work. This means that while you can compare these
- * objects between IdentityHashMaps, comparing them with regular sets
- * or entries is likely to have undefined behavior. The entries
- * in this set are reference-based, rather than the normal object
- * equality. Therefore,
- *
- * Note that the iterators for all three views, from keySet(), entrySet(),
- * and values(), traverse the Map in the same sequence.
- *
- * @return a set view of the entries
- * @see #keySet()
- * @see #values()
- * @see Map.Entry
- */
- public Set entrySet()
- {
- if (entries == null)
- entries = new AbstractSet()
- {
- public int size()
- {
- return size;
- }
-
- public Iterator iterator()
- {
- return new IdentityIterator(ENTRIES);
- }
-
- public void clear()
- {
- IdentityHashMap.this.clear();
- }
-
- public boolean contains(Object o)
- {
- if (! (o instanceof Map.Entry))
- return false;
- Map.Entry m = (Map.Entry) o;
- return m.getValue() == table[hash(m.getKey()) + 1];
- }
-
- public int hashCode()
- {
- return IdentityHashMap.this.hashCode();
- }
-
- public boolean remove(Object o)
- {
- if (! (o instanceof Map.Entry))
- return false;
- Object key = ((Map.Entry) o).getKey();
- int h = hash(key);
- if (table[h] == key)
- {
- size--;
- modCount++;
- table[h] = tombstone;
- table[h + 1] = tombstone;
- return true;
- }
- return false;
- }
- };
- return entries;
- }
-
- /**
- * Compares two maps for equality. This returns true only if both maps
- * have the same reference-identity comparisons. While this returns
- *
- *
- * The semantics of this set are different from the contract of Set
- * in order to make IdentityHashMap work. This means that while you can
- * compare these objects between IdentityHashMaps, comparing them with
- * regular sets is likely to have undefined behavior. The hashCode
- * of the set is the sum of the identity hash codes, instead of the
- * regular hashCodes, and equality is determined by reference instead
- * of by the equals method.
- *
- *
- * @return a set view of the keys
- * @see #values()
- * @see #entrySet()
- */
- public Set keySet()
- {
- if (keys == null)
- keys = new AbstractSet()
- {
- public int size()
- {
- return size;
- }
-
- public Iterator iterator()
- {
- return new IdentityIterator(KEYS);
- }
-
- public void clear()
- {
- IdentityHashMap.this.clear();
- }
-
- public boolean contains(Object o)
- {
- return containsKey(o);
- }
-
- public int hashCode()
- {
- int hash = 0;
- for (int i = table.length - 2; i >= 0; i -= 2)
- {
- Object key = table[i];
- if (key == emptyslot || key == tombstone)
- continue;
- hash += System.identityHashCode(key);
- }
- return hash;
-
- }
-
- public boolean remove(Object o)
- {
- int h = hash(o);
- if (table[h] == o)
- {
- size--;
- modCount++;
- table[h] = tombstone;
- table[h + 1] = tombstone;
- return true;
- }
- return false;
- }
- };
- return keys;
- }
-
- /**
- * Puts the supplied value into the Map, mapped by the supplied key.
- * The value may be retrieved by any object which
- *
- * The semantics of this set are different from the contract of
- * Collection in order to make IdentityHashMap work. This means that
- * while you can compare these objects between IdentityHashMaps, comparing
- * them with regular sets is likely to have undefined behavior.
- * Likewise, contains and remove go by == instead of equals().
- *
- *
- * @return a bag view of the values
- * @see #keySet()
- * @see #entrySet()
- */
- public Collection values()
- {
- if (values == null)
- values = new AbstractCollection()
- {
- public int size()
- {
- return size;
- }
-
- public Iterator iterator()
- {
- return new IdentityIterator(VALUES);
- }
-
- public void clear()
- {
- IdentityHashMap.this.clear();
- }
-
- public boolean remove(Object o)
- {
- for (int i = table.length - 1; i > 0; i -= 2)
- if (table[i] == o)
- {
- modCount++;
- table[i - 1] = tombstone;
- table[i] = tombstone;
- size--;
- return true;
- }
- return false;
- }
- };
- return values;
- }
-
- /**
- * Helper method which computes the hash code, then traverses the table
- * until it finds the key, or the spot where the key would go.
- *
- * @param key the key to check
- * @return the index where the key belongs
- * @see #IdentityHashMap(int)
- * @see #put(Object, Object)
- */
- // Package visible for use by nested classes.
- int hash(Object key)
- {
- // Implementation note: it is feasible for the table to have no
- // emptyslots, if it is full with entries and tombstones, so we must
- // remember where we started. If we encounter the key or an emptyslot,
- // we are done. If we encounter a tombstone, the key may still be in
- // the array. If we don't encounter the key, we use the first emptyslot
- // or tombstone we encountered as the location where the key would go.
- // By requiring at least 2 key/value slots, and rehashing at 75%
- // capacity, we guarantee that there will always be either an emptyslot
- // or a tombstone somewhere in the table.
- int h = 2 * Math.abs(System.identityHashCode(key) % (table.length / 2));
- int del = -1;
- int save = h;
-
- do
- {
- if (table[h] == key)
- return h;
- if (table[h] == emptyslot)
- break;
- if (table[h] == tombstone && del < 0)
- del = h;
- h -= 2;
- if (h < 0)
- h = table.length - 2;
- }
- while (h != save);
-
- return del < 0 ? h : del;
- }
-
- /**
- * This class allows parameterized iteration over IdentityHashMaps. Based
- * on its construction, it returns the key or value of a mapping, or
- * creates the appropriate Map.Entry object with the correct fail-fast
- * semantics and identity comparisons.
- *
- * @author Tom Tromey Collections.synchronizedMap(new IdentityHashMap(...));.
- * The iterators are fail-fast, meaning that a structural modification
- * made to the map outside of an iterator's remove method cause the
- * iterator, and in the case of the entrySet, the Map.Entry, to
- * fail with a {@link ConcurrentModificationException}.
- *
- * @author Tom Tromey entry == key instead of
- * entry == null ? key == null : entry.equals(key).
- *
- * @param key the key to look for
- * @return true if the key is contained in the map
- * @see #containsValue(Object)
- * @see #get(Object)
- */
- public boolean containsKey(Object key)
- {
- return key == table[hash(key)];
- }
-
- /**
- * Returns true if this HashMap contains the value. Unlike normal maps,
- * this test uses entry == value instead of
- * entry == null ? value == null : entry.equals(value).
- *
- * @param value the value to search for in this HashMap
- * @return true if at least one key maps to the value
- * @see #containsKey(Object)
- */
- public boolean containsValue(Object value)
- {
- for (int i = table.length - 1; i > 0; i -= 2)
- if (table[i] == value)
- return true;
- return false;
- }
-
- /**
- * Returns a "set view" of this Map's entries. The set is backed by
- * the Map, so changes in one show up in the other. The set supports
- * element removal, but not element addition.
- * e1.equals(e2) returns
- * e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue(),
- * and e.hashCode() returns
- * System.identityHashCode(e.getKey()) ^
- * System.identityHashCode(e.getValue()).
- * this.entrySet().equals(m.entrySet()) as specified by Map,
- * this will not work with normal maps, since the entry set compares
- * with == instead of .equals.
- *
- * @param o the object to compare to
- * @return true if it is equal
- */
- public boolean equals(Object o)
- {
- // Why did Sun specify this one? The superclass does the right thing.
- return super.equals(o);
- }
-
- /**
- * Return the value in this Map associated with the supplied key,
- * or null
if the key maps to nothing. NOTE: Since the value
- * could also be null, you must use containsKey to see if this key
- * actually maps to something. Unlike normal maps, this tests for the key
- * with entry == key instead of
- * entry == null ? key == null : entry.equals(key).
- *
- * @param key the key for which to fetch an associated value
- * @return what the key maps to, if present
- * @see #put(Object, Object)
- * @see #containsKey(Object)
- */
- public Object get(Object key)
- {
- int h = hash(key);
- return table[h] == key ? table[h + 1] : null;
- }
-
- /**
- * Returns the hashcode of this map. This guarantees that two
- * IdentityHashMaps that compare with equals() will have the same hash code,
- * but may break with comparison to normal maps since it uses
- * System.identityHashCode() instead of hashCode().
- *
- * @return the hash code
- */
- public int hashCode()
- {
- int hash = 0;
- for (int i = table.length - 2; i >= 0; i -= 2)
- {
- Object key = table[i];
- if (key == emptyslot || key == tombstone)
- continue;
- hash += (System.identityHashCode(key)
- ^ System.identityHashCode(table[i + 1]));
- }
- return hash;
- }
-
- /**
- * Returns true if there are no key-value mappings currently in this Map
- * @return size() == 0
- */
- public boolean isEmpty()
- {
- return size == 0;
- }
-
- /**
- * Returns a "set view" of this Map's keys. The set is backed by the
- * Map, so changes in one show up in the other. The set supports
- * element removal, but not element addition.
- * equals()
- * this key. NOTE: Since the prior value could also be null, you must
- * first use containsKey if you want to see if you are replacing the
- * key's mapping. Unlike normal maps, this tests for the key
- * with entry == key instead of
- * entry == null ? key == null : entry.equals(key).
- *
- * @param key the key used to locate the value
- * @param value the value to be stored in the HashMap
- * @return the prior mapping of the key, or null if there was none
- * @see #get(Object)
- */
- public Object put(Object key, Object value)
- {
- // Rehash if the load factor is too high.
- if (size > threshold)
- {
- Object[] old = table;
- // This isn't necessarily prime, but it is an odd number of key/value
- // slots, which has a higher probability of fewer collisions.
- table = new Object[old.length * 2 + 2];
- Arrays.fill(table, emptyslot);
- size = 0;
- threshold = (table.length / 2) / 4 * 3;
-
- for (int i = old.length - 2; i >= 0; i -= 2)
- {
- Object oldkey = old[i];
- if (oldkey != tombstone && oldkey != emptyslot)
- // Just use put. This isn't very efficient, but it is ok.
- put(oldkey, old[i + 1]);
- }
- }
-
- int h = hash(key);
- if (table[h] == key)
- {
- Object r = table[h + 1];
- table[h + 1] = value;
- return r;
- }
-
- // At this point, we add a new mapping.
- modCount++;
- size++;
- table[h] = key;
- table[h + 1] = value;
- return null;
- }
-
- /**
- * Copies all of the mappings from the specified map to this. If a key
- * is already in this map, its value is replaced.
- *
- * @param m the map to copy
- * @throws NullPointerException if m is null
- */
- public void putAll(Map m)
- {
- // Why did Sun specify this one? The superclass does the right thing.
- super.putAll(m);
- }
-
- /**
- * Removes from the HashMap and returns the value which is mapped by the
- * supplied key. If the key maps to nothing, then the HashMap remains
- * unchanged, and null
is returned. NOTE: Since the value
- * could also be null, you must use containsKey to see if you are
- * actually removing a mapping. Unlike normal maps, this tests for the
- * key with entry == key instead of
- * entry == null ? key == null : entry.equals(key).
- *
- * @param key the key used to locate the value to remove
- * @return whatever the key mapped to, if present
- */
- public Object remove(Object key)
- {
- int h = hash(key);
- if (table[h] == key)
- {
- modCount++;
- size--;
- Object r = table[h + 1];
- table[h] = tombstone;
- table[h + 1] = tombstone;
- return r;
- }
- return null;
- }
-
- /**
- * Returns the number of kay-value mappings currently in this Map
- * @return the size
- */
- public int size()
- {
- return size;
- }
-
- /**
- * Returns a "collection view" (or "bag view") of this Map's values.
- * The collection is backed by the Map, so changes in one show up
- * in the other. The collection supports element removal, but not element
- * addition.
- * next()
method.
- * @throws ConcurrentModificationException if the Map was modified
- * @throws IllegalStateException if called when there is no last element
- */
- public void remove()
- {
- if (knownMod != modCount)
- throw new ConcurrentModificationException();
- if (loc == table.length || table[loc] == tombstone)
- throw new IllegalStateException();
- modCount++;
- size--;
- table[loc] = tombstone;
- table[loc + 1] = tombstone;
- knownMod++;
- }
- } // class IdentityIterator
-
- /**
- * This class provides Map.Entry objects for IdentityHashMaps. The entry
- * is fail-fast, and will throw a ConcurrentModificationException if
- * the underlying map is modified, or if remove is called on the iterator
- * that generated this object. It is identity based, so it violates
- * the general contract of Map.Entry, and is probably unsuitable for
- * comparison to normal maps; but it works among other IdentityHashMaps.
- *
- * @author Eric Blake