View Javadoc

1   /*
2    * $Header: /home/projects/jaxen/scm/jaxen/src/java/main/org/jaxen/util/IdentityHashMap.java,v 1.9 2005/04/15 14:13:52 elharo Exp $
3    * $Revision: 1.9 $
4    * $Date: 2005/04/15 14:13:52 $
5    *
6    * ====================================================================
7    *
8    * Copyright (C) 2000-2002 bob mcwhirter & James Strachan.
9    * All rights reserved.
10   *
11   * Redistribution and use in source and binary forms, with or without
12   * modification, are permitted provided that the following conditions
13   * are met:
14   * 
15   * 1. Redistributions of source code must retain the above copyright
16   *    notice, this list of conditions, and the following disclaimer.
17   *
18   * 2. Redistributions in binary form must reproduce the above copyright
19   *    notice, this list of conditions, and the disclaimer that follows 
20   *    these conditions in the documentation and/or other materials 
21   *    provided with the distribution.
22   *
23   * 3. The name "Jaxen" must not be used to endorse or promote products
24   *    derived from this software without prior written permission.  For
25   *    written permission, please contact license@jaxen.org.
26   * 
27   * 4. Products derived from this software may not be called "Jaxen", nor
28   *    may "Jaxen" appear in their name, without prior written permission
29   *    from the Jaxen Project Management (pm@jaxen.org).
30   * 
31   * In addition, we request (but do not require) that you include in the 
32   * end-user documentation provided with the redistribution and/or in the 
33   * software itself an acknowledgement equivalent to the following:
34   *     "This product includes software developed by the
35   *      Jaxen Project (http://www.jaxen.org/)."
36   * Alternatively, the acknowledgment may be graphical using the logos 
37   * available at http://www.jaxen.org/
38   *
39   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
40   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
41   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
42   * DISCLAIMED.  IN NO EVENT SHALL THE Jaxen AUTHORS OR THE PROJECT
43   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
45   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
46   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
47   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
48   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
49   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50   * SUCH DAMAGE.
51   *
52   * ====================================================================
53   * This software consists of voluntary contributions made by many 
54   * individuals on behalf of the Jaxen Project and was originally 
55   * created by bob mcwhirter <bob@werken.com> and 
56   * James Strachan <jstrachan@apache.org>.  For more information on the 
57   * Jaxen Project, please see <http://www.jaxen.org/>.
58   * 
59   * $Id: IdentityHashMap.java,v 1.9 2005/04/15 14:13:52 elharo Exp $
60   */
61  
62  package org.jaxen.util;
63  import java.io.IOException;
64  import java.util.AbstractCollection;
65  import java.util.AbstractMap;
66  import java.util.AbstractSet;
67  import java.util.Collection;
68  import java.util.ConcurrentModificationException;
69  import java.util.Iterator;
70  import java.util.Map;
71  import java.util.NoSuchElementException;
72  import java.util.Set;
73  
74  import org.jaxen.JaxenConstants;
75  
76  public class IdentityHashMap extends AbstractMap implements Map, Cloneable,
77                                           java.io.Serializable {
78      /***
79       * The hash table data.
80       */
81      private transient Entry table[];
82  
83      /***
84       * The total number of mappings in the hash table.
85       */
86      private transient int count;
87  
88      /***
89       * The table is rehashed when its size exceeds this threshold.  (The
90       * value of this field is (int)(capacity * loadFactor).)
91       *
92       * @serial
93       */
94      private int threshold;
95  
96      /***
97       * The load factor for the hashtable.
98       *
99       * @serial
100      */
101     private float loadFactor;
102 
103     /***
104      * The number of times this HashMap has been structurally modified
105      * Structural modifications are those that change the number of mappings in
106      * the HashMap or otherwise modify its internal structure (e.g.,
107      * rehash).  This field is used to make iterators on Collection-views of
108      * the HashMap fail-fast.  (See ConcurrentModificationException).
109      */
110     private transient int modCount = 0;
111 
112     /***
113      * Constructs a new, empty map with the specified initial 
114      * capacity and the specified load factor. 
115      *
116      * @param      initialCapacity   the initial capacity of the HashMap
117      * @param      loadFactor        the load factor of the HashMap
118      * @throws     IllegalArgumentException  if the initial capacity is less
119      *               than zero, or if the load factor is non-positive
120      */
121     public IdentityHashMap(int initialCapacity, float loadFactor) {
122         if (initialCapacity < 0)
123             throw new IllegalArgumentException("Illegal Initial Capacity: "+
124                                                initialCapacity);
125         if (loadFactor <= 0 || Float.isNaN(loadFactor))
126             throw new IllegalArgumentException("Illegal Load factor: "+
127                                                loadFactor);
128         if (initialCapacity==0)
129             initialCapacity = 1;
130         this.loadFactor = loadFactor;
131         table = new Entry[initialCapacity];
132         threshold = (int)(initialCapacity * loadFactor);
133     }
134 
135     /***
136      * Constructs a new, empty map with the specified initial capacity
137      * and default load factor, which is <code>0.75</code>.
138      *
139      * @param   initialCapacity   the initial capacity of the HashMap
140      * @throws  IllegalArgumentException if the initial capacity is less
141      *              than zero
142      */
143     public IdentityHashMap(int initialCapacity) {
144         this(initialCapacity, 0.75f);
145     }
146 
147     /***
148      * Constructs a new, empty map with a default capacity and load
149      * factor, which is <code>0.75</code>.
150      */
151     public IdentityHashMap() {
152         this(11, 0.75f);
153     }
154 
155     /***
156      * Constructs a new map with the same mappings as the given map.  The
157      * map is created with a capacity of twice the number of mappings in
158      * the given map or 11 (whichever is greater), and a default load factor,
159      * which is <code>0.75</code>.
160      *
161      * @param t the map whose mappings are to be placed in this map
162      */
163     public IdentityHashMap(Map t) {
164         this(Math.max(2*t.size(), 11), 0.75f);
165         putAll(t);
166     }
167 
168     /***
169      * Returns the number of key-value mappings in this map
170      *
171      * @return the number of key-value mappings in this map
172      */
173     public int size() {
174         return count;
175     }
176 
177     /***
178      * Returns <code>true</code> if this map contains no key-value mappings
179      *
180      * @return <code>true</code> if this map contains no key-value mappings
181      */
182     public boolean isEmpty() {
183         return count == 0;
184     }
185 
186     /***
187      * Returns <code>true</code> if this map maps one or more keys to the
188      * specified value.
189      *
190      * @param value value whose presence in this map is to be tested.
191      * @return <code>true</code> if this map maps one or more keys to the
192      *         specified value
193      */
194     public boolean containsValue(Object value) {
195         Entry tab[] = table;
196 
197         if (value==null) {
198             for (int i = tab.length ; i > 0 ; i--)
199                 for (Entry e = tab[i] ; e != null ; e = e.next)
200                     if (e.value==null)
201                         return true;
202         } else {
203             for (int i = tab.length ; i > 0 ; i--)
204                 for (Entry e = tab[i] ; e != null ; e = e.next)
205                     if (value.equals(e.value))
206                         return true;
207         }
208 
209         return false;
210     }
211 
212     /***
213      * Returns <code>true</code> if this map contains a mapping for the specified
214      * key.
215      * 
216      * @return <code>true</code> if this map contains a mapping for the specified
217      * key
218      * @param key key whose presence in this Map is to be tested
219      */
220     public boolean containsKey(Object key) {
221         Entry tab[] = table;
222         if (key != null) {
223             //int hash = key.hashCode();
224             int hash = System.identityHashCode( key );
225             int index = (hash & 0x7FFFFFFF) % tab.length;
226             for (Entry e = tab[index]; e != null; e = e.next)
227                 // if (e.hash==hash && key.equals(e.key))
228                 if (e.hash==hash && ( key == e.key ) )
229                     return true;
230         } else {
231             for (Entry e = tab[0]; e != null; e = e.next)
232                 if (e.key==null) return true;
233         }
234 
235         return false;
236     }
237 
238     /***
239      * Returns the value to which this map maps the specified key.  Returns
240      * <code>null</code> if the map contains no mapping for this key.  A return
241      * value of <code>null</code> does not <i>necessarily</i> indicate that the
242      * map contains no mapping for the key; it's also possible that the map
243      * explicitly maps the key to <code>null</code>.  The <code>containsKey</code>
244      * operation may be used to distinguish these two cases.
245      *
246      * @return the value to which this map maps the specified key
247      * @param key key whose associated value is to be returned
248      */
249     public Object get(Object key) {
250         Entry tab[] = table;
251 
252         if (key != null) {
253             // int hash = key.hashCode();
254             int hash = System.identityHashCode( key );
255             int index = (hash & 0x7FFFFFFF) % tab.length;
256             for (Entry e = tab[index]; e != null; e = e.next)
257                 // if ((e.hash == hash) && key.equals(e.key))
258                 if ((e.hash == hash) && ( key == e.key ) )
259                     return e.value;
260         } else {
261             for (Entry e = tab[0]; e != null; e = e.next)
262                 if (e.key==null)
263                     return e.value;
264         }
265 
266         return null;
267     }
268 
269     /***
270      * Rehashes the contents of this map into a new <code>IdentityHashMap</code> instance
271      * with a larger capacity. This method is called automatically when the
272      * number of keys in this map exceeds its capacity and load factor.
273      */
274     private void rehash() {
275         int oldCapacity = table.length;
276         Entry oldMap[] = table;
277 
278         int newCapacity = oldCapacity * 2 + 1;
279         Entry newMap[] = new Entry[newCapacity];
280 
281         modCount++;
282         threshold = (int)(newCapacity * loadFactor);
283         table = newMap;
284 
285         for (int i = oldCapacity ; i-- > 0 ;) {
286             for (Entry old = oldMap[i] ; old != null ; ) {
287                 Entry e = old;
288                 old = old.next;
289 
290                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
291                 e.next = newMap[index];
292                 newMap[index] = e;
293             }
294         }
295     }
296 
297     /***
298      * Associates the specified value with the specified key in this map.
299      * If the map previously contained a mapping for this key, the old
300      * value is replaced.
301      *
302      * @param key key with which the specified value is to be associated
303      * @param value value to be associated with the specified key
304      * @return previous value associated with specified key, or <code>null</code>
305      *         if there was no mapping for key.  A <code>null</code> return can
306      *         also indicate that the IdentityHashMap previously associated
307      *         <code>null</code> with the specified key.
308      */
309     public Object put(Object key, Object value) {
310         // XXX this method is a HotSpot in Jaxen
311         // Makes sure the key is not already in the IdentityHashMap.
312         
313         // I think this copy, which has no semantic effect, is being 
314         // done to speed things up by using a local variable instead of a field
315         // access. I'm not sure this is significant. - ERH
316         Entry tab[] = table;
317         int hash = 0;
318         int index = 0;
319 
320         if (key != null) {
321             hash = System.identityHashCode( key );
322             index = (hash & 0x7FFFFFFF) % tab.length;
323             for (Entry e = tab[index] ; e != null ; e = e.next) {
324                 if ((e.hash == hash) && ( key == e.key ) ) {
325                     Object old = e.value;
326                     e.value = value;
327                     return old;
328                 }
329             }
330         } else {
331             for (Entry e = tab[0] ; e != null ; e = e.next) {
332                 if (e.key == null) {
333                     Object old = e.value;
334                     e.value = value;
335                     return old;
336                 }
337             }
338         }
339 
340         modCount++;
341         if (count >= threshold) {
342             // Rehash the table if the threshold is exceeded
343             rehash();
344 
345             tab = table;
346             index = (hash & 0x7FFFFFFF) % tab.length;
347         }
348 
349         // Creates the new entry.
350         Entry e = new Entry(hash, key, value, tab[index]);
351         tab[index] = e;
352         count++;
353         return null;
354     }
355 
356     /***
357      * Removes the mapping for this key from this map if present.
358      *
359      * @param key key whose mapping is to be removed from the map
360      * @return previous value associated with specified key, or <code>null</code>
361      *         if there was no mapping for key.  A <code>null</code> return can
362      *         also indicate that the map previously associated <code>null</code>
363      *         with the specified key.
364      */
365     public Object remove(Object key) {
366         Entry tab[] = table;
367 
368         if (key != null) {
369             // int hash = key.hashCode();
370             int hash = System.identityHashCode( key );
371             int index = (hash & 0x7FFFFFFF) % tab.length;
372 
373             for (Entry e = tab[index], prev = null; e != null;
374                  prev = e, e = e.next) {
375                 // if ((e.hash == hash) && key.equals(e.key)) {
376                 if ((e.hash == hash) && ( key == e.key ) ) {
377                     modCount++;
378                     if (prev != null)
379                         prev.next = e.next;
380                     else
381                         tab[index] = e.next;
382 
383                     count--;
384                     Object oldValue = e.value;
385                     e.value = null;
386                     return oldValue;
387                 }
388             }
389         } else {
390             for (Entry e = tab[0], prev = null; e != null;
391                  prev = e, e = e.next) {
392                 if (e.key == null) {
393                     modCount++;
394                     if (prev != null)
395                         prev.next = e.next;
396                     else
397                         tab[0] = e.next;
398 
399                     count--;
400                     Object oldValue = e.value;
401                     e.value = null;
402                     return oldValue;
403                 }
404             }
405         }
406 
407         return null;
408     }
409 
410     /***
411      * Copies all of the mappings from the specified map to this one.
412      * 
413      * These mappings replace any mappings that this map had for any of the
414      * keys currently in the specified Map.
415      *
416      * @param t mappings to be stored in this map
417      */
418     public void putAll(Map t) {
419         Iterator i = t.entrySet().iterator();
420         while (i.hasNext()) {
421             Map.Entry e = (Map.Entry) i.next();
422             put(e.getKey(), e.getValue());
423         }
424     }
425 
426     /***
427      * Removes all mappings from this map.
428      */
429     public void clear() {
430         Entry tab[] = table;
431         modCount++;
432         for (int index = tab.length; --index >= 0; )
433             tab[index] = null;
434         count = 0;
435     }
436 
437     /***
438      * Returns a shallow copy of this <code>IdentityHashMap</code> instance: the keys and
439      * values themselves are not cloned.
440      *
441      * @return a shallow copy of this map
442      */
443     public Object clone() {
444         try { 
445             IdentityHashMap t = (IdentityHashMap)super.clone();
446             t.table = new Entry[table.length];
447             for (int i = table.length ; i-- > 0 ; ) {
448                 t.table[i] = (table[i] != null) 
449                     ? (Entry)table[i].clone() : null;
450             }
451             t.keySet = null;
452             t.entrySet = null;
453             t.values = null;
454             t.modCount = 0;
455             return t;
456         } catch (CloneNotSupportedException e) { 
457             // this shouldn't happen, since we are Cloneable
458             throw new InternalError();
459         }
460     }
461 
462     // Views
463 
464     private transient Set keySet = null;
465     private transient Set entrySet = null;
466     private transient Collection values = null;
467 
468     /***
469      * Returns a set view of the keys contained in this map.  The set is
470      * backed by the map, so changes to the map are reflected in the set, and
471      * vice-versa.  The set supports element removal, which removes the
472      * corresponding mapping from this map, via the <code>Iterator.remove</code>,
473      * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>, and
474      * <code>clear</code> operations.  It does not support the <code>add</code> or
475      * <code>addAll</code> operations.
476      *
477      * @return a set view of the keys contained in this map
478      */
479     public Set keySet() {
480         if (keySet == null) {
481             keySet = new AbstractSet() {
482                 public Iterator iterator() {
483                     return getHashIterator(KEYS);
484                 }
485                 public int size() {
486                     return count;
487                 }
488                 public boolean contains(Object o) {
489                     return containsKey(o);
490                 }
491                 public boolean remove(Object o) {
492                     int oldSize = count;
493                     IdentityHashMap.this.remove(o);
494                     return count != oldSize;
495                 }
496                 public void clear() {
497                     IdentityHashMap.this.clear();
498                 }
499             };
500         }
501         return keySet;
502     }
503 
504     /***
505      * Returns a collection view of the values contained in this map.  The
506      * collection is backed by the map, so changes to the map are reflected in
507      * the collection, and vice-versa.  The collection supports element
508      * removal, which removes the corresponding mapping from this map, via the
509      * <code>Iterator.remove</code>, <code>Collection.remove</code>,
510      * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations.
511      * It does not support the <code>add</code> or <code>addAll</code> operations.
512      *
513      * @return a collection view of the values contained in this map
514      */
515     public Collection values() {
516         if (values==null) {
517             values = new AbstractCollection() {
518                 public Iterator iterator() {
519                     return getHashIterator(VALUES);
520                 }
521                 public int size() {
522                     return count;
523                 }
524                 public boolean contains(Object o) {
525                     return containsValue(o);
526                 }
527                 public void clear() {
528                     IdentityHashMap.this.clear();
529                 }
530             };
531         }
532         return values;
533     }
534 
535     /***
536      * Returns a collection view of the mappings contained in this map.  Each
537      * element in the returned collection is a <code>Map.Entry</code>.  The
538      * collection is backed by the map, so changes to the map are reflected in
539      * the collection, and vice-versa.  The collection supports element
540      * removal, which removes the corresponding mapping from the map, via the
541      * <code>Iterator.remove</code>, <code>Collection.remove</code>,
542      * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations.
543      * It does not support the <code>add</code> or <code>addAll</code> operations.
544      *
545      * @return a collection view of the mappings contained in this map
546      * @see Map.Entry
547      */
548     public Set entrySet() {
549         if (entrySet==null) {
550             entrySet = new AbstractSet() {
551                 public Iterator iterator() {
552                     return getHashIterator(ENTRIES);
553                 }
554 
555                 public boolean contains(Object o) {
556                     if (!(o instanceof Map.Entry))
557                         return false;
558                     Map.Entry entry = (Map.Entry)o;
559                     Object key = entry.getKey();
560                     Entry tab[] = table;
561                     // int hash = (key==null ? 0 : key.hashCode());
562                     int hash = (key==null ? 0 : System.identityHashCode( key ) );
563                     int index = (hash & 0x7FFFFFFF) % tab.length;
564 
565                     for (Entry e = tab[index]; e != null; e = e.next)
566                         if (e.hash==hash && e.equals(entry))
567                             return true;
568                     return false;
569                 }
570 
571                 public boolean remove(Object o) {
572                     if (!(o instanceof Map.Entry))
573                         return false;
574                     Map.Entry entry = (Map.Entry)o;
575                     Object key = entry.getKey();
576                     Entry tab[] = table;
577                     // int hash = (key==null ? 0 : key.hashCode());
578                     int hash = (key==null ? 0 : System.identityHashCode( key ) );
579                     int index = (hash & 0x7FFFFFFF) % tab.length;
580 
581                     for (Entry e = tab[index], prev = null; e != null;
582                          prev = e, e = e.next) {
583                         if (e.hash==hash && e.equals(entry)) {
584                             modCount++;
585                             if (prev != null)
586                                 prev.next = e.next;
587                             else
588                                 tab[index] = e.next;
589 
590                             count--;
591                             e.value = null;
592                             return true;
593                         }
594                     }
595                     return false;
596                 }
597 
598                 public int size() {
599                     return count;
600                 }
601 
602                 public void clear() {
603                     IdentityHashMap.this.clear();
604                 }
605             };
606         }
607 
608         return entrySet;
609     }
610 
611     private Iterator getHashIterator(int type) {
612         if (count == 0) {
613             return JaxenConstants.EMPTY_ITERATOR;
614         } else {
615             return new HashIterator(type);
616         }
617     }
618 
619     /***
620      * IdentityHashMap collision list entry.
621      */
622     private static class Entry implements Map.Entry {
623         int hash;
624         Object key;
625         Object value;
626         Entry next;
627 
628         Entry(int hash, Object key, Object value, Entry next) {
629             this.hash = hash;
630             this.key = key;
631             this.value = value;
632             this.next = next;
633         }
634 
635         protected Object clone() {
636             return new Entry(hash, key, value,
637                              (next==null ? null : (Entry)next.clone()));
638         }
639 
640         // Map.Entry Ops 
641 
642         public Object getKey() {
643             return key;
644         }
645 
646         public Object getValue() {
647             return value;
648         }
649 
650         public Object setValue(Object value) {
651             Object oldValue = this.value;
652             this.value = value;
653             return oldValue;
654         }
655 
656         public boolean equals(Object o) {
657             if (!(o instanceof Map.Entry))
658                 return false;
659             Map.Entry e = (Map.Entry)o;
660 
661             return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
662                (value==null ? e.getValue()==null : value.equals(e.getValue()));
663         }
664 
665         public int hashCode() {
666             return hash ^ (value==null ? 0 : value.hashCode());
667         }
668 
669         public String toString() {
670             return key+"="+value;
671         }
672     }
673 
674     // Types of Iterators
675     private static final int KEYS = 0;
676     private static final int VALUES = 1;
677     private static final int ENTRIES = 2;
678                     
679     private class HashIterator implements Iterator {
680         Entry[] table = IdentityHashMap.this.table;
681         int index = table.length;
682         Entry entry = null;
683         Entry lastReturned = null;
684         int type;
685 
686         /***
687          * The modCount value that the iterator believes that the backing
688          * List should have.  If this expectation is violated, the iterator
689          * has detected concurrent modification.
690          */
691         private int expectedModCount = modCount;
692 
693         HashIterator(int type) {
694             this.type = type;
695         }
696 
697         public boolean hasNext() {
698             Entry e = entry;
699             int i = index;
700             Entry t[] = table;
701             /* Use locals for faster loop iteration */
702             while (e == null && i > 0)
703                 e = t[--i];
704             entry = e;
705             index = i;
706             return e != null;
707         }
708 
709         public Object next() {
710             if (modCount != expectedModCount)
711                 throw new ConcurrentModificationException();
712 
713             Entry et = entry;
714             int i = index;
715             Entry t[] = table;
716 
717             /* Use locals for faster loop iteration */
718             while (et == null && i > 0) 
719                 et = t[--i];
720 
721             entry = et;
722             index = i;
723             if (et != null) {
724                 Entry e = lastReturned = entry;
725                 entry = e.next;
726                 return type == KEYS ? e.key : (type == VALUES ? e.value : e);
727             }
728             throw new NoSuchElementException();
729         }
730 
731         public void remove() {
732             if (lastReturned == null)
733                 throw new IllegalStateException();
734             if (modCount != expectedModCount)
735                 throw new ConcurrentModificationException();
736 
737             Entry[] tab = IdentityHashMap.this.table;
738             int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
739 
740             for (Entry e = tab[index], prev = null; e != null;
741                  prev = e, e = e.next) {
742                 if (e == lastReturned) {
743                     modCount++;
744                     expectedModCount++;
745                     if (prev == null)
746                         tab[index] = e.next;
747                     else
748                         prev.next = e.next;
749                     count--;
750                     lastReturned = null;
751                     return;
752                 }
753             }
754             throw new ConcurrentModificationException();
755         }
756     }
757 
758     /***
759      * Save the state of the <code>IdentityHashMap</code> instance to a stream (i.e.,
760      * serialize it).
761      *
762      * @serialData the <em>capacity</em> of the IdentityHashMap (the length of the
763      *             bucket array) is emitted (int), followed  by the
764      *             <em>size</em> of the IdentityHashMap (the number of key-value
765      *             mappings), followed by the key (Object) and value (Object)
766      *             for each key-value mapping represented by the IdentityHashMap.
767      *             The key-value mappings are emitted in no particular order.
768      */
769     private void writeObject(java.io.ObjectOutputStream s)
770         throws IOException
771     {
772         // Write out the threshold, load factor, and any hidden stuff
773         s.defaultWriteObject();
774 
775         // Write out number of buckets
776         s.writeInt(table.length);
777 
778         // Write out size (number of Mappings)
779         s.writeInt(count);
780 
781         // Write out keys and values (alternating)
782         for (int index = table.length-1; index >= 0; index--) {
783             Entry entry = table[index];
784 
785             while (entry != null) {
786                 s.writeObject(entry.key);
787                 s.writeObject(entry.value);
788                 entry = entry.next;
789             }
790         }
791     }
792 
793     private static final long serialVersionUID = 362498820763181265L;
794 
795     /***
796      * Reconstitute the <code>IdentityHashMap</code> instance from a stream (i.e.,
797      * deserialize it).
798      */
799     private void readObject(java.io.ObjectInputStream s)
800          throws IOException, ClassNotFoundException
801     {
802         // Read in the threshold, loadfactor, and any hidden stuff
803         s.defaultReadObject();
804 
805         // Read in number of buckets and allocate the bucket array;
806         int numBuckets = s.readInt();
807         table = new Entry[numBuckets];
808 
809         // Read in size (number of Mappings)
810         int size = s.readInt();
811 
812         // Read the keys and values, and put the mappings in the IdentityHashMap
813         for (int i=0; i<size; i++) {
814             Object key = s.readObject();
815             Object value = s.readObject();
816             put(key, value);
817         }
818     }
819 
820     int capacity() {
821         return table.length;
822     }
823 
824     float loadFactor() {
825         return loadFactor;
826     }
827 }