Java > Open Source Codes > org > apache > commons > collections > map > AbstractHashedMap


1 /*
2  * Copyright 2003-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.map;
17
18 import java.io.IOException ;
19 import java.io.ObjectInputStream ;
20 import java.io.ObjectOutputStream ;
21 import java.util.AbstractCollection ;
22 import java.util.AbstractMap ;
23 import java.util.AbstractSet ;
24 import java.util.Collection ;
25 import java.util.ConcurrentModificationException ;
26 import java.util.Iterator ;
27 import java.util.Map ;
28 import java.util.NoSuchElementException ;
29 import java.util.Set ;
30
31 import org.apache.commons.collections.IterableMap;
32 import org.apache.commons.collections.KeyValue;
33 import org.apache.commons.collections.MapIterator;
34 import org.apache.commons.collections.iterators.EmptyIterator;
35 import org.apache.commons.collections.iterators.EmptyMapIterator;
36
37 /**
38  * An abstract implementation of a hash-based map which provides numerous points for
39  * subclasses to override.
40  * <p>
41  * This class implements all the features necessary for a subclass hash-based map.
42  * Key-value entries are stored in instances of the <code>HashEntry</code> class,
43  * which can be overridden and replaced. The iterators can similarly be replaced,
44  * without the need to replace the KeySet, EntrySet and Values view classes.
45  * <p>
46  * Overridable methods are provided to change the default hashing behaviour, and
47  * to change how entries are added to and removed from the map. Hopefully, all you
48  * need for unusual subclasses is here.
49  * <p>
50  * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
51  * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
52  * This extends clause will be removed in v4.0.
53  *
54  * @since Commons Collections 3.0
55  * @version $Revision: 1.20 $ $Date: 2004/06/22 21:42:12 $
56  *
57  * @author java util HashMap
58  * @author Stephen Colebourne
59  */
60 public class AbstractHashedMap extends AbstractMap implements IterableMap {
61     
62     protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
63     protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
64     protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
65     protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
66     protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
67     protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
68     
69     /** The default capacity to use */
70     protected static final int DEFAULT_CAPACITY = 16;
71     /** The default threshold to use */
72     protected static final int DEFAULT_THRESHOLD = 12;
73     /** The default load factor to use */
74     protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
75     /** The maximum capacity allowed */
76     protected static final int MAXIMUM_CAPACITY = 1 << 30;
77     /** An object for masking null */
78     protected static final Object NULL = new Object ();
79     
80     /** Load factor, normally 0.75 */
81     protected transient float loadFactor;
82     /** The size of the map */
83     protected transient int size;
84     /** Map entries */
85     protected transient HashEntry[] data;
86     /** Size at which to rehash */
87     protected transient int threshold;
88     /** Modification count for iterators */
89     protected transient int modCount;
90     /** Entry set */
91     protected transient EntrySet entrySet;
92     /** Key set */
93     protected transient KeySet keySet;
94     /** Values */
95     protected transient Values values;
96
97     /**
98      * Constructor only used in deserialization, do not use otherwise.
99      */
100     protected AbstractHashedMap() {
101         super();
102     }
103
104     /**
105      * Constructor which performs no validation on the passed in parameters.
106      *
107      * @param initialCapacity the initial capacity, must be a power of two
108      * @param loadFactor the load factor, must be &gt; 0.0f and generally &lt; 1.0f
109      * @param threshold the threshold, must be sensible
110      */
111     protected AbstractHashedMap(int initialCapacity, float loadFactor, int threshold) {
112         super();
113         this.loadFactor = loadFactor;
114         this.data = new HashEntry[initialCapacity];
115         this.threshold = threshold;
116         init();
117     }
118
119     /**
120      * Constructs a new, empty map with the specified initial capacity and
121      * default load factor.
122      *
123      * @param initialCapacity the initial capacity
124      * @throws IllegalArgumentException if the initial capacity is less than one
125      */
126     protected AbstractHashedMap(int initialCapacity) {
127         this(initialCapacity, DEFAULT_LOAD_FACTOR);
128     }
129
130     /**
131      * Constructs a new, empty map with the specified initial capacity and
132      * load factor.
133      *
134      * @param initialCapacity the initial capacity
135      * @param loadFactor the load factor
136      * @throws IllegalArgumentException if the initial capacity is less than one
137      * @throws IllegalArgumentException if the load factor is less than or equal to zero
138      */
139     protected AbstractHashedMap(int initialCapacity, float loadFactor) {
140         super();
141         if (initialCapacity < 1) {
142             throw new IllegalArgumentException ("Initial capacity must be greater than 0");
143         }
144         if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
145             throw new IllegalArgumentException ("Load factor must be greater than 0");
146         }
147         this.loadFactor = loadFactor;
148         this.threshold = calculateThreshold(initialCapacity, loadFactor);
149         initialCapacity = calculateNewCapacity(initialCapacity);
150         this.data = new HashEntry[initialCapacity];
151         init();
152     }
153
154     /**
155      * Constructor copying elements from another map.
156      *
157      * @param map the map to copy
158      * @throws NullPointerException if the map is null
159      */
160     protected AbstractHashedMap(Map map) {
161         this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
162         putAll(map);
163     }
164
165     /**
166      * Initialise subclasses during construction, cloning or deserialization.
167      */
168     protected void init() {
169     }
170
171     //-----------------------------------------------------------------------
172 /**
173      * Gets the value mapped to the key specified.
174      *
175      * @param key the key
176      * @return the mapped value, null if no match
177      */
178     public Object get(Object key) {
179         key = convertKey(key);
180         int hashCode = hash(key);
181         HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
182 while (entry != null) {
183             if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
184                 return entry.getValue();
185             }
186             entry = entry.next;
187         }
188         return null;
189     }
190
191     /**
192      * Gets the size of the map.
193      *
194      * @return the size
195      */
196     public int size() {
197         return size;
198     }
199
200     /**
201      * Checks whether the map is currently empty.
202      *
203      * @return true if the map is currently size zero
204      */
205     public boolean isEmpty() {
206         return (size == 0);
207     }
208
209     //-----------------------------------------------------------------------
210 /**
211      * Checks whether the map contains the specified key.
212      *
213      * @param key the key to search for
214      * @return true if the map contains the key
215      */
216     public boolean containsKey(Object key) {
217         key = convertKey(key);
218         int hashCode = hash(key);
219         HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
220 while (entry != null) {
221             if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
222                 return true;
223             }
224             entry = entry.next;
225         }
226         return false;
227     }
228
229     /**
230      * Checks whether the map contains the specified value.
231      *
232      * @param value the value to search for
233      * @return true if the map contains the value
234      */
235     public boolean containsValue(Object value) {
236         if (value == null) {
237             for (int i = 0, isize = data.length; i < isize; i++) {
238                 HashEntry entry = data[i];
239                 while (entry != null) {
240                     if (entry.getValue() == null) {
241                         return true;
242                     }
243                     entry = entry.next;
244                 }
245             }
246         } else {
247             for (int i = 0, isize = data.length; i < isize; i++) {
248                 HashEntry entry = data[i];
249                 while (entry != null) {
250                     if (isEqualValue(value, entry.getValue())) {
251                         return true;
252                     }
253                     entry = entry.next;
254                 }
255             }
256         }
257         return false;
258     }
259
260     //-----------------------------------------------------------------------
261 /**
262      * Puts a key-value mapping into this map.
263      *
264      * @param key the key to add
265      * @param value the value to add
266      * @return the value previously mapped to this key, null if none
267      */
268     public Object put(Object key, Object value) {
269         key = convertKey(key);
270         int hashCode = hash(key);
271         int index = hashIndex(hashCode, data.length);
272         HashEntry entry = data[index];
273         while (entry != null) {
274             if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
275                 Object oldValue = entry.getValue();
276                 updateEntry(entry, value);
277                 return oldValue;
278             }
279             entry = entry.next;
280         }
281         
282         addMapping(index, hashCode, key, value);
283         return null;
284     }
285
286     /**
287      * Puts all the values from the specified map into this map.
288      * <p>
289      * This implementation iterates around the specified map and
290      * uses {@link #put(Object, Object)}.
291      *
292      * @param map the map to add
293      * @throws NullPointerException if the map is null
294      */
295     public void putAll(Map map) {
296         int mapSize = map.size();
297         if (mapSize == 0) {
298             return;
299         }
300         int newSize = (int) ((size + mapSize) / loadFactor + 1);
301         ensureCapacity(calculateNewCapacity(newSize));
302         for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
303             Map.Entry entry = (Map.Entry ) it.next();
304             put(entry.getKey(), entry.getValue());
305         }
306     }
307
308     /**
309      * Removes the specified mapping from this map.
310      *
311      * @param key the mapping to remove
312      * @return the value mapped to the removed key, null if key not in map
313      */
314     public Object remove(Object key) {
315         key = convertKey(key);
316         int hashCode = hash(key);
317         int index = hashIndex(hashCode, data.length);
318         HashEntry entry = data[index];
319         HashEntry previous = null;
320         while (entry != null) {
321             if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
322                 Object oldValue = entry.getValue();
323                 removeMapping(entry, index, previous);
324                 return oldValue;
325             }
326             previous = entry;
327             entry = entry.next;
328         }
329         return null;
330     }
331
332     /**
333      * Clears the map, resetting the size to zero and nullifying references
334      * to avoid garbage collection issues.
335      */
336     public void clear() {
337         modCount++;
338         HashEntry[] data = this.data;
339         for (int i = data.length - 1; i >= 0; i--) {
340             data[i] = null;
341         }
342         size = 0;
343     }
344
345     //-----------------------------------------------------------------------
346 /**
347      * Converts input keys to another object for storage in the map.
348      * This implementation masks nulls.
349      * Subclasses can override this to perform alternate key conversions.
350      * <p>
351      * The reverse conversion can be changed, if required, by overriding the
352      * getKey() method in the hash entry.
353      *
354      * @param key the key convert
355      * @return the converted key
356      */
357     protected Object convertKey(Object key) {
358         return (key == null ? NULL : key);
359     }
360     
361     /**
362      * Gets the hash code for the key specified.
363      * This implementation uses the additional hashing routine from JDK1.4.
364      * Subclasses can override this to return alternate hash codes.
365      *
366      * @param key the key to get a hash code for
367      * @return the hash code
368      */
369     protected int hash(Object key) {
370         // same as JDK 1.4
371 int h = key.hashCode();
372         h += ~(h << 9);
373         h ^= (h >>> 14);
374         h += (h << 4);
375         h ^= (h >>> 10);
376         return h;
377     }
378     
379     /**
380      * Compares two keys, in internal converted form, to see if they are equal.
381      * This implementation uses the equals method and assumes neither key is null.
382      * Subclasses can override this to match differently.
383      *
384      * @param key1 the first key to compare passed in from outside
385      * @param key2 the second key extracted from the entry via <code>entry.key</code>
386      * @return true if equal
387      */
388     protected boolean isEqualKey(Object key1, Object key2) {
389         return (key1 == key2 || key1.equals(key2));
390     }
391     
392     /**
393      * Compares two values, in external form, to see if they are equal.
394      * This implementation uses the equals method and assumes neither value is null.
395      * Subclasses can override this to match differently.
396      *
397      * @param value1 the first value to compare passed in from outside
398      * @param value2 the second value extracted from the entry via <code>getValue()</code>
399      * @return true if equal
400      */
401     protected boolean isEqualValue(Object value1, Object value2) {
402         return (value1 == value2 || value1.equals(value2));
403     }
404     
405     /**
406      * Gets the index into the data storage for the hashCode specified.
407      * This implementation uses the least significant bits of the hashCode.
408      * Subclasses can override this to return alternate bucketing.
409      *
410      * @param hashCode the hash code to use
411      * @param dataSize the size of the data to pick a bucket from
412      * @return the bucket index
413      */
414     protected int hashIndex(int hashCode, int dataSize) {
415         return hashCode & (dataSize - 1);
416     }
417     
418     //-----------------------------------------------------------------------
419 /**
420      * Gets the entry mapped to the key specified.
421      * <p>
422      * This method exists for subclasses that may need to perform a multi-step
423      * process accessing the entry. The public methods in this class don't use this
424      * method to gain a small performance boost.
425      *
426      * @param key the key
427      * @return the entry, null if no match
428      */
429     protected HashEntry getEntry(Object key) {
430         key = convertKey(key);
431         int hashCode = hash(key);
432         HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
433 while (entry != null) {
434             if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
435                 return entry;
436             }
437             entry = entry.next;
438         }
439         return null;
440     }
441
442     //-----------------------------------------------------------------------
443 /**
444      * Updates an existing key-value mapping to change the value.
445      * <p>
446      * This implementation calls <code>setValue()</code> on the entry.
447      * Subclasses could override to handle changes to the map.
448      *
449      * @param entry the entry to update
450      * @param newValue the new value to store
451      */
452     protected void updateEntry(HashEntry entry, Object newValue) {
453         entry.setValue(newValue);
454     }
455     
456     /**
457      * Reuses an existing key-value mapping, storing completely new data.
458      * <p>
459      * This implementation sets all the data fields on the entry.
460      * Subclasses could populate additional entry fields.
461      *
462      * @param entry the entry to update, not null
463      * @param hashIndex the index in the data array
464      * @param hashCode the hash code of the key to add
465      * @param key the key to add
466      * @param value the value to add
467      */
468     protected void reuseEntry(HashEntry entry, int hashIndex, int hashCode, Object key, Object value) {
469         entry.next = data[hashIndex];
470         entry.hashCode = hashCode;
471         entry.key = key;
472         entry.value = value;
473     }
474     
475     //-----------------------------------------------------------------------
476 /**
477      * Adds a new key-value mapping into this map.
478      * <p>
479      * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
480      * and <code>checkCapacity()</code>.
481      * It also handles changes to <code>modCount</code> and <code>size</code>.
482      * Subclasses could override to fully control adds to the map.
483      *
484      * @param hashIndex the index into the data array to store at
485      * @param hashCode the hash code of the key to add
486      * @param key the key to add
487      * @param value the value to add
488      */
489     protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
490         modCount++;
491         HashEntry entry = createEntry(data[hashIndex], hashCode, key, value);
492         addEntry(entry, hashIndex);
493         size++;
494         checkCapacity();
495     }
496     
497     /**
498      * Creates an entry to store the key-value data.
499      * <p>
500      * This implementation creates a new HashEntry instance.
501      * Subclasses can override this to return a different storage class,
502      * or implement caching.
503      *
504      * @param next the next entry in sequence
505      * @param hashCode the hash code to use
506      * @param key the key to store
507      * @param value the value to store
508      * @return the newly created entry
509      */
510     protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
511         return new HashEntry(next, hashCode, key, value);
512     }
513     
514     /**
515      * Adds an entry into this map.
516      * <p>
517      * This implementation adds the entry to the data storage table.
518      * Subclasses could override to handle changes to the map.
519      *
520      * @param entry the entry to add
521      * @param hashIndex the index into the data array to store at
522      */
523     protected void addEntry(HashEntry entry, int hashIndex) {
524         data[hashIndex] = entry;
525     }
526     
527     //-----------------------------------------------------------------------
528 /**
529      * Removes a mapping from the map.
530      * <p>
531      * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
532      * It also handles changes to <code>modCount</code> and <code>size</code>.
533      * Subclasses could override to fully control removals from the map.
534      *
535      * @param entry the entry to remove
536      * @param hashIndex the index into the data structure
537      * @param previous the previous entry in the chain
538      */
539     protected void removeMapping(HashEntry entry, int hashIndex, HashEntry previous) {
540         modCount++;
541         removeEntry(entry, hashIndex, previous);
542         size--;
543         destroyEntry(entry);
544     }
545     
546     /**
547      * Removes an entry from the chain stored in a particular index.
548      * <p>
549      * This implementation removes the entry from the data storage table.
550      * The size is not updated.
551      * Subclasses could override to handle changes to the map.
552      *
553      * @param entry the entry to remove
554      * @param hashIndex the index into the data structure
555      * @param previous the previous entry in the chain
556      */
557     protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
558         if (previous == null) {
559             data[hashIndex] = entry.next;
560         } else {
561             previous.next = entry.next;
562         }
563     }
564     
565     /**
566      * Kills an entry ready for the garbage collector.
567      * <p>
568      * This implementation prepares the HashEntry for garbage collection.
569      * Subclasses can override this to implement caching (override clear as well).
570      *
571      * @param entry the entry to destroy
572      */
573     protected void destroyEntry(HashEntry entry) {
574         entry.next = null;
575         entry.key = null;
576         entry.value = null;
577     }
578     
579     //-----------------------------------------------------------------------
580 /**
581      * Checks the capacity of the map and enlarges it if necessary.
582      * <p>
583      * This implementation uses the threshold to check if the map needs enlarging
584      */
585     protected void checkCapacity() {
586         if (size >= threshold) {
587             int newCapacity = data.length * 2;
588             if (newCapacity <= MAXIMUM_CAPACITY) {
589                 ensureCapacity(newCapacity);
590             }
591         }
592     }
593     
594     /**
595      * Changes the size of the data structure to the capacity proposed.
596      *
597      * @param newCapacity the new capacity of the array (a power of two, less or equal to max)
598      */
599     protected void ensureCapacity(int newCapacity) {
600         int oldCapacity = data.length;
601         if (newCapacity <= oldCapacity) {
602             return;
603         }
604         if (size == 0) {
605             threshold = calculateThreshold(newCapacity, loadFactor);
606             data = new HashEntry[newCapacity];
607         } else {
608             HashEntry oldEntries[] = data;
609             HashEntry newEntries[] = new HashEntry[newCapacity];
610
611             modCount++;
612             for (int i = oldCapacity - 1; i >= 0; i--) {
613                 HashEntry entry = oldEntries[i];
614                 if (entry != null) {
615                     oldEntries[i] = null; // gc
616 do {
617                         HashEntry next = entry.next;
618                         int index = hashIndex(entry.hashCode, newCapacity);
619                         entry.next = newEntries[index];
620                         newEntries[index] = entry;
621                         entry = next;
622                     } while (entry != null);
623                 }
624             }
625             threshold = calculateThreshold(newCapacity, loadFactor);
626             data = newEntries;
627         }
628     }
629
630     /**
631      * Calculates the new capacity of the map.
632      * This implementation normalizes the capacity to a power of two.
633      *
634      * @param proposedCapacity the proposed capacity
635      * @return the normalized new capacity
636      */
637     protected int calculateNewCapacity(int proposedCapacity) {
638         int newCapacity = 1;
639         if (proposedCapacity > MAXIMUM_CAPACITY) {
640             newCapacity = MAXIMUM_CAPACITY;
641         } else {
642             while (newCapacity < proposedCapacity) {
643                 newCapacity <<= 1; // multiply by two
644 }
645             if (newCapacity > MAXIMUM_CAPACITY) {
646                 newCapacity = MAXIMUM_CAPACITY;
647             }
648         }
649         return newCapacity;
650     }
651     
652     /**
653      * Calculates the new threshold of the map, where it will be resized.
654      * This implementation uses the load factor.
655      *
656      * @param newCapacity the new capacity
657      * @param factor the load factor
658      * @return the new resize threshold
659      */
660     protected int calculateThreshold(int newCapacity, float factor) {
661         return (int) (newCapacity * factor);
662     }
663     
664     //-----------------------------------------------------------------------
665 /**
666      * Gets the <code>next</code> field from a <code>HashEntry</code>.
667      * Used in subclasses that have no visibility of the field.
668      *
669      * @param entry the entry to query, must not be null
670      * @return the <code>next</code> field of the entry
671      * @throws NullPointerException if the entry is null
672      * @since Commons Collections 3.1
673      */
674     protected HashEntry entryNext(HashEntry entry) {
675         return entry.next;
676     }
677     
678     /**
679      * Gets the <code>hashCode</code> field from a <code>HashEntry</code>.
680      * Used in subclasses that have no visibility of the field.
681      *
682      * @param entry the entry to query, must not be null
683      * @return the <code>hashCode</code> field of the entry
684      * @throws NullPointerException if the entry is null
685      * @since Commons Collections 3.1
686      */
687     protected int entryHashCode(HashEntry entry) {
688         return entry.hashCode;
689     }
690     
691     /**
692      * Gets the <code>key</code> field from a <code>HashEntry</code>.
693      * Used in subclasses that have no visibility of the field.
694      *
695      * @param entry the entry to query, must not be null
696      * @return the <code>key</code> field of the entry
697      * @throws NullPointerException if the entry is null
698      * @since Commons Collections 3.1
699      */
700     protected Object entryKey(HashEntry entry) {
701         return entry.key;
702     }
703     
704     /**
705      * Gets the <code>value</code> field from a <code>HashEntry</code>.
706      * Used in subclasses that have no visibility of the field.
707      *
708      * @param entry the entry to query, must not be null
709      * @return the <code>value</code> field of the entry
710      * @throws NullPointerException if the entry is null
711      * @since Commons Collections 3.1
712      */
713     protected Object entryValue(HashEntry entry) {
714         return entry.value;
715     }
716     
717     //-----------------------------------------------------------------------
718 /**
719      * Gets an iterator over the map.
720      * Changes made to the iterator affect this map.
721      * <p>
722      * A MapIterator returns the keys in the map. It also provides convenient
723      * methods to get the key and value, and set the value.
724      * It avoids the need to create an entrySet/keySet/values object.
725      * It also avoids creating the Map.Entry object.
726      *
727      * @return the map iterator
728      */
729     public MapIterator mapIterator() {
730         if (size == 0) {
731             return EmptyMapIterator.INSTANCE;
732         }
733         return new HashMapIterator(this);
734     }
735
736     /**
737      * MapIterator implementation.
738      */
739     protected static class HashMapIterator extends HashIterator implements MapIterator {
740         
741         protected HashMapIterator(AbstractHashedMap parent) {
742             super(parent);
743         }
744
745         public Object next() {
746             return super.nextEntry().getKey();
747         }
748
749         public Object getKey() {
750             HashEntry current = currentEntry();
751             if (current == null) {
752                 throw new IllegalStateException (AbstractHashedMap.GETKEY_INVALID);
753             }
754             return current.getKey();
755         }
756
757         public Object getValue() {
758             HashEntry current = currentEntry();
759             if (current == null) {
760                 throw new IllegalStateException (AbstractHashedMap.GETVALUE_INVALID);
761             }
762             return current.getValue();
763         }
764
765         public Object setValue(Object value) {
766             HashEntry current = currentEntry();
767             if (current == null) {
768                 throw new IllegalStateException (AbstractHashedMap.SETVALUE_INVALID);
769             }
770             return current.setValue(value);
771         }
772     }
773     
774     //-----------------------------------------------------------------------
775 /**
776      * Gets the entrySet view of the map.
777      * Changes made to the view affect this map.
778      * To simply iterate through the entries, use {@link #mapIterator()}.
779      *
780      * @return the entrySet view
781      */
782     public Set entrySet() {
783         if (entrySet == null) {
784             entrySet = new EntrySet(this);
785         }
786         return entrySet;
787     }
788     
789     /**
790      * Creates an entry set iterator.
791      * Subclasses can override this to return iterators with different properties.
792      *
793      * @return the entrySet iterator
794      */
795     protected Iterator createEntrySetIterator() {
796         if (size() == 0) {
797             return EmptyIterator.INSTANCE;
798         }
799         return new EntrySetIterator(this);
800     }
801
802     /**
803      * EntrySet implementation.
804      */
805     protected static class EntrySet extends AbstractSet {
806         /** The parent map */
807         protected final AbstractHashedMap parent;
808         
809         protected EntrySet(AbstractHashedMap parent) {
810             super();
811             this.parent = parent;
812         }
813
814         public int size() {
815             return parent.size();
816         }
817         
818         public void clear() {
819             parent.clear();
820         }
821         
822         public boolean contains(Object entry) {
823             if (entry instanceof Map.Entry ) {
824                 Map.Entry e = (Map.Entry ) entry;
825                 Entry match = parent.getEntry(e.getKey());
826                 return (match != null && match.equals(e));
827             }
828             return false;
829         }
830         
831         public boolean remove(Object obj) {
832             if (obj instanceof Map.Entry == false) {
833                 return false;
834             }
835             if (contains(obj) == false) {
836                 return false;
837             }
838             Map.Entry entry = (Map.Entry ) obj;
839             Object key = entry.getKey();
840             parent.remove(key);
841             return true;
842         }
843
844         public Iterator iterator() {
845             return parent.createEntrySetIterator();
846         }
847     }
848
849     /**
850      * EntrySet iterator.
851      */
852     protected static class EntrySetIterator extends HashIterator {
853         
854         protected EntrySetIterator(AbstractHashedMap parent) {
855             super(parent);
856         }
857
858         public Object next() {
859             return super.nextEntry();
860         }
861     }
862
863     //-----------------------------------------------------------------------
864 /**
865      * Gets the keySet view of the map.
866      * Changes made to the view affect this map.
867      * To simply iterate through the keys, use {@link #mapIterator()}.
868      *
869      * @return the keySet view
870      */
871     public Set keySet() {
872         if (keySet == null) {
873             keySet = new KeySet(this);
874         }
875         return keySet;
876     }
877
878     /**
879      * Creates a key set iterator.
880      * Subclasses can override this to return iterators with different properties.
881      *
882      * @return the keySet iterator
883      */
884     protected Iterator createKeySetIterator() {
885         if (size() == 0) {
886             return EmptyIterator.INSTANCE;
887         }
888         return new KeySetIterator(this);
889     }
890
891     /**
892      * KeySet implementation.
893      */
894