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     protected static class KeySet extends AbstractSet {
895         /** The parent map */
896         protected final AbstractHashedMap parent;
897         
898         protected KeySet(AbstractHashedMap parent) {
899             super();
900             this.parent = parent;
901         }
902
903         public int size() {
904             return parent.size();
905         }
906         
907         public void clear() {
908             parent.clear();
909         }
910         
911         public boolean contains(Object key) {
912             return parent.containsKey(key);
913         }
914         
915         public boolean remove(Object key) {
916             boolean result = parent.containsKey(key);
917             parent.remove(key);
918             return result;
919         }
920
921         public Iterator iterator() {
922             return parent.createKeySetIterator();
923         }
924     }
925
926     /**
927      * KeySet iterator.
928      */
929     protected static class KeySetIterator extends EntrySetIterator {
930         
931         protected KeySetIterator(AbstractHashedMap parent) {
932             super(parent);
933         }
934
935         public Object next() {
936             return super.nextEntry().getKey();
937         }
938     }
939     
940     //-----------------------------------------------------------------------
941 /**
942      * Gets the values view of the map.
943      * Changes made to the view affect this map.
944      * To simply iterate through the values, use {@link #mapIterator()}.
945      *
946      * @return the values view
947      */
948     public Collection values() {
949         if (values == null) {
950             values = new Values(this);
951         }
952         return values;
953     }
954
955     /**
956      * Creates a values iterator.
957      * Subclasses can override this to return iterators with different properties.
958      *
959      * @return the values iterator
960      */
961     protected Iterator createValuesIterator() {
962         if (size() == 0) {
963             return EmptyIterator.INSTANCE;
964         }
965         return new ValuesIterator(this);
966     }
967
968     /**
969      * Values implementation.
970      */
971     protected static class Values extends AbstractCollection {
972         /** The parent map */
973         protected final AbstractHashedMap parent;
974         
975         protected Values(AbstractHashedMap parent) {
976             super();
977             this.parent = parent;
978         }
979
980         public int size() {
981             return parent.size();
982         }
983         
984         public void clear() {
985             parent.clear();
986         }
987         
988         public boolean contains(Object value) {
989             return parent.containsValue(value);
990         }
991         
992         public Iterator iterator() {
993             return parent.createValuesIterator();
994         }
995     }
996
997     /**
998      * Values iterator.
999      */
1000    protected static class ValuesIterator extends HashIterator {
1001        
1002        protected ValuesIterator(AbstractHashedMap parent) {
1003            super(parent);
1004        }
1005
1006        public Object next() {
1007            return super.nextEntry().getValue();
1008        }
1009    }
1010    
1011    //-----------------------------------------------------------------------
1012 /**
1013     * HashEntry used to store the data.
1014     * <p>
1015     * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code>
1016     * then you will not be able to access the protected fields.
1017     * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> exist
1018     * to provide the necessary access.
1019     */
1020    protected static class HashEntry implements Map.Entry , KeyValue {
1021        /** The next entry in the hash chain */
1022        protected HashEntry next;
1023        /** The hash code of the key */
1024        protected int hashCode;
1025        /** The key */
1026        protected Object key;
1027        /** The value */
1028        protected Object value;
1029        
1030        protected HashEntry(HashEntry next, int hashCode, Object key, Object value) {
1031            super();
1032            this.next = next;
1033            this.hashCode = hashCode;
1034            this.key = key;
1035            this.value = value;
1036        }
1037        
1038        public Object getKey() {
1039            return (key == NULL ? null : key);
1040        }
1041        
1042        public Object getValue() {
1043            return value;
1044        }
1045        
1046        public Object setValue(Object value) {
1047            Object old = this.value;
1048            this.value = value;
1049            return old;
1050        }
1051        
1052        public boolean equals(Object obj) {
1053            if (obj == this) {
1054                return true;
1055            }
1056            if (obj instanceof Map.Entry == false) {
1057                return false;
1058            }
1059            Map.Entry other = (Map.Entry ) obj;
1060            return
1061                (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
1062                (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
1063        }
1064        
1065        public int hashCode() {
1066            return (getKey() == null ? 0 : getKey().hashCode()) ^
1067                   (getValue() == null ? 0 : getValue().hashCode());
1068        }
1069        
1070        public String toString() {
1071            return new StringBuffer ().append(getKey()).append('=').append(getValue()).toString();
1072        }
1073    }
1074    
1075    /**
1076     * Base Iterator
1077     */
1078    protected static abstract class HashIterator implements Iterator {
1079        
1080        /** The parent map */
1081        protected final AbstractHashedMap parent;
1082        /** The current index into the array of buckets */
1083        protected int hashIndex;
1084        /** The last returned entry */
1085        protected HashEntry last;
1086        /** The next entry */
1087        protected HashEntry next;
1088        /** The modification count expected */
1089        protected int expectedModCount;
1090        
1091        protected HashIterator(AbstractHashedMap parent) {
1092            super();
1093            this.parent = parent;
1094            HashEntry[] data = parent.data;
1095            int i = data.length;
1096            HashEntry next = null;
1097            while (i > 0 && next == null) {
1098                next = data[--i];
1099            }
1100            this.next = next;
1101            this.hashIndex = i;
1102            this.expectedModCount = parent.modCount;
1103        }
1104
1105        public boolean hasNext() {
1106            return (next != null);
1107        }
1108
1109        protected HashEntry nextEntry() {
1110            if (parent.modCount != expectedModCount) {
1111                throw new ConcurrentModificationException ();
1112            }
1113            HashEntry newCurrent = next;
1114            if (newCurrent == null) {
1115                throw new NoSuchElementException (AbstractHashedMap.NO_NEXT_ENTRY);
1116            }
1117            HashEntry[] data = parent.data;
1118            int i = hashIndex;
1119            HashEntry n = newCurrent.next;
1120            while (n == null && i > 0) {
1121                n = data[--i];
1122            }
1123            next = n;
1124            hashIndex = i;
1125            last = newCurrent;
1126            return newCurrent;
1127        }
1128
1129        protected HashEntry currentEntry() {
1130            return last;
1131        }
1132        
1133        public void remove() {
1134            if (last == null) {
1135                throw new IllegalStateException (AbstractHashedMap.REMOVE_INVALID);
1136            }
1137            if (parent.modCount != expectedModCount) {
1138                throw new ConcurrentModificationException ();
1139            }
1140            parent.remove(last.getKey());
1141            last = null;
1142            expectedModCount = parent.modCount;
1143        }
1144
1145        public String toString() {
1146            if (last != null) {
1147                return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
1148            } else {
1149                return "Iterator[]";
1150            }
1151        }
1152    }
1153    
1154    //-----------------------------------------------------------------------
1155 /**
1156     * Writes the map data to the stream. This method must be overridden if a
1157     * subclass must be setup before <code>put()</code> is used.
1158     * <p>
1159     * Serialization is not one of the JDK's nicest topics. Normal serialization will
1160     * initialise the superclass before the subclass. Sometimes however, this isn't
1161     * what you want, as in this case the <code>put()</code> method on read can be
1162     * affected by subclass state.
1163     * <p>
1164     * The solution adopted here is to serialize the state data of this class in
1165     * this protected method. This method must be called by the
1166     * <code>writeObject()</code> of the first serializable subclass.
1167     * <p>
1168     * Subclasses may override if they have a specific field that must be present
1169     * on read before this implementation will work. Generally, the read determines
1170     * what must be serialized here, if anything.
1171     *
1172     * @param out the output stream
1173     */
1174    protected void doWriteObject(ObjectOutputStream out) throws IOException {
1175        out.writeFloat(loadFactor);
1176        out.writeInt(data.length);
1177        out.writeInt(size);
1178        for (MapIterator it = mapIterator(); it.hasNext();) {
1179            out.writeObject(it.next());
1180            out.writeObject(it.getValue());
1181        }
1182    }
1183
1184    /**
1185     * Reads the map data from the stream. This method must be overridden if a
1186     * subclass must be setup before <code>put()</code> is used.
1187     * <p>
1188     * Serialization is not one of the JDK's nicest topics. Normal serialization will
1189     * initialise the superclass before the subclass. Sometimes however, this isn't
1190     * what you want, as in this case the <code>put()</code> method on read can be
1191     * affected by subclass state.
1192     * <p>
1193     * The solution adopted here is to deserialize the state data of this class in
1194     * this protected method. This method must be called by the
1195     * <code>readObject()</code> of the first serializable subclass.
1196     * <p>
1197     * Subclasses may override if the subclass has a specific field that must be present
1198     * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
1199     *
1200     * @param in the input stream
1201     */
1202    protected void doReadObject(ObjectInputStream in) throws IOException , ClassNotFoundException {
1203        loadFactor = in.readFloat();
1204        int capacity = in.readInt();
1205        int size = in.readInt();
1206        init();
1207        data = new HashEntry[capacity];
1208        for (int i = 0; i < size; i++) {
1209            Object key = in.readObject();
1210            Object value = in.readObject();
1211            put(key, value);
1212        }
1213        threshold = calculateThreshold(data.length, loadFactor);
1214    }
1215    
1216    //-----------------------------------------------------------------------
1217 /**
1218     * Clones the map without cloning the keys or values.
1219     * <p>
1220     * To implement <code>clone()</code>, a subclass must implement the
1221     * <code>Cloneable</code> interface and make this method public.
1222     *
1223     * @return a shallow clone
1224     */
1225    protected Object clone() {
1226        try {
1227            AbstractHashedMap cloned = (AbstractHashedMap) super.clone();
1228            cloned.data = new HashEntry[data.length];
1229            cloned.entrySet = null;
1230            cloned.keySet = null;
1231            cloned.values = null;
1232            cloned.modCount = 0;
1233            cloned.size = 0;
1234            cloned.init();
1235            cloned.putAll(this);
1236            return cloned;
1237            
1238        } catch (CloneNotSupportedException ex) {
1239            return null; // should never happen
1240 }
1241    }
1242    
1243    /**
1244     * Compares this map with another.
1245     *
1246     * @param obj the object to compare to
1247     * @return true if equal
1248     */
1249    public boolean equals(Object obj) {
1250        if (obj == this) {
1251            return true;
1252        }
1253        if (obj instanceof Map == false) {
1254            return false;
1255        }
1256        Map map = (Map ) obj;
1257        if (map.size() != size()) {
1258            return false;
1259        }
1260        MapIterator it = mapIterator();
1261        try {
1262            while (it.hasNext()) {
1263                Object key = it.next();
1264                Object value = it.getValue();
1265                if (value == null) {
1266                    if (map.get(key) != null || map.containsKey(key) == false) {
1267                        return false;
1268                    }
1269                } else {
1270                    if (value.equals(map.get(key)) == false) {
1271                        return false;
1272                    }
1273                }
1274            }
1275        } catch (ClassCastException ignored) {
1276            return false;
1277        } catch (NullPointerException ignored) {
1278            return false;
1279        }
1280        return true;
1281    }
1282
1283    /**
1284     * Gets the standard Map hashCode.
1285     *
1286     * @return the hash code defined in the Map interface
1287     */
1288    public int hashCode() {
1289        int total = 0;
1290        Iterator it = createEntrySetIterator();
1291        while (it.hasNext()) {
1292            total += it.next().hashCode();
1293        }
1294        return total;
1295    }
1296
1297    /**
1298     * Gets the map as a String.
1299     *
1300     * @return a string version of the map
1301     */
1302    public String toString() {
1303        if (size() == 0) {
1304            return "{}";
1305        }
1306        StringBuffer buf = new StringBuffer (32 * size());
1307        buf.append('{');
1308
1309        MapIterator it = mapIterator();
1310        boolean hasNext = it.hasNext();
1311        while (hasNext) {
1312            Object key = it.next();
1313            Object value = it.getValue();
1314            buf.append(key == this ? "(this Map)" : key)
1315               .append('=')
1316               .append(value == this ? "(this Map)" : value);
1317
1318            hasNext = it.hasNext();
1319            if (hasNext) {
1320                buf.append(',').append(' ');
1321            }
1322        }
1323
1324        buf.append('}');
1325        return buf.toString();
1326    }
1327}
1328

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags