Source code: edu/emory/mathcs/util/HashIntMap.java
1 /* ***** BEGIN LICENSE BLOCK *****
2 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
3 *
4 * The contents of this file are subject to the Mozilla Public License Version
5 * 1.1 (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 * http://www.mozilla.org/MPL/
8 *
9 * Software distributed under the License is distributed on an "AS IS" basis,
10 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
11 * for the specific language governing rights and limitations under the
12 * License.
13 *
14 * The Original Code is the Emory Utilities.
15 *
16 * The Initial Developer of the Original Code is
17 * The Distributed Computing Laboratory, Emory University.
18 * Portions created by the Initial Developer are Copyright (C) 2002
19 * the Initial Developer. All Rights Reserved.
20 *
21 * Alternatively, the contents of this file may be used under the terms of
22 * either the GNU General Public License Version 2 or later (the "GPL"), or
23 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
24 * in which case the provisions of the GPL or the LGPL are applicable instead
25 * of those above. If you wish to allow use of your version of this file only
26 * under the terms of either the GPL or the LGPL, and not to allow others to
27 * use your version of this file under the terms of the MPL, indicate your
28 * decision by deleting the provisions above and replace them with the notice
29 * and other provisions required by the GPL or the LGPL. If you do not delete
30 * the provisions above, a recipient may use your version of this file under
31 * the terms of any one of the MPL, the GPL or the LGPL.
32 *
33 * ***** END LICENSE BLOCK ***** */
34
35 package edu.emory.mathcs.util;
36
37 import java.util.*;
38 import java.io.*;
39
40 /**
41 * Hash table based implementation of the <tt>IntMap</tt> interface. This
42 * implementation provides all of the optional map operations, and permixts
43 * <tt>null</tt> values. This class makes no guarantees as to
44 * the order of the map; in particular, it does not guarantee that the order
45 * will remain constant over time.<p>
46 *
47 * This implementation provides constant-time performance for the basic
48 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
49 * disperses the elements properly among the buckets. Iteration over
50 * collection views requires time proportional to the "capacity" of the
51 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
52 * of key-value mappings). Thus, it's very important not to set the intial
53 * capacity too high (or the load factor too low) if iteration performance is
54 * important.<p>
55 *
56 * An instance of <tt>HashIntMap</tt> has two parameters that affect its
57 * performance: <i>initial capacity</i> and <i>load factor</i>. The
58 * <i>capacity</i> is the number of buckets in the hash table, and the initial
59 * capacity is simply the capacity at the time the hash table is created. The
60 * <i>load factor</i> is a measure of how full the hash table is allowed to
61 * get before its capacity is automatically increased. When the number of
62 * entries in the hash table exceeds the product of the load factor and the
63 * current capacity, the capacity is roughly doubled by calling the
64 * <tt>rehash</tt> method.<p>
65 *
66 * As a general rule, the default load factor (.75) offers a good tradeoff
67 * between time and space costs. Higher values decrease the space overhead
68 * but increase the lookup cost (reflected in most of the operations of the
69 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
70 * expected number of entries in the map and its load factor should be taken
71 * into account when setting its initial capacity, so as to minimize the
72 * number of <tt>rehash</tt> operations. If the initial capacity is greater
73 * than the maximum number of entries divided by the load factor, no
74 * <tt>rehash</tt> operations will ever occur.<p>
75 *
76 * If many mappings are to be stored in a <tt>HashIntMap</tt> instance, creating
77 * it with a sufficiently large capacity will allow the mappings to be stored
78 * more efficiently than letting it perform automatic rehashing as needed to
79 * grow the table.<p>
80 *
81 * <b>Note that this implementation is not synchronized.</b> If multiple
82 * threads access this map concurrently, and at least one of the threads
83 * modifies the map structurally, it <i>must</i> be synchronized externally.
84 * (A structural modification is any operation that adds or deletes one or
85 * more mappings; merely changing the value associated with a key that an
86 * instance already contains is not a structural modification.) This is
87 * typically accomplished by synchronizing on some object that naturally
88 * encapsulates the map. If no such object exists, the map should be
89 * "wrapped" using the <tt>Collections.synchronizedMap</tt> method. This is
90 * best done at creation time, to prevent accidental unsynchronized access to
91 * the map: <pre> Map m = Collections.synchronizedMap(new HashMap(...));
92 * </pre><p>
93 *
94 * The iterators returned by all of this class's "collection view methods" are
95 * <i>fail-fast</i>: if the map is structurally modified at any time after the
96 * iterator is created, in any way except through the iterator's own
97 * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
98 * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
99 * modification, the iterator fails quickly and cleanly, rather than risking
100 * arbitrary, non-determixnistic behavior at an undetermined time in the
101 * future.
102 *
103 * @author Josh Bloch
104 * @author Arthur van Hoff
105 * @author Dawid Kurzyniec
106 * @version 1.0
107 * @see Object#hashCode()
108 * @see Collection
109 * @see IntMap
110 * @see TreeIntMap
111 * @since 1.2
112 */
113
114 public class HashIntMap extends AbstractIntMap implements IntMap, Cloneable,
115 java.io.Serializable {
116 /**
117 * The hash table data.
118 */
119 private transient Entry table[];
120
121 /**
122 * The total number of mappings in the hash table.
123 */
124 private transient int count;
125
126 /**
127 * The table is rehashed when its size exceeds this threshold. (The
128 * value of this field is (int)(capacity * loadFactor).)
129 *
130 * @serial
131 */
132 private int threshold;
133
134 /**
135 * The load factor for the hashtable.
136 *
137 * @serial
138 */
139 private float loadFactor;
140
141 /**
142 * The number of times this HashMap has been structurally modified
143 * Structural modifications are those that change the number of mappings in
144 * the HashMap or otherwise modify its internal structure (e.g.,
145 * rehash). This field is used to make iterators on Collection-views of
146 * the HashMap fail-fast. (See ConcurrentModificationException).
147 */
148 private transient int modCount = 0;
149
150 /**
151 * Constructs a new, empty map with the specified initial
152 * capacity and the specified load factor.
153 *
154 * @param initialCapacity the initial capacity of the HashMap.
155 * @param loadFactor the load factor of the HashMap
156 * @throws IllegalArgumentException if the initial capacity is less
157 * than zero, or if the load factor is nonpositive.
158 */
159 public HashIntMap(int initialCapacity, float loadFactor) {
160 if (initialCapacity < 0)
161 throw new IllegalArgumentException("Illegal Initial Capacity: "+
162 initialCapacity);
163 if (loadFactor <= 0 || Float.isNaN(loadFactor))
164 throw new IllegalArgumentException("Illegal Load factor: "+
165 loadFactor);
166 if (initialCapacity==0)
167 initialCapacity = 1;
168 this.loadFactor = loadFactor;
169 table = new Entry[initialCapacity];
170 threshold = (int)(initialCapacity * loadFactor);
171 }
172
173 /**
174 * Constructs a new, empty map with the specified initial capacity
175 * and default load factor, which is <tt>0.75</tt>.
176 *
177 * @param initialCapacity the initial capacity of the HashMap.
178 * @throws IllegalArgumentException if the initial capacity is less
179 * than zero.
180 */
181 public HashIntMap(int initialCapacity) {
182 this(initialCapacity, 0.75f);
183 }
184
185 /**
186 * Constructs a new, empty map with a default capacity and load
187 * factor, which is <tt>0.75</tt>.
188 */
189 public HashIntMap() {
190 this(11, 0.75f);
191 }
192
193 /**
194 * Constructs a new map with the same mappings as the given map. The
195 * map is created with a capacity of twice the number of mappings in
196 * the given map or 11 (whichever is greater), and a default load factor,
197 * which is <tt>0.75</tt>.
198 *
199 * @param t the map whose mappings are to be placed in this map.
200 */
201 public HashIntMap(Map t) {
202 this(Math.max(2*t.size(), 11), 0.75f);
203 putAll(t);
204 }
205
206 /**
207 * Returns the number of key-value mappings in this map.
208 *
209 * @return the number of key-value mappings in this map.
210 */
211 public int size() {
212 return count;
213 }
214
215 /**
216 * Returns <tt>true</tt> if this map contains no key-value mappings.
217 *
218 * @return <tt>true</tt> if this map contains no key-value mappings.
219 */
220 public boolean isEmpty() {
221 return count == 0;
222 }
223
224 /**
225 * Returns <tt>true</tt> if this map maps one or more keys to the
226 * specified value.
227 *
228 * @param value value whose presence in this map is to be tested.
229 * @return <tt>true</tt> if this map maps one or more keys to the
230 * specified value.
231 */
232 public boolean containsValue(Object value) {
233 Entry tab[] = table;
234
235 if (value==null) {
236 for (int i = tab.length ; i-- > 0 ;)
237 for (Entry e = tab[i] ; e != null ; e = e.next) {
238 if (e.value==null) return true;
239 }
240 } else {
241 for (int i = tab.length ; i-- > 0 ;)
242 for (Entry e = tab[i] ; e != null ; e = e.next) {
243 if (value.equals(e.value)) return true;
244 }
245 }
246
247 return false;
248 }
249
250 /**
251 * Returns <tt>true</tt> if this map contains a mapping for the specified
252 * key.
253 *
254 * @return <tt>true</tt> if this map contains a mapping for the specified
255 * key.
256 * @param key key whose presence in this Map is to be tested.
257 */
258 public boolean containsKey(int key) {
259 Entry tab[] = table;
260 int index = (key & 0x7FFFFFFF) % tab.length;
261 for (Entry e = tab[index]; e != null; e = e.next) {
262 if (key == e.key) return true;
263 }
264
265 return false;
266 }
267
268 /**
269 * Returns the value to which this map maps the specified key. Returns
270 * <tt>null</tt> if the map contains no mapping for this key. A return
271 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
272 * map contains no mapping for the key; it's also possible that the map
273 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
274 * operation may be used to distinguish these two cases.
275 *
276 * @return the value to which this map maps the specified key.
277 * @param key key whose associated value is to be returned.
278 */
279 public Object get(int key) {
280 Entry tab[] = table;
281 int index = (key & 0x7FFFFFFF) % tab.length;
282 for (Entry e = tab[index]; e != null; e = e.next) {
283 if (key == e.key) return e.value;
284 }
285
286 return null;
287 }
288
289 /**
290 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
291 * with a larger capacity. This method is called automatically when the
292 * number of keys in this map exceeds its capacity and load factor.
293 */
294 private void rehash() {
295 int oldCapacity = table.length;
296 Entry oldMap[] = table;
297
298 int newCapacity = oldCapacity * 2 + 1;
299 Entry newMap[] = new Entry[newCapacity];
300
301 modCount++;
302 threshold = (int)(newCapacity * loadFactor);
303 table = newMap;
304
305 for (int i = oldCapacity ; i-- > 0 ;) {
306 for (Entry old = oldMap[i] ; old != null ; ) {
307 Entry e = old;
308 old = old.next;
309
310 int index = (e.key & 0x7FFFFFFF) % newCapacity;
311 e.next = newMap[index];
312 newMap[index] = e;
313 }
314 }
315 }
316
317 /**
318 * Associates the specified value with the specified key in this map.
319 * If the map previously contained a mapping for this key, the old
320 * value is replaced.
321 *
322 * @param key key with which the specified value is to be associated.
323 * @param value value to be associated with the specified key.
324 * @return previous value associated with specified key, or <tt>null</tt>
325 * if there was no mapping for key. A <tt>null</tt> return can
326 * also indicate that the HashMap previously associated
327 * <tt>null</tt> with the specified key.
328 */
329 public Object put(int key, Object value) {
330 // Makes sure the key is not already in the HashMap.
331 Entry tab[] = table;
332 int index = 0;
333
334 index = (key & 0x7FFFFFFF) % tab.length;
335 for (Entry e = tab[index] ; e != null ; e = e.next) {
336 if (key == e.key) {
337 Object old = e.value;
338 e.value = value;
339 return old;
340 }
341 }
342
343 modCount++;
344 if (count >= threshold) {
345 // Rehash the table if the threshold is exceeded
346 rehash();
347
348 tab = table;
349 index = (key & 0x7FFFFFFF) % tab.length;
350 }
351
352 // Creates the new entry.
353 Entry e = new Entry(key, value, tab[index]);
354 tab[index] = e;
355 count++;
356 return null;
357 }
358
359 /**
360 * Removes the mapping for this key from this map if present.
361 *
362 * @param key key whose mapping is to be removed from the map.
363 * @return previous value associated with specified key, or <tt>null</tt>
364 * if there was no mapping for key. A <tt>null</tt> return can
365 * also indicate that the map previously associated <tt>null</tt>
366 * with the specified key.
367 */
368 public Object remove(int key) {
369 Entry tab[] = table;
370
371 int index = (key & 0x7FFFFFFF) % tab.length;
372
373 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
374 if (key == e.key) {
375 modCount++;
376 if (prev != null)
377 prev.next = e.next;
378 else
379 tab[index] = e.next;
380
381 count--;
382 Object oldValue = e.value;
383 e.value = null;
384 return oldValue;
385 }
386 }
387
388 return null;
389 }
390
391 /**
392 * Copies all of the mappings from the specified map to this one.
393 *
394 * These mappings replace any mappings that this map had for any of the
395 * keys currently in the specified Map.
396 *
397 * @param t Mappings to be stored in this map.
398 */
399 public void putAll(IntMap t) {
400 Iterator i = t.entrySet().iterator();
401 while (i.hasNext()) {
402 IntMap.Entry e = (IntMap.Entry) i.next();
403 put(e.getKey(), e.getValue());
404 }
405 }
406
407 /**
408 * Removes all mappings from this map.
409 */
410 public void clear() {
411 Entry tab[] = table;
412 modCount++;
413 for (int index = tab.length; --index >= 0; )
414 tab[index] = null;
415 count = 0;
416 }
417
418 /**
419 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
420 * values themselves are not cloned.
421 *
422 * @return a shallow copy of this map.
423 */
424 public Object clone() {
425 try {
426 HashIntMap t = (HashIntMap)super.clone();
427 t.table = new Entry[table.length];
428 for (int i = table.length ; i-- > 0 ; ) {
429 t.table[i] = (table[i] != null) ? (Entry)table[i].clone() : null;
430 }
431 //t.keySet = null;
432 t.entrySet = null;
433 t.values = null;
434 t.modCount = 0;
435 return t;
436 } catch (CloneNotSupportedException e) {
437 // this shouldn't happen, since we are Cloneable
438 throw new InternalError();
439 }
440 }
441
442 // Views
443
444 // private transient Set keySet = null;
445 private transient Set entrySet = null;
446 private transient Collection values = null;
447
448 // /**
449 // * Returns a set view of the keys contained in this map. The set is
450 // * backed by the map, so changes to the map are reflected in the set, and
451 // * vice-versa. The set supports element removal, which removes the
452 // * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
453 // * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
454 // * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
455 // * <tt>addAll</tt> operations.
456 // *
457 // * @return a set view of the keys contained in this map.
458 // */
459 // public Set keySet() {
460 // if (keySet == null) {
461 // keySet = new AbstractSet() {
462 // public Iterator iterator() {
463 // return getHashIterator(KEYS);
464 // }
465 // public int size() {
466 // return count;
467 // }
468 // public boolean contains(Object o) {
469 // return containsKey(o);
470 // }
471 // public boolean remove(Object o) {
472 // int oldSize = count;
473 // HashMap.this.remove(o);
474 // return count != oldSize;
475 // }
476 // public void clear() {
477 // HashMap.this.clear();
478 // }
479 // };
480 // }
481 // return keySet;
482 // }
483
484 /**
485 * Returns a collection view of the values contained in this map. The
486 * collection is backed by the map, so changes to the map are reflected in
487 * the collection, and vice-versa. The collection supports element
488 * removal, which removes the corresponding mapping from this map, via the
489 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
490 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
491 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
492 *
493 * @return a collection view of the values contained in this map.
494 */
495 public Collection values() {
496 if (values==null) {
497 values = new AbstractCollection() {
498 public Iterator iterator() {
499 return getHashIterator(VALUES);
500 }
501 public int size() {
502 return count;
503 }
504 public boolean contains(Object o) {
505 return containsValue(o);
506 }
507 public void clear() {
508 HashIntMap.this.clear();
509 }
510 };
511 }
512 return values;
513 }
514
515 /**
516 * Returns a collection view of the mappings contained in this map. Each
517 * element in the returned collection is a <tt>Map.Entry</tt>. The
518 * collection is backed by the map, so changes to the map are reflected in
519 * the collection, and vice-versa. The collection supports element
520 * removal, which removes the corresponding mapping from the map, via the
521 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
522 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
523 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
524 *
525 * @return a collection view of the mappings contained in this map.
526 * @see Map.Entry
527 */
528 public Set entrySet() {
529 if (entrySet==null) {
530 entrySet = new AbstractSet() {
531 public Iterator iterator() {
532 return getHashIterator(ENTRIES);
533 }
534
535 public boolean contains(Object o) {
536 if (!(o instanceof IntMap.Entry)) return false;
537 IntMap.Entry entry = (IntMap.Entry)o;
538 int key = entry.getKey();
539 Entry tab[] = table;
540 int index = (key & 0x7FFFFFFF) % tab.length;
541
542 for (Entry e = tab[index]; e != null; e = e.next) {
543 if (e.key==key && e.equals(entry)) return true;
544 }
545 return false;
546 }
547
548 public boolean remove(Object o) {
549 if (!(o instanceof IntMap.Entry)) return false;
550 IntMap.Entry entry = (IntMap.Entry)o;
551 int key = entry.getKey();
552 Entry tab[] = table;
553 int index = (key & 0x7FFFFFFF) % tab.length;
554
555 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
556 if (e.key==key && e.equals(entry)) {
557 modCount++;
558 if (prev != null)
559 prev.next = e.next;
560 else
561 tab[index] = e.next;
562
563 count--;
564 e.value = null;
565 return true;
566 }
567 }
568 return false;
569 }
570
571 public int size() {
572 return count;
573 }
574
575 public void clear() {
576 HashIntMap.this.clear();
577 }
578 };
579 }
580
581 return entrySet;
582 }
583
584 private Iterator getHashIterator(int type) {
585 if (count == 0) {
586 return emptyHashIterator;
587 } else {
588 return new HashIterator(type);
589 }
590 }
591
592 /**
593 * HashMap collision list entry.
594 */
595 private static class Entry implements IntMap.Entry {
596 int key; // it is its own hash
597 Object value;
598 Entry next;
599
600 Entry(int key, Object value, Entry next) {
601 this.key = key;
602 this.value = value;
603 this.next = next;
604 }
605
606 protected Object clone() {
607 return new Entry(key, value,
608 (next==null ? null : (Entry)next.clone()));
609 }
610
611 // Map.Entry Ops
612
613 public int getKey() {
614 return key;
615 }
616
617 public Object getValue() {
618 return value;
619 }
620
621 public Object setValue(Object value) {
622 Object oldValue = this.value;
623 this.value = value;
624 return oldValue;
625 }
626
627 public boolean equals(Object o) {
628 if (!(o instanceof IntMap.Entry)) return false;
629 IntMap.Entry e = (IntMap.Entry)o;
630
631 return (key == e.getKey()) &&
632 (value==null ? e.getValue()==null : value.equals(e.getValue()));
633 }
634
635 public int hashCode() {
636 return key ^ (value==null ? 0 : value.hashCode());
637 }
638
639 public String toString() {
640 return ""+key+"="+value;
641 }
642 }
643
644 // Types of Iterators
645 //private static final int KEYS = 0;
646 private static final int VALUES = 1;
647 private static final int ENTRIES = 2;
648
649 private static EmptyHashIterator emptyHashIterator = new EmptyHashIterator();
650
651 private static class EmptyHashIterator implements Iterator {
652 EmptyHashIterator() {}
653
654 public boolean hasNext() {
655 return false;
656 }
657
658 public Object next() {
659 throw new NoSuchElementException();
660 }
661
662 public void remove() {
663 throw new IllegalStateException();
664 }
665 }
666
667 private class HashIterator implements Iterator {
668 Entry[] table = HashIntMap.this.table;
669 int index = table.length;
670 Entry entry = null;
671 Entry lastReturned = null;
672 int type;
673
674 /**
675 * The modCount value that the iterator believes that the backing
676 * List should have. If this expectation is violated, the iterator
677 * has detected concurrent modification.
678 */
679 private int expectedModCount = modCount;
680
681 HashIterator(int type) {
682 this.type = type;
683 }
684
685 public boolean hasNext() {
686 Entry e = entry;
687 int i = index;
688 Entry t[] = table;
689 /* Use locals for faster loop iteration */
690 while (e == null && i > 0)
691 e = t[--i];
692 entry = e;
693 index = i;
694 return e != null;
695 }
696
697 public Object next() {
698 if (modCount != expectedModCount)
699 throw new ConcurrentModificationException();
700
701 Entry et = entry;
702 int i = index;
703 Entry t[] = table;
704
705 /* Use locals for faster loop iteration */
706 while (et == null && i > 0)
707 et = t[--i];
708
709 entry = et;
710 index = i;
711 if (et != null) {
712 Entry e = lastReturned = entry;
713 entry = e.next;
714 return type == VALUES ? e.value : e;
715 }
716 throw new NoSuchElementException();
717 }
718
719 public void remove() {
720 if (lastReturned == null) throw new IllegalStateException();
721 if (modCount != expectedModCount) throw new ConcurrentModificationException();
722
723 Entry[] tab = HashIntMap.this.table;
724 int index = (lastReturned.key & 0x7FFFFFFF) % tab.length;
725
726 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
727 if (e == lastReturned) {
728 modCount++;
729 expectedModCount++;
730 if (prev == null)
731 tab[index] = e.next;
732 else
733 prev.next = e.next;
734 count--;
735 lastReturned = null;
736 return;
737 }
738 }
739 throw new ConcurrentModificationException();
740 }
741 }
742
743 /**
744 * Save the state of the <tt>HashIntMap</tt> instance to a stream (i.e.,
745 * serialize it).
746 *
747 * @serialData The <i>capacity</i> of the HashIntMap (the length of the
748 * bucket array) is emitted (int), followed by the
749 * <i>size</i> of the HashIntMap (the number of key-value
750 * mappings), followed by the key (Object) and value (Object)
751 * for each key-value mapping represented by the HashIntMap
752 * The key-value mappings are emitted in no particular order.
753 */
754 private void writeObject(java.io.ObjectOutputStream s) throws IOException {
755 // Write out the threshold, loadfactor, and any hidden stuff
756 s.defaultWriteObject();
757
758 // Write out number of buckets
759 s.writeInt(table.length);
760
761 // Write out size (number of Mappings)
762 s.writeInt(count);
763
764 // Write out keys and values (alternating)
765 for (int index = table.length-1; index >= 0; index--) {
766 Entry entry = table[index];
767
768 while (entry != null) {
769 s.writeInt(entry.key);
770 s.writeObject(entry.value);
771 entry = entry.next;
772 }
773 }
774 }
775
776 // private static final long serialVersionUID = 362498820763181265L;
777
778 /**
779 * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
780 * deserialize it).
781 */
782 private void readObject(java.io.ObjectInputStream s)
783 throws IOException, ClassNotFoundException
784 {
785 // Read in the threshold, loadfactor, and any hidden stuff
786 s.defaultReadObject();
787
788 // Read in number of buckets and allocate the bucket array;
789 int numBuckets = s.readInt();
790 table = new Entry[numBuckets];
791
792 // Read in size (number of Mappings)
793 int size = s.readInt();
794
795 // Read the keys and values, and put the mappings in the HashMap
796 for (int i=0; i<size; i++) {
797 int key = s.readInt();
798 Object value = s.readObject();
799 put(key, value);
800 }
801 }
802
803 int capacity() {
804 return table.length;
805 }
806
807 float loadFactor() {
808 return loadFactor;
809 }
810 }
811