Java > Open Source Codes > javolution > util > FastMap


1 /*
2  * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
3  * Copyright (C) 2006 - Javolution (http://javolution.org/)
4  * All rights reserved.
5  *
6  * Permission to use, copy, modify, and distribute this software is
7  * freely granted, provided that this notice is preserved.
8  */
9 package javolution.util;
10
11 import j2me.io.ObjectInputStream;
12 import j2me.io.ObjectOutputStream;
13 import j2me.io.Serializable;
14 import j2me.lang.UnsupportedOperationException;
15 import j2me.util.Collection;
16 import j2me.util.Iterator;
17 import j2me.util.Map;
18 import j2me.util.Set;
19 import j2mex.realtime.MemoryArea;
20 import java.io.IOException ;
21 import java.io.PrintStream ;
22 import javolution.context.PersistentContext;
23 import javolution.context.Realtime;
24 import javolution.context.RealtimeObject;
25 import javolution.lang.Reusable;
26 import javolution.text.Text;
27 import javolution.text.TextBuilder;
28 import javolution.util.FastCollection.Record;
29 import javolution.xml.XMLBinding;
30 import javolution.xml.XMLFormat;
31 import javolution.xml.stream.XMLStreamException;
32
33 /**
34  * <p> This class represents a hash map with real-time behavior;
35  * smooth capacity increase and no rehashing ever performed.</p>
36  * <img SRC="doc-files/map-put.png"/>
37  *
38  * <p> {@link FastMap} has a predictable iteration order, which is the order in
39  * which keys are inserted into the map (similar to
40  * <code>java.util.LinkedHashMap</code> collection class).</p>
41  *
42  * <p> {@link FastMap.Entry} can quickly be iterated over (forward or backward)
43  * without using iterators. For example:[code]
44  * FastMap<String, Thread> map = new FastMap<String, Thread>();
45  * for (FastMap.Entry<String, Thread> e = map.head(), end = map.tail(); (e = e.getNext()) != end;) {
46  * String key = e.getKey(); // No typecast necessary.
47  * Thread value = e.getValue(); // No typecast necessary.
48  * }[/code]</p>
49  *
50  * <p> {@link FastMap} may use custom key comparators; the default comparator is
51  * either {@link FastComparator#DIRECT DIRECT} or
52  * {@link FastComparator#REHASH REHASH} based upon the current <a HREF=
53  * "{@docRoot}/overview-summary.html#configuration">Javolution
54  * Configuration</a>. Users may explicitly set the key comparator to
55  * {@link FastComparator#DIRECT DIRECT} for optimum performance
56  * when the hash codes are well distributed for all run-time platforms
57  * (e.g. calculated hash codes).</p>
58  *
59  * <p> Custom key comparators are extremely useful for value retrieval when
60  * map's keys and argument keys are not of the same class, such as
61  * {@link String} and {@link javolution.text.Text Text}
62  * ({@link FastComparator#LEXICAL LEXICAL}) or for identity maps
63  * ({@link FastComparator#IDENTITY IDENTITY}).
64  * For example:[code]
65  * FastMap identityMap = new FastMap().setKeyComparator(FastComparator.IDENTITY);
66  * [/code]</p>
67  *
68  * <p> {@link FastMap} marked {@link #setShared(boolean) shared} are
69  * thread-safe without external synchronization and are often good
70  * substitutes for <code>ConcurrentHashMap</code>. For example:[code]
71  * // Holds the units multiplication lookup table (persistent).
72  * static final FastMap<Unit, FastMap<Unit, Unit>> MULT_LOOKUP
73  * = new FastMap<Unit, FastMap<Unit, Unit>>("mult-unit-lookup").setShared(true);
74  *
75  * // Fast and non-blocking (no synchronization necessary).
76  * static Unit productOf(Unit left, Unit right) {
77  * FastMap<Unit, Unit> leftTable = MULT_LOOKUP.get(left);
78  * if (leftTable == null) return calculateProductOf(left, right);
79  * Unit result = leftTable.get(right);
80  * if (result == null) return calculateProductOf(left, right);
81  * return result; // Returns cache result.
82  * }[/code]</p>
83  *
84  * <p> Finally, {@link FastMap} are {@link Reusable reusable}; they maintain an
85  * internal pool of <code>Map.Entry</code> objects. When an entry is removed
86  * from a map, it is automatically restored to its pool (unless the map
87  * is shared in which case the removed entry is candidate for garbage
88  * collection as it cannot be safely recycled).</p>
89  *
90  * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle </a>
91  * @version 4.2, December 18, 2006
92  */
93 public class FastMap/*<K,V>*/extends RealtimeObject implements Map/*<K,V>*/,
94         Reusable, Serializable {
95
96     /**
97      * Holds the default XML representation for FastMap instances.
98      * This representation is identical to {@link XMLBinding#MAP_XML}
99      * except that it may include the key/value comparators for the map
100      * (if different from {@link FastComparator#DEFAULT}) and the
101      * {@link #isShared() "shared"} attribute.
102      */
103     protected static final XMLFormat/*<FastMap>*/XML = new XMLFormat(
104             new FastMap().getClass()) {
105
106         public void read(InputElement xml, Object obj)
107                 throws XMLStreamException {
108             final FastMap fm = (FastMap) obj;
109             fm.setShared(xml.getAttribute("shared", false));
110             FastComparator keyComparator = (FastComparator) xml
111                     .get("KeyComparator");
112             if (keyComparator != null) {
113                 fm.setKeyComparator(keyComparator);
114             }
115             FastComparator valueComparator = (FastComparator) xml
116                     .get("ValueComparator");
117             if (valueComparator != null) {
118                 fm.setValueComparator(valueComparator);
119             }
120             while (xml.hasNext()) {
121                 Object key = xml.get("Key");
122                 Object value = xml.get("Value");
123                 fm.put(key, value);
124             }
125         }
126
127         public void write(Object obj, OutputElement xml)
128                 throws XMLStreamException {
129             final FastMap fm = (FastMap) obj;
130             if (fm.isShared()) {
131                 xml.setAttribute("shared", true);
132             }
133             if (fm.getKeyComparator() != FastComparator.DEFAULT) {
134                 xml.add(fm.getKeyComparator(), "KeyComparator");
135             }
136             if (fm.getValueComparator() != FastComparator.DEFAULT) {
137                 xml.add(fm.getValueComparator(), "ValueComparator");
138             }
139             for (Entry e = fm.head(), end = fm.tail(); (e = (Entry) e.getNext()) != end;) {
140                 xml.add(e.getKey(), "Key");
141                 xml.add(e.getValue(), "Value");
142             }
143         }
144     };
145
146     /**
147      * Holds table higher index rotation.
148      */
149     private static final int R0 = 5;
150
151     /**
152      * Holds the table lower index mask.
153      */
154     private static final int M0 = (1 << R0) - 1;
155
156     /**
157      * Holds the map factory.
158      */
159     private static final Factory FACTORY = new Factory() {
160
161         public Object create() {
162             return new FastMap();
163         }
164
165         public void cleanup(Object obj) {
166             ((FastMap) obj).reset();
167         }
168     };
169
170     /**
171      * Holds the map's hash table.
172      * Use two dimensional arrays to avoid large arrays allocations.
173      */
174     private transient Entry/*<K,V>*/[][] _entries;
175
176     /**
177      * Holds the head entry to which the first entry attaches.
178      * The head entry never changes (entries always added last).
179      */
180     private transient Entry/*<K,V>*/_head;
181
182     /**
183      * Holds the tail entry to which the last entry attaches.
184      * The tail entry changes as entries are added/removed.
185      */
186     private transient Entry/*<K,V>*/_tail;
187
188     /**
189      * Holds the current size.
190      */
191     private transient int _size;
192
193     /**
194      * Holds the values view.
195      */
196     private transient Values _values;
197
198     /**
199      * Holds the key set view.
200      */
201     private transient KeySet _keySet;
202
203     /**
204      * Holds the entry set view.
205      */
206     private transient EntrySet _entrySet;
207
208     /**
209      * Holds the unmodifiable view.
210      */
211     private transient Map/*<K,V>*/_unmodifiable;
212
213     /**
214      * Holds a reference to a map having the old entries when resizing.
215      */
216     private transient FastMap/*<K,V>*/_oldEntries;
217
218     /**
219      * Holds the key comparator.
220      */
221     private transient FastComparator _keyComparator = FastComparator.DEFAULT;
222
223     /**
224      * Holds the value comparator.
225      */
226     private transient FastComparator _valueComparator = FastComparator.DEFAULT;
227
228     /**
229      * Holds comparator set to <code>null</code> when equivalent to direct.
230      */
231     private transient FastComparator _keyComp
232          = FastComparator._Rehash ? FastComparator.REHASH : null;
233
234     /**
235      * Indicates if this map is shared (thread-safe).
236      */
237     private transient boolean _isShared;
238
239     /**
240      * Creates a fast map of small initial capacity.
241      */
242     public FastMap() {
243         this(4);
244     }
245
246     /**
247      * Creates a persistent map associated to the specified unique identifier
248      * (convenience method).
249      *
250      * @param id the unique identifier for this map.
251      * @throws IllegalArgumentException if the identifier is not unique.
252      * @see javolution.context.PersistentContext.Reference
253      */
254     public FastMap(String id) {
255         this();
256         new PersistentContext.Reference(id, this) {
257             protected void notifyChange() {
258                 FastMap.this.clear();
259                 FastMap.this.putAll((FastMap) this.get());
260             }
261         };
262     }
263
264     /**
265      * Creates a map of specified initial capacity; unless the map size
266      * reaches the specified capacity, operations on this map will not allocate
267      * memory (no lazy object creation).
268      *
269      * @param capacity the initial capacity.
270      */
271     public FastMap(int capacity) {
272         setup(capacity);
273     }
274     private void setup(int capacity) {
275         int tableLength = 1 << R0;
276         while (tableLength < capacity) {
277             tableLength <<= 1;
278         }
279         _entries = (Entry/*<K,V>*/[][]) new Entry[tableLength >> R0][];
280         for (int i = 0; i < _entries.length;) {
281             _entries[i++] = (Entry/*<K,V>*/[]) new Entry[1 << R0];
282         }
283         _head = new Entry();
284         _tail = new Entry();
285         _head._next = _tail;
286         _tail._previous = _head;
287         Entry/*<K,V>*/previous = _tail;
288         for (int i = 0; i++ < capacity;) {
289             Entry/*<K,V>*/newEntry = new Entry/*<K,V>*/();
290             newEntry._previous = previous;
291             previous._next = newEntry;
292             previous = newEntry;
293         }
294     }
295
296     /**
297      * Creates a map containing the specified entries, in the order they
298      * are returned by the map iterator.
299      *
300      * @param map the map whose entries are to be placed into this map.
301      */
302     public FastMap(Map/*<? extends K, ? extends V>*/map) {
303         this(map.size());
304         putAll(map);
305     }
306
307     /**
308      * Creates a fast map having the specified entry table.
309      *
310      * @param entries the entry table.
311      */
312     private FastMap(Entry/*<K,V>*/[][] entries) {
313         _head = new Entry();
314         _tail = new Entry();
315         _head._next = _tail;
316         _tail._previous = _head;
317         _entries = entries;
318     }
319
320     /**
321      * Returns a new, preallocated or {@link #recycle recycled} map instance
322      * (on the stack when executing in a {@link javolution.context.PoolContext
323      * PoolContext}).
324      *
325      * @return a new, preallocated or recycled map instance.
326      */
327     public static/*<K,V>*/FastMap/*<K,V>*/newInstance() {
328         return (FastMap/*<K,V>*/) FACTORY.object();
329     }
330
331     /**
332      * Recycles a map {@link #newInstance() instance} immediately
333      * (on the stack when executing in a {@link javolution.context.PoolContext
334      * PoolContext}).
335      */
336     public static void recycle(FastMap instance) {
337         FACTORY.recycle(instance);
338     }
339
340     /**
341      * Returns the head entry of this map.
342      *
343      * @return the entry such as <code>head().getNext()</code> holds
344      * the first map entry.
345      */
346     public final Entry/*<K,V>*/head() {
347         return _head;
348     }
349
350     /**
351      * Returns the tail entry of this map.
352      *
353      * @return the entry such as <code>tail().getPrevious()</code>
354      * holds the last map entry.
355      */
356     public final Entry/*<K,V>*/tail() {
357         return _tail;
358     }
359
360     /**
361      * Returns the number of key-value mappings in this {@link FastMap}.
362      *
363      * @return this map's size.
364      */
365     public final int size() {
366         return _size;
367     }
368
369     /**
370      * Indicates if this map contains no key-value mappings.
371      *
372      * @return <code>true</code> if this map contains no key-value mappings;
373      * <code>false</code> otherwise.
374      */
375     public final boolean isEmpty() {
376         return _head._next == _tail;
377     }
378
379     /**
380      * Indicates if this map contains a mapping for the specified key.
381      *
382      * @param key the key whose presence in this map is to be tested.
383      * @return <code>true</code> if this map contains a mapping for the
384      * specified key; <code>false</code> otherwise.
385      * @throws NullPointerException if the key is <code>null</code>.
386      */
387     public final boolean containsKey(Object key) {
388         return getEntry(key) != null;
389     }
390
391     /**
392      * Indicates if this map associates one or more keys to the specified value.
393      *
394      * @param value the value whose presence in this map is to be tested.
395      * @return <code>true</code> if this map maps one or more keys to the
396      * specified value.
397      * @throws NullPointerException if the key is <code>null</code>.
398      */
399     public final boolean containsValue(Object value) {
400         return values().contains(value);
401     }
402
403     /**
404      * Returns the value to which this map associates the specified key.
405      *
406      * @param key the key whose associated value is to be returned.
407      * @return the value to which this map maps the specified key, or
408      * <code>null</code> if there is no mapping for the key.
409      * @throws NullPointerException if key is <code>null</code>.
410      */
411     public final Object /*{V}*/get(Object key) {
412         Entry/*<K,V>*/entry = getEntry(key, (_keyComp == null) ? key
413                 .hashCode() : _keyComp.hashCodeOf(key));
414         return (entry != null) ? entry._value : null;
415     }
416
417     /**
418      * Returns the entry with the specified key.
419      *
420      * @param key the key whose associated entry is to be returned.
421      * @return the entry for the specified key or <code>null</code> if none.
422      */
423     public final Entry/*<K,V>*/getEntry(Object key) {
424         return getEntry(key, (_keyComp == null) ? key.hashCode() : _keyComp
425                 .hashCodeOf(key));
426     }
427
428     /**
429      * Associates the specified value with the specified key in this map.
430      * If this map previously contained a mapping for this key, the old value
431      * is replaced. For {@link #isShared() shared} map, internal synchronization
432      * is performed only when new entries are created.
433      *
434      * @param key the key with which the specified value is to be associated.
435      * @param value the value to be associated with the specified key.
436      * @return the previous value associated with specified key, or
437      * <code>null</code> if there was no mapping for key. A
438      * <code>null</code> return can also indicate that the map
439      * previously associated <code>null</code> with the specified key.
440      * @throws NullPointerException if the key is <code>null</code>.
441      */
442     public final Object /*{V}*/put(Object /*{K}*/key, Object /*{V}*/value) {
443         final int keyHash = (_keyComp == null) ? key.hashCode() : _keyComp
444                 .hashCodeOf(key);
445         Entry/*<K,V>*/entry = getEntry(key, keyHash);
446         if (entry != null) {
447             Object /*{V}*/prevValue = entry._value;
448             entry._value = value;
449             return prevValue;
450         }
451         if (_isShared) // Synchronization only if shared and new entry.
452 return putShared(key, value, keyHash);
453         addEntry(keyHash, key, value);
454         return null;
455     }
456
457     private synchronized Object /*{V}*/putShared(Object /*{K}*/key,
458             Object /*{V}*/value, int keyHash) {
459         Entry/*<K,V>*/entry = getEntry(key, keyHash); // To avoid duplicates.
460 if (entry == null) { // Most likely.
461 addEntry(keyHash, key, value);
462             return null;
463         }
464         Object /*{V}*/prevValue = entry._value;
465         entry._value = value;
466         return prevValue;
467     }
468
469     /**
470      * Copies all of the mappings from the specified map to this map.
471      *
472      * @param map the mappings to be stored in this map.
473      * @throws NullPointerException the specified map is <code>null</code>,
474      * or the specified map contains <code>null</code> keys.
475      */
476     public final void putAll(Map/*<? extends K, ? extends V>*/map) {
477         if (map instanceof FastMap) { // Optimization.
478 FastMap/*<? extends K, ? extends V>*/fm = (FastMap/*<? extends K, ? extends V>*/) map;
479             for (Entry/*<? extends K, ? extends V>*/e = fm._head, end = fm._tail; (e = e._next) != end;) {
480                 put(e._key, e._value);
481             }
482         } else {
483             for (Iterator i = map.entrySet().iterator(); i.hasNext();) {
484                 Map.Entry/*<? extends K, ? extends V>*/e = (Map.Entry/*<? extends K, ? extends V>*/) i
485                         .next();
486                 put(e.getKey(), e.getValue());
487             }
488         }
489     }
490
491     /**
492      * Removes the entry for the specified key if present. The entry
493      * is recycled if the map is not marked as {@link #isShared shared};
494      * otherwise the entry is candidate for garbage collection.
495      *
496      * <p> Note: Shared maps in ImmortalMemory (e.g. static) should not remove
497      * their entries as it could cause a memory leak (ImmortalMemory
498      * is never garbage collected), instead they should set their
499      * entry values to <code>null</code>.</p>
500      *
501      * @param key the key whose mapping is to be removed from the map.
502      * @return previous value associated with specified key, or
503      * <code>null</code> if there was no mapping for key. A
504      * <code>null</code> return can also indicate that the map
505      * previously associated <code>null</code> with the specified key.
506      * @throws NullPointerException if the key is <code>null</code>.
507      */
508     public final Object /*{V}*/remove(Object key) {
509         Entry/*<K,V>*/entry = getEntry(key);
510         if (entry == null)
511             return null;
512         if (_isShared) // Synchronization only if shared and entry exists.
513 return removeShared(entry);
514         Object /*{V}*/prevValue = entry._value;
515         removeEntry(entry);
516         return prevValue;
517     }
518
519     private synchronized Object /*{V}*/removeShared(Entry/*<K,V>*/entry) {
520         _size--;
521         entry.detach();
522         return entry._value;
523     }
524
525     /**
526      * <p> Sets the shared status of this map (whether the map is thread-safe
527      * or not). Shared maps are typically used for lookup table (e.g. static
528      * instances in ImmortalMemory). They support concurrent access
529      * (e.g. iterations) without synchronization, the maps updates
530      * themselves are synchronized internally.</p>
531      * <p> Unlike <code>ConcurrentHashMap</code> access to a shared map never
532      * blocks. Retrieval reflects the map state not older than the last
533      * time the accessing thread has been synchronized (for multi-processors
534      * systems synchronizing ensures that the CPU internal cache is not
535      * stale).</p>
536      *
537      * @param isShared <code>true</code> if this map is shared and thread-safe;
538      * <code>false</code> otherwise.
539      * @return <code>this</code>
540      */
541     public FastMap/*<K,V>*/setShared(boolean isShared) {
542         _isShared = isShared;
543         return this;
544     }
545
546     /**
547      * Indicates if this map supports concurrent operations without
548      * synchronization (default unshared).
549      *
550      * @return <code>true</code> if this map is thread-safe; <code>false</code>
551      * otherwise.
552      */
553     public boolean isShared() {
554         return _isShared;
555     }
556
557     /**
558      * Sets the key comparator for this fast map.
559      *
560      * @param keyComparator the key comparator.
561      * @return <code>this</code>
562      */
563     public FastMap/*<K,V>*/setKeyComparator(FastComparator/*<? super K>*/ keyComparator) {
564         _keyComparator = keyComparator;
565         _keyComp = (keyComparator instanceof FastComparator.Default) ?
566                 (FastComparator._Rehash ? FastComparator.REHASH : null)
567                 : (keyComparator instanceof FastComparator.Direct) ? null
568                         : keyComparator;
569         return this;
570     }
571
572     /**
573      * Returns the key comparator for this fast map.
574      *
575      * @return the key comparator.
576      */
577     public FastComparator/*<? super K>*/ getKeyComparator() {
578         return _keyComparator;
579     }
580
581     /**
582      * Sets the value comparator for this map.
583      *
584      * @param valueComparator the value comparator.
585      * @return <code>this</code>
586      */
587     public FastMap/*<K,V>*/setValueComparator(FastComparator/*<? super V>*/ valueComparator) {
588         _valueComparator = valueComparator;
589         return this;
590     }
591
592     /**
593      * Returns the value comparator for this fast map.
594      *
595      * @return the value comparator.
596      */
597     public FastComparator/*<? super V>*/ getValueComparator() {
598         return _valueComparator;
599     }
600
601     /**
602      * Removes all map's entries. The entries are removed and recycled;
603      * unless this map is {@link #isShared shared} in which case the entries
604      * are candidate for garbage collection.
605      *
606      * <p> Note: Shared maps in ImmortalMemory (e.g. static) should not remove
607      * their entries as it could cause a memory leak (ImmortalMemory
608      * is never garbage collected), instead they should set their
609      * entry values to <code>null</code>.</p>
610      */
611     public final void clear() {
612         if (_isShared) {
613             clearShared();
614             return;
615         }
616         // Clears all keys, values and buckets linked lists.
617 for (Entry/*<K,V>*/e = _head, end = _tail; (e = e._next) != end;) {
618             e._key = null;
619             e._value = null;
620             final Entry/*<K,V>*/[][] table = e._table;
621             table[(e._keyHash >> R0) & (table.length - 1)][e._keyHash & M0] = null;
622         }
623         _tail = _head._next;
624         _size = 0;
625
626         // Discards old entries.
627 _oldEntries = null;
628     }
629
630     private synchronized void clearShared() {
631         for (Entry/*<K,V>*/e = _head, end = _tail; (e = e._next) != end;) {
632             final Entry/*<K,V>*/[][] table = e._table;
633             table[(e._keyHash >> R0) & (table.length - 1)][e._keyHash & M0] = null;
634         }
635         _head._next = _tail; // Does not modify current linked list.
636 _tail._previous = _head; //
637 _oldEntries = null;
638         _size = 0;
639     }
640
641     /**
642      * Compares the specified object with this map for equality.
643      * Returns <code>true</code> if the given object is also a map and the two
644      * maps represent the same mappings (regardless of collection iteration
645      * order).
646      *
647      * @param obj the object to be compared for equality with this map.
648      * @return <code>true</code> if the specified object is equal to this map;
649      * <code>false</code> otherwise.
650      */
651     public boolean equals(Object obj) {
652         if (obj == this) {
653             return true;
654         } else if (obj instanceof Map) {
655             Map/*<?,?>*/that = (Map) obj;
656             return this.entrySet().equals(that.entrySet());
657         } else {
658             return false;
659         }
660     }
661
662     /**
663      * Returns the hash code value for this map.
664      *
665      * @return the hash code value for this map.
666      */
667     public int hashCode() {
668         int code = 0;
669         for (Entry e = _head, end = _tail; (e = e._next) != end;) {
670             code += e.hashCode();
671         }
672         return code;
673     }
674
675     /**
676      * Returns the textual representation of this map.
677      *
678      * @return the textual representation of the entry set.
679      */
680     public Text toText() {
681         return Text.valueOf(entrySet());
682     }
683
684     /**
685      * Prints the current statistics on this map.
686      * This method may help identify poorly defined hash functions.
687      * An average collision of less than <code>50%</code> is typically
688      * acceptable.
689      *
690      * @param out the stream to use for output (e.g. <code>System.out</code>)
691      */
692     public void printStatistics(PrintStream out) {
693         int maxOccupancy = 0;
694         int totalCollisions = 0;
695         int size = 0;
696         for (int i = 0; i < _entries.length; i++) {
697             for (int j = 0; j < _entries[i].length; j++) {
698                 Entry entry = _entries[i][j];
699                 int occupancy = 0;
700                 while (entry != null) {
701                     occupancy++;
702                     if (occupancy > maxOccupancy) {
703                         maxOccupancy = occupancy;
704                     }
705                     if (occupancy > 1) {
706                         totalCollisions++;
707                     }
708                     entry = entry._beside;
709                     size++;
710                 }
711             }
712         }
713         TextBuilder percentCollisions = TextBuilder.newInstance();
714         if (size != 0) {
715             percentCollisions.append((100 * totalCollisions) / size);
716             percentCollisions.append('%');
717         } else {
718             percentCollisions.append("N/A");
719         }
720         synchronized (out) {
721             out.print("SIZE: " + size);
722             out
723                     .print(", TABLE LENGTH: " + _entries.length
724                             * _entries[0].length);
725             out.print(", AVG COLLISIONS: " + percentCollisions);
726             out.print(", MAX SLOT OCCUPANCY: " + maxOccupancy);
727             out.print(", KEY COMPARATOR: "
728                     + ((_keyComp == null) ? FastComparator.DIRECT : _keyComp));
729             out.print(", SHARED: " + _isShared);
730             out.println();
731             if (_oldEntries != null) {
732                 out.print(" + ");
733                 _oldEntries.printStatistics(out);
734             }
735         }
736     }
737
738     /**
739      * Returns a {@link FastCollection} view of the values contained in this
740      * map. The collection is backed by the map, so changes to the
741      * map are reflected in the collection, and vice-versa. The collection
742      * supports element removal, which removes the corresponding mapping from
743      * this map, via the <code>Iterator.remove</code>,
744      * <code>Collection.remove</code>, <code>removeAll</code>,
745      * <code>retainAll</code> and <code>clear</code> operations.
746      * It does not support the <code>add</code> or <code>addAll</code>
747      * operations.
748      *
749      * @return a collection view of the values contained in this map
750      * (instance of {@link FastCollection}).
751      */
752     public final Collection/*<V>*/values() {
753         if (_values == null) {
754             MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
755                 public void run() {
756                     _values = new Values();
757                 }
758             });
759         }
760         return _values;
761     }
762
763     private final class Values extends FastCollection {
764
765         public int size() {
766             return _size;
767         }
768
769         public void clear() {
770             FastMap.this.clear();
771         }
772
773         public Record head() {
774             return FastMap.this._head;
775         }
776
777         public Record tail() {
778             return FastMap.this._tail;
779         }
780
781         public Object valueOf(Record record) {
782             return ((Entry) record)._value;
783         }
784
785         public void delete(Record record) {
786             FastMap.this.remove(((Entry) record).getKey());
787         }
788         
789         public FastComparator getValueComparator() {
790             return _valueComparator;
791         }
792     }
793
794     /**
795      * Returns a {@link FastCollection} view of the mappings contained in this
796      * map. Each element in the returned collection is a
797      * <code>FastMap.Entry</code>. The collection is backed by the map, so
798      * changes to the map are reflected in the collection, and vice-versa. The
799      * collection supports element removal, which removes the corresponding
800      * mapping from this map, via the <code>Iterator.remove</code>,
801      * <code>Collection.remove</code>,<code>removeAll</code>,
802      * <code>retainAll</code>, and <code>clear</code> operations. It does
803      * not support the <code>add</code> or <code>addAll</code> operations.
804      *
805      * @return a collection view of the mappings contained in this map
806      * (instance of {@link FastCollection}).
807      */
808     public final Set/*<Map.Entry<K,V>>*/entrySet() {
809         if (_entrySet == null) {
810             MemoryArea.getMemoryArea(this).executeInArea(new Runnable () {
811                 public void run() {
812                     _entrySet = new EntrySet();
813                 }
814             });
815         }
816         return _entrySet;
817     }
818
819     private final class EntrySet extends FastCollection implements Set {
820
821         public int size() {
822             return _size;
823         }
824
825         public void clear() {
826             FastMap.this.clear();
827         }
828
829         public boolean contains(Object obj) { // Optimization.
830 if (obj instanceof Map.Entry) {
831                 Map.Entry thatEntry = (Entry) obj;
832                 Entry thisEntry = getEntry(thatEntry.getKey());
833                 if (thisEntry == null) return false;
834                 return _valueComparator.areEqual(thisEntry.getValue(), thatEntry.getValue());
835             } else {
836                 return false;
837             }
838         }
839
840         public Text toText() {
841             Text text = Text.valueOf('[');
842             final Text equ = Text.valueOf('=');
843             final Text sep = Text.valueOf(", ");
844             for (Entry e = _head, end = _tail; (e = e._next) != end;) {
845                 text = text.concat(Text.valueOf(e._key)).concat(equ).concat(
846                         Text.valueOf(e._value));
847                 if (e._next != end) {
848                     text = text.concat(sep);
849                 }
850             }
851             return text.concat(Text.valueOf(']'));
852         }
853
854         public Record head() {
855             return _head;
856         }
857
858         public Record tail() {
859             return _tail;
860         }
861
862         public Object valueOf(Record record) {
863             return (Map.Entry) record;
864         }
865
866         public void delete(Record record) {
867             FastMap.this.remove(((Entry) record).getKey());
868         }
869         
870         public FastComparator getValueComparator() {
871             return _entryComparator;
872         }
873         private final FastComparator _entryComparator = new FastComparator() {
874
875             public boolean areEqual(Object o1, Object o2) {
876                 if ((o1 instanceof Map.Entry) && (o2 instanceof Map.Entry)) {
877                     Map.Entry e1 = (Map.Entry) o1;
878                     Map.Entry e2 = (Map.Entry) o2;
879                     return _keyComparator.areEqual(e1.getKey(), e2.getKey()) &&
880                        _valueComparator.areEqual(e1.getValue(), e2.getValue());
881                 }
882                 return (o1 == null) && (o2 == null);
883             }
884
885             public int compare(Object o1, Object o2) {
886                 return _keyComparator.compare(o1, o2);
887             }
888
889             public int hashCodeOf(Object obj) {
890                 Map.Entry entry = (Map.Entry) obj;
891                 return _keyComparator.hashCodeOf(entry.