libjava/java/util/IdentityHashMap.java

   1 /* IdentityHashMap.java -- a class providing a hashtable data structure,
   2    mapping Object --> Object, which uses object identity for hashing.
   3    Copyright (C) 2001, 2002, 2004, 2005  Free Software Foundation, Inc.
   4
   5 This file is part of GNU Classpath.
   6
   7 GNU Classpath is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU Classpath is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Classpath; see the file COPYING.  If not, write to the
  19 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  20 02111-1307 USA.
  21
  22 Linking this library statically or dynamically with other modules is
  23 making a combined work based on this library.  Thus, the terms and
  24 conditions of the GNU General Public License cover the whole
  25 combination.
  26
  27 As a special exception, the copyright holders of this library give you
  28 permission to link this library with independent modules to produce an
  29 executable, regardless of the license terms of these independent
  30 modules, and to copy and distribute the resulting executable under
  31 terms of your choice, provided that you also meet, for each linked
  32 independent module, the terms and conditions of the license of that
  33 module.  An independent module is a module which is not derived from
  34 or based on this library.  If you modify this library, you may extend
  35 this exception to your version of the library, but you are not
  36 obligated to do so.  If you do not wish to do so, delete this
  37 exception statement from your version. */
  38
  39 package java.util;
  40
  41 import java.io.IOException;
  42 import java.io.ObjectInputStream;
  43 import java.io.ObjectOutputStream;
  44 import java.io.Serializable;
  45
  46 /**
  47  * This class provides a hashtable-backed implementation of the
  48  * Map interface, but uses object identity to do its hashing.  In fact,
  49  * it uses object identity for comparing values, as well. It uses a
  50  * linear-probe hash table, which may have faster performance
  51  * than the chaining employed by HashMap.
  52  * <p>
  53  *
  54  * <em>WARNING: This is not a general purpose map. Because it uses
  55  * System.identityHashCode and ==, instead of hashCode and equals, for
  56  * comparison, it violated Map's general contract, and may cause
  57  * undefined behavior when compared to other maps which are not
  58  * IdentityHashMaps.  This is designed only for the rare cases when
  59  * identity semantics are needed.</em> An example use is
  60  * topology-preserving graph transformations, such as deep cloning,
  61  * or as proxy object mapping such as in debugging.
  62  * <p>
  63  *
  64  * This map permits <code>null</code> keys and values, and does not
  65  * guarantee that elements will stay in the same order over time. The
  66  * basic operations (<code>get</code> and <code>put</code>) take
  67  * constant time, provided System.identityHashCode is decent. You can
  68  * tune the behavior by specifying the expected maximum size. As more
  69  * elements are added, the map may need to allocate a larger table,
  70  * which can be expensive.
  71  * <p>
  72  *
  73  * This implementation is unsynchronized.  If you want multi-thread
  74  * access to be consistent, you must synchronize it, perhaps by using
  75  * <code>Collections.synchronizedMap(new IdentityHashMap(...));</code>.
  76  * The iterators are <i>fail-fast</i>, meaning that a structural modification
  77  * made to the map outside of an iterator's remove method cause the
  78  * iterator, and in the case of the entrySet, the Map.Entry, to
  79  * fail with a {@link ConcurrentModificationException}.
  80  *
  81  * @author Tom Tromey (tromey@redhat.com)
  82  * @author Eric Blake (ebb9@email.byu.edu)
  83  * @see System#identityHashCode(Object)
  84  * @see Collection
  85  * @see Map
  86  * @see HashMap
  87  * @see TreeMap
  88  * @see LinkedHashMap
  89  * @see WeakHashMap
  90  * @since 1.4
  91  * @status updated to 1.4
  92  */
  93 public class IdentityHashMap extends AbstractMap
  94   implements Map, Serializable, Cloneable
  95 {
  96   /** The default capacity. */
  97   private static final int DEFAULT_CAPACITY = 21;
  98
  99   /**
 100    * This object is used to mark deleted items. Package visible for use by
 101    * nested classes.
 102    */
 103   static final Object tombstone = new Object();
 104
 105   /**
 106    * This object is used to mark empty slots.  We need this because
 107    * using null is ambiguous. Package visible for use by nested classes.
 108    */
 109   static final Object emptyslot = new Object();
 110
 111   /**
 112    * Compatible with JDK 1.4.
 113    */
 114   private static final long serialVersionUID = 8188218128353913216L;
 115
 116   /**
 117    * The number of mappings in the table. Package visible for use by nested
 118    * classes.
 119    * @serial
 120    */
 121   int size;
 122
 123   /**
 124    * The table itself. Package visible for use by nested classes.
 125    */
 126   transient Object[] table;
 127
 128   /**
 129    * The number of structural modifications made so far. Package visible for
 130    * use by nested classes.
 131    */
 132   transient int modCount;
 133
 134   /**
 135    * The cache for {@link #entrySet()}.
 136    */
 137   private transient Set entries;
 138
 139   /**
 140    * The threshold for rehashing, which is 75% of (table.length / 2).
 141    */
 142   private transient int threshold;
 143
 144   /**
 145    * Create a new IdentityHashMap with the default capacity (21 entries).
 146    */
 147   public IdentityHashMap()
 148   {
 149     this(DEFAULT_CAPACITY);
 150   }
 151
 152   /**
 153    * Create a new IdentityHashMap with the indicated number of
 154    * entries.  If the number of elements added to this hash map
 155    * exceeds this maximum, the map will grow itself; however, that
 156    * incurs a performance penalty.
 157    *
 158    * @param max initial size
 159    * @throws IllegalArgumentException if max is negative
 160    */
 161   public IdentityHashMap(int max)
 162   {
 163     if (max < 0)
 164       throw new IllegalArgumentException();
 165     // Need at least two slots, or hash() will break.
 166     if (max < 2)
 167       max = 2;
 168     table = new Object[max << 1];
 169     Arrays.fill(table, emptyslot);
 170     threshold = (max >> 2) * 3;
 171   }
 172
 173   /**
 174    * Create a new IdentityHashMap whose contents are taken from the
 175    * given Map.
 176    *
 177    * @param m The map whose elements are to be put in this map
 178    * @throws NullPointerException if m is null
 179    */
 180   public IdentityHashMap(Map m)
 181   {
 182     this(Math.max(m.size() << 1, DEFAULT_CAPACITY));
 183     putAll(m);
 184   }
 185
 186   /**
 187    * Remove all mappings from this map.
 188    */
 189   public void clear()
 190   {
 191     if (size != 0)
 192       {
 193         modCount++;
 194         Arrays.fill(table, emptyslot);
 195         size = 0;
 196       }
 197   }
 198
 199   /**
 200    * Creates a shallow copy where keys and values are not cloned.
 201    */
 202   public Object clone()
 203   {
 204     try
 205       {
 206         IdentityHashMap copy = (IdentityHashMap) super.clone();
 207         copy.table = (Object[]) table.clone();
 208         copy.entries = null; // invalidate the cache
 209         return copy;
 210       }
 211     catch (CloneNotSupportedException e)
 212       {
 213         // Can't happen.
 214         return null;
 215       }
 216   }
 217
 218   /**
 219    * Tests whether the specified key is in this map.  Unlike normal Maps,
 220    * this test uses <code>entry == key</code> instead of
 221    * <code>entry == null ? key == null : entry.equals(key)</code>.
 222    *
 223    * @param key the key to look for
 224    * @return true if the key is contained in the map
 225    * @see #containsValue(Object)
 226    * @see #get(Object)
 227    */
 228   public boolean containsKey(Object key)
 229   {
 230     return key == table[hash(key)];
 231   }
 232
 233   /**
 234    * Returns true if this HashMap contains the value.  Unlike normal maps,
 235    * this test uses <code>entry == value</code> instead of
 236    * <code>entry == null ? value == null : entry.equals(value)</code>.
 237    *
 238    * @param value the value to search for in this HashMap
 239    * @return true if at least one key maps to the value
 240    * @see #containsKey(Object)
 241    */
 242   public boolean containsValue(Object value)
 243   {
 244     for (int i = table.length - 1; i > 0; i -= 2)
 245       if (table[i] == value)
 246         return true;
 247     return false;
 248   }
 249
 250   /**
 251    * Returns a "set view" of this Map's entries. The set is backed by
 252    * the Map, so changes in one show up in the other.  The set supports
 253    * element removal, but not element addition.
 254    * <p>
 255    *
 256    * <em>The semantics of this set, and of its contained entries, are
 257    * different from the contract of Set and Map.Entry in order to make
 258    * IdentityHashMap work.  This means that while you can compare these
 259    * objects between IdentityHashMaps, comparing them with regular sets
 260    * or entries is likely to have undefined behavior.</em>  The entries
 261    * in this set are reference-based, rather than the normal object
 262    * equality.  Therefore, <code>e1.equals(e2)</code> returns
 263    * <code>e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue()</code>,
 264    * and <code>e.hashCode()</code> returns
 265    * <code>System.identityHashCode(e.getKey()) ^
 266    *       System.identityHashCode(e.getValue())</code>.
 267    * <p>
 268    *
 269    * Note that the iterators for all three views, from keySet(), entrySet(),
 270    * and values(), traverse the Map in the same sequence.
 271    *
 272    * @return a set view of the entries
 273    * @see #keySet()
 274    * @see #values()
 275    * @see Map.Entry
 276    */
 277   public Set entrySet()
 278   {
 279     if (entries == null)
 280       entries = new AbstractSet()
 281       {
 282         public int size()
 283         {
 284           return size;
 285         }
 286
 287         public Iterator iterator()
 288         {
 289           return new IdentityIterator(ENTRIES);
 290         }
 291
 292         public void clear()
 293         {
 294           IdentityHashMap.this.clear();
 295         }
 296
 297         public boolean contains(Object o)
 298         {
 299           if (! (o instanceof Map.Entry))
 300             return false;
 301           Map.Entry m = (Map.Entry) o;
 302           return m.getValue() == table[hash(m.getKey()) + 1];
 303         }
 304
 305         public int hashCode()
 306         {
 307           return IdentityHashMap.this.hashCode();
 308         }
 309
 310         public boolean remove(Object o)
 311         {
 312           if (! (o instanceof Map.Entry))
 313             return false;
 314           Object key = ((Map.Entry) o).getKey();
 315           int h = hash(key);
 316           if (table[h] == key)
 317             {
 318               size--;
 319               modCount++;
 320               table[h] = tombstone;
 321               table[h + 1] = tombstone;
 322               return true;
 323             }
 324           return false;
 325         }
 326       };
 327     return entries;
 328   }
 329
 330   /**
 331    * Compares two maps for equality. This returns true only if both maps
 332    * have the same reference-identity comparisons. While this returns
 333    * <code>this.entrySet().equals(m.entrySet())</code> as specified by Map,
 334    * this will not work with normal maps, since the entry set compares
 335    * with == instead of .equals.
 336    *
 337    * @param o the object to compare to
 338    * @return true if it is equal
 339    */
 340   public boolean equals(Object o)
 341   {
 342     // Why did Sun specify this one? The superclass does the right thing.
 343     return super.equals(o);
 344   }
 345
 346   /**
 347    * Return the value in this Map associated with the supplied key, or
 348    * <code>null</code> if the key maps to nothing.
 349    *
 350    * <p>NOTE: Since the value could also be null, you must use
 351    * containsKey to see if this key actually maps to something.
 352    * Unlike normal maps, this tests for the key with <code>entry ==
 353    * key</code> instead of <code>entry == null ? key == null :
 354    * entry.equals(key)</code>.
 355    *
 356    * @param key the key for which to fetch an associated value
 357    * @return what the key maps to, if present
 358    * @see #put(Object, Object)
 359    * @see #containsKey(Object)
 360    */
 361   public Object get(Object key)
 362   {
 363     int h = hash(key);
 364     return table[h] == key ? table[h + 1] : null;
 365   }
 366
 367   /**
 368    * Returns the hashcode of this map. This guarantees that two
 369    * IdentityHashMaps that compare with equals() will have the same hash code,
 370    * but may break with comparison to normal maps since it uses
 371    * System.identityHashCode() instead of hashCode().
 372    *
 373    * @return the hash code
 374    */
 375   public int hashCode()
 376   {
 377     int hash = 0;
 378     for (int i = table.length - 2; i >= 0; i -= 2)
 379       {
 380         Object key = table[i];
 381         if (key == emptyslot || key == tombstone)
 382           continue;
 383         hash += (System.identityHashCode(key)
 384                  ^ System.identityHashCode(table[i + 1]));
 385       }
 386     return hash;
 387   }
 388
 389   /**
 390    * Returns true if there are no key-value mappings currently in this Map
 391    * @return <code>size() == 0</code>
 392    */
 393   public boolean isEmpty()
 394   {
 395     return size == 0;
 396   }
 397
 398   /**
 399    * Returns a "set view" of this Map's keys. The set is backed by the
 400    * Map, so changes in one show up in the other.  The set supports
 401    * element removal, but not element addition.
 402    * <p>
 403    *
 404    * <em>The semantics of this set are different from the contract of Set
 405    * in order to make IdentityHashMap work.  This means that while you can
 406    * compare these objects between IdentityHashMaps, comparing them with
 407    * regular sets is likely to have undefined behavior.</em>  The hashCode
 408    * of the set is the sum of the identity hash codes, instead of the
 409    * regular hashCodes, and equality is determined by reference instead
 410    * of by the equals method.
 411    * <p>
 412    *
 413    * @return a set view of the keys
 414    * @see #values()
 415    * @see #entrySet()
 416    */
 417   public Set keySet()
 418   {
 419     if (keys == null)
 420       keys = new AbstractSet()
 421       {
 422         public int size()
 423         {
 424           return size;
 425         }
 426
 427         public Iterator iterator()
 428         {
 429           return new IdentityIterator(KEYS);
 430         }
 431
 432         public void clear()
 433         {
 434           IdentityHashMap.this.clear();
 435         }
 436
 437         public boolean contains(Object o)
 438         {
 439           return containsKey(o);
 440         }
 441
 442         public int hashCode()
 443         {
 444           int hash = 0;
 445           for (int i = table.length - 2; i >= 0; i -= 2)
 446             {
 447               Object key = table[i];
 448               if (key == emptyslot || key == tombstone)
 449                 continue;
 450               hash += System.identityHashCode(key);
 451             }
 452           return hash;
 453
 454         }
 455
 456         public boolean remove(Object o)
 457         {
 458           int h = hash(o);
 459           if (table[h] == o)
 460             {
 461               size--;
 462               modCount++;
 463               table[h] = tombstone;
 464               table[h + 1] = tombstone;
 465               return true;
 466             }
 467           return false;
 468         }
 469       };
 470     return keys;
 471   }
 472
 473   /**
 474    * Puts the supplied value into the Map, mapped by the supplied key.
 475    * The value may be retrieved by any object which <code>equals()</code>
 476    * this key. NOTE: Since the prior value could also be null, you must
 477    * first use containsKey if you want to see if you are replacing the
 478    * key's mapping.  Unlike normal maps, this tests for the key
 479    * with <code>entry == key</code> instead of
 480    * <code>entry == null ? key == null : entry.equals(key)</code>.
 481    *
 482    * @param key the key used to locate the value
 483    * @param value the value to be stored in the HashMap
 484    * @return the prior mapping of the key, or null if there was none
 485    * @see #get(Object)
 486    */
 487   public Object put(Object key, Object value)
 488   {
 489     // Rehash if the load factor is too high.
 490     if (size > threshold)
 491       {
 492         Object[] old = table;
 493         // This isn't necessarily prime, but it is an odd number of key/value
 494         // slots, which has a higher probability of fewer collisions.
 495         table = new Object[(old.length * 2) + 2];
 496         Arrays.fill(table, emptyslot);
 497         size = 0;
 498         threshold = (table.length >>> 3) * 3;
 499
 500         for (int i = old.length - 2; i >= 0; i -= 2)
 501           {
 502             Object oldkey = old[i];
 503             if (oldkey != tombstone && oldkey != emptyslot)
 504               // Just use put.  This isn't very efficient, but it is ok.
 505               put(oldkey, old[i + 1]);
 506           }
 507       }
 508
 509     int h = hash(key);
 510     if (table[h] == key)
 511       {
 512         Object r = table[h + 1];
 513         table[h + 1] = value;
 514         return r;
 515       }
 516
 517     // At this point, we add a new mapping.
 518     modCount++;
 519     size++;
 520     table[h] = key;
 521     table[h + 1] = value;
 522     return null;
 523   }
 524
 525   /**
 526    * Copies all of the mappings from the specified map to this. If a key
 527    * is already in this map, its value is replaced.
 528    *
 529    * @param m the map to copy
 530    * @throws NullPointerException if m is null
 531    */
 532   public void putAll(Map m)
 533   {
 534     // Why did Sun specify this one? The superclass does the right thing.
 535     super.putAll(m);
 536   }
 537
 538   /**
 539    * Removes from the HashMap and returns the value which is mapped by
 540    * the supplied key. If the key maps to nothing, then the HashMap
 541    * remains unchanged, and <code>null</code> is returned.
 542    *
 543    * NOTE: Since the value could also be null, you must use
 544    * containsKey to see if you are actually removing a mapping.
 545    * Unlike normal maps, this tests for the key with <code>entry ==
 546    * key</code> instead of <code>entry == null ? key == null :
 547    * entry.equals(key)</code>.
 548    *
 549    * @param key the key used to locate the value to remove
 550    * @return whatever the key mapped to, if present
 551    */
 552   public Object remove(Object key)
 553   {
 554     int h = hash(key);
 555     if (table[h] == key)
 556       {
 557         modCount++;
 558         size--;
 559         Object r = table[h + 1];
 560         table[h] = tombstone;
 561         table[h + 1] = tombstone;
 562         return r;
 563       }
 564     return null;
 565   }
 566
 567   /**
 568    * Returns the number of kay-value mappings currently in this Map
 569    * @return the size
 570    */
 571   public int size()
 572   {
 573     return size;
 574   }
 575
 576   /**
 577    * Returns a "collection view" (or "bag view") of this Map's values.
 578    * The collection is backed by the Map, so changes in one show up
 579    * in the other.  The collection supports element removal, but not element
 580    * addition.
 581    * <p>
 582    *
 583    * <em>The semantics of this set are different from the contract of
 584    * Collection in order to make IdentityHashMap work.  This means that
 585    * while you can compare these objects between IdentityHashMaps, comparing
 586    * them with regular sets is likely to have undefined behavior.</em>
 587    * Likewise, contains and remove go by == instead of equals().
 588    * <p>
 589    *
 590    * @return a bag view of the values
 591    * @see #keySet()
 592    * @see #entrySet()
 593    */
 594   public Collection values()
 595   {
 596     if (values == null)
 597       values = new AbstractCollection()
 598       {
 599         public int size()
 600         {
 601           return size;
 602         }
 603
 604         public Iterator iterator()
 605         {
 606           return new IdentityIterator(VALUES);
 607         }
 608
 609         public void clear()
 610         {
 611           IdentityHashMap.this.clear();
 612         }
 613
 614         public boolean remove(Object o)
 615         {
 616           for (int i = table.length - 1; i > 0; i -= 2)
 617             if (table[i] == o)
 618               {
 619                 modCount++;
 620                 table[i - 1] = tombstone;
 621                 table[i] = tombstone;
 622                 size--;
 623                 return true;
 624               }
 625           return false;
 626         }
 627       };
 628     return values;
 629   }
 630
 631   /**
 632    * Helper method which computes the hash code, then traverses the table
 633    * until it finds the key, or the spot where the key would go.
 634    *
 635    * @param key the key to check
 636    * @return the index where the key belongs
 637    * @see #IdentityHashMap(int)
 638    * @see #put(Object, Object)
 639    */
 640   // Package visible for use by nested classes.
 641   int hash(Object key)
 642   {
 643     // Implementation note: it is feasible for the table to have no
 644     // emptyslots, if it is full with entries and tombstones, so we must
 645     // remember where we started. If we encounter the key or an emptyslot,
 646     // we are done.  If we encounter a tombstone, the key may still be in
 647     // the array.  If we don't encounter the key, we use the first emptyslot
 648     // or tombstone we encountered as the location where the key would go.
 649     // By requiring at least 2 key/value slots, and rehashing at 75%
 650     // capacity, we guarantee that there will always be either an emptyslot
 651     // or a tombstone somewhere in the table.
 652     int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1;
 653     int del = -1;
 654     int save = h;
 655
 656     do
 657       {
 658         if (table[h] == key)
 659           return h;
 660         if (table[h] == emptyslot)
 661           break;
 662         if (table[h] == tombstone && del < 0)
 663           del = h;
 664         h -= 2;
 665         if (h < 0)
 666           h = table.length - 2;
 667       }
 668     while (h != save);
 669
 670     return del < 0 ? h : del;
 671   }
 672
 673   /**
 674    * This class allows parameterized iteration over IdentityHashMaps.  Based
 675    * on its construction, it returns the key or value of a mapping, or
 676    * creates the appropriate Map.Entry object with the correct fail-fast
 677    * semantics and identity comparisons.
 678    *
 679    * @author Tom Tromey (tromey@redhat.com)
 680    * @author Eric Blake (ebb9@email.byu.edu)
 681    */
 682   private class IdentityIterator implements Iterator
 683   {
 684     /**
 685      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
 686      * or {@link #ENTRIES}.
 687      */
 688     final int type;
 689     /** The number of modifications to the backing Map that we know about. */
 690     int knownMod = modCount;
 691     /** The number of elements remaining to be returned by next(). */
 692     int count = size;
 693     /** Location in the table. */
 694     int loc = table.length;
 695
 696     /**
 697      * Construct a new Iterator with the supplied type.
 698      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
 699      */
 700     IdentityIterator(int type)
 701     {
 702       this.type = type;
 703     }
 704
 705     /**
 706      * Returns true if the Iterator has more elements.
 707      * @return true if there are more elements
 708      * @throws ConcurrentModificationException if the Map was modified
 709      */
 710     public boolean hasNext()
 711     {
 712       if (knownMod != modCount)
 713         throw new ConcurrentModificationException();
 714       return count > 0;
 715     }
 716
 717     /**
 718      * Returns the next element in the Iterator's sequential view.
 719      * @return the next element
 720      * @throws ConcurrentModificationException if the Map was modified
 721      * @throws NoSuchElementException if there is none
 722      */
 723     public Object next()
 724     {
 725       if (knownMod != modCount)
 726         throw new ConcurrentModificationException();
 727       if (count == 0)
 728         throw new NoSuchElementException();
 729       count--;
 730
 731       Object key;
 732       do
 733         {
 734           loc -= 2;
 735           key = table[loc];
 736         }
 737       while (key == emptyslot || key == tombstone);
 738
 739       return type == KEYS ? key : (type == VALUES ? table[loc + 1]
 740                                    : new IdentityEntry(loc));
 741     }
 742
 743     /**
 744      * Removes from the backing Map the last element which was fetched
 745      * with the <code>next()</code> method.
 746      *
 747      * @throws ConcurrentModificationException if the Map was modified
 748      * @throws IllegalStateException if called when there is no last element
 749      */
 750     public void remove()
 751     {
 752       if (knownMod != modCount)
 753         throw new ConcurrentModificationException();
 754       if (loc == table.length || table[loc] == tombstone)
 755         throw new IllegalStateException();
 756       modCount++;
 757       size--;
 758       table[loc] = tombstone;
 759       table[loc + 1] = tombstone;
 760       knownMod++;
 761     }
 762   } // class IdentityIterator
 763
 764   /**
 765    * This class provides Map.Entry objects for IdentityHashMaps.  The entry
 766    * is fail-fast, and will throw a ConcurrentModificationException if
 767    * the underlying map is modified, or if remove is called on the iterator
 768    * that generated this object.  It is identity based, so it violates
 769    * the general contract of Map.Entry, and is probably unsuitable for
 770    * comparison to normal maps; but it works among other IdentityHashMaps.
 771    *
 772    * @author Eric Blake (ebb9@email.byu.edu)
 773    */
 774   private final class IdentityEntry implements Map.Entry
 775   {
 776     /** The location of this entry. */
 777     final int loc;
 778     /** The number of modifications to the backing Map that we know about. */
 779     final int knownMod = modCount;
 780
 781     /**
 782      * Constructs the Entry.
 783      *
 784      * @param loc the location of this entry in table
 785      */
 786     IdentityEntry(int loc)
 787     {
 788       this.loc = loc;
 789     }
 790
 791     /**
 792      * Compares the specified object with this entry, using identity
 793      * semantics. Note that this can lead to undefined results with
 794      * Entry objects created by normal maps.
 795      *
 796      * @param o the object to compare
 797      * @return true if it is equal
 798      * @throws ConcurrentModificationException if the entry was invalidated
 799      *         by modifying the Map or calling Iterator.remove()
 800      */
 801     public boolean equals(Object o)
 802     {
 803       if (knownMod != modCount || table[loc] == tombstone)
 804         throw new ConcurrentModificationException();
 805       if (! (o instanceof Map.Entry))
 806         return false;
 807       Map.Entry e = (Map.Entry) o;
 808       return table[loc] == e.getKey() && table[loc + 1] == e.getValue();
 809     }
 810
 811     /**
 812      * Returns the key of this entry.
 813      *
 814      * @return the key
 815      * @throws ConcurrentModificationException if the entry was invalidated
 816      *         by modifying the Map or calling Iterator.remove()
 817      */
 818     public Object getKey()
 819     {
 820       if (knownMod != modCount || table[loc] == tombstone)
 821         throw new ConcurrentModificationException();
 822       return table[loc];
 823     }
 824
 825     /**
 826      * Returns the value of this entry.
 827      *
 828      * @return the value
 829      * @throws ConcurrentModificationException if the entry was invalidated
 830      *         by modifying the Map or calling Iterator.remove()
 831      */
 832     public Object getValue()
 833     {
 834       if (knownMod != modCount || table[loc] == tombstone)
 835         throw new ConcurrentModificationException();
 836       return table[loc + 1];
 837     }
 838
 839     /**
 840      * Returns the hashcode of the entry, using identity semantics.
 841      * Note that this can lead to undefined results with Entry objects
 842      * created by normal maps.
 843      *
 844      * @return the hash code
 845      * @throws ConcurrentModificationException if the entry was invalidated
 846      *         by modifying the Map or calling Iterator.remove()
 847      */
 848     public int hashCode()
 849     {
 850       if (knownMod != modCount || table[loc] == tombstone)
 851         throw new ConcurrentModificationException();
 852       return (System.identityHashCode(table[loc])
 853               ^ System.identityHashCode(table[loc + 1]));
 854     }
 855
 856     /**
 857      * Replaces the value of this mapping, and returns the old value.
 858      *
 859      * @param value the new value
 860      * @return the old value
 861      * @throws ConcurrentModificationException if the entry was invalidated
 862      *         by modifying the Map or calling Iterator.remove()
 863      */
 864     public Object setValue(Object value)
 865     {
 866       if (knownMod != modCount || table[loc] == tombstone)
 867         throw new ConcurrentModificationException();
 868       Object r = table[loc + 1];
 869       table[loc + 1] = value;
 870       return r;
 871     }
 872
 873     /**
 874      * This provides a string representation of the entry. It is of the form
 875      * "key=value", where string concatenation is used on key and value.
 876      *
 877      * @return the string representation
 878      * @throws ConcurrentModificationException if the entry was invalidated
 879      *         by modifying the Map or calling Iterator.remove()
 880      */
 881     public String toString()
 882     {
 883       if (knownMod != modCount || table[loc] == tombstone)
 884         throw new ConcurrentModificationException();
 885       return table[loc] + "=" + table[loc + 1];
 886     }
 887   } // class IdentityEntry
 888
 889   /**
 890    * Reads the object from a serial stream.
 891    *
 892    * @param s the stream to read from
 893    * @throws ClassNotFoundException if the underlying stream fails
 894    * @throws IOException if the underlying stream fails
 895    * @serialData expects the size (int), followed by that many key (Object)
 896    *             and value (Object) pairs, with the pairs in no particular
 897    *             order
 898    */
 899   private void readObject(ObjectInputStream s)
 900     throws IOException, ClassNotFoundException
 901   {
 902     s.defaultReadObject();
 903
 904     int num = s.readInt();
 905     table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1];
 906     // Read key/value pairs.
 907     while (--num >= 0)
 908       put(s.readObject(), s.readObject());
 909   }
 910
 911   /**
 912    * Writes the object to a serial stream.
 913    *
 914    * @param s the stream to write to
 915    * @throws IOException if the underlying stream fails
 916    * @serialData outputs the size (int), followed by that many key (Object)
 917    *             and value (Object) pairs, with the pairs in no particular
 918    *             order
 919    */
 920   private void writeObject(ObjectOutputStream s)
 921     throws IOException
 922   {
 923     s.defaultWriteObject();
 924     s.writeInt(size);
 925     for (int i = table.length - 2; i >= 0; i -= 2)
 926       {
 927         Object key = table[i];
 928         if (key != tombstone && key != emptyslot)
 929           {
 930             s.writeObject(key);
 931             s.writeObject(table[i + 1]);
 932           }
 933       }
 934   }
 935 }