001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.map;
018
019 import java.io.IOException;
020 import java.io.ObjectInputStream;
021 import java.io.ObjectOutputStream;
022 import java.util.AbstractCollection;
023 import java.util.AbstractMap;
024 import java.util.AbstractSet;
025 import java.util.Collection;
026 import java.util.ConcurrentModificationException;
027 import java.util.Iterator;
028 import java.util.Map;
029 import java.util.NoSuchElementException;
030 import java.util.Set;
031
032 import org.apache.commons.collections.IterableMap;
033 import org.apache.commons.collections.KeyValue;
034 import org.apache.commons.collections.MapIterator;
035 import org.apache.commons.collections.iterators.EmptyIterator;
036 import org.apache.commons.collections.iterators.EmptyMapIterator;
037
038 /**
039 * An abstract implementation of a hash-based map which provides numerous points for
040 * subclasses to override.
041 * <p>
042 * This class implements all the features necessary for a subclass hash-based map.
043 * Key-value entries are stored in instances of the <code>HashEntry</code> class,
044 * which can be overridden and replaced. The iterators can similarly be replaced,
045 * without the need to replace the KeySet, EntrySet and Values view classes.
046 * <p>
047 * Overridable methods are provided to change the default hashing behaviour, and
048 * to change how entries are added to and removed from the map. Hopefully, all you
049 * need for unusual subclasses is here.
050 * <p>
051 * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
052 * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
053 * This extends clause will be removed in v4.0.
054 *
055 * @since Commons Collections 3.0
056 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
057 *
058 * @author java util HashMap
059 * @author Stephen Colebourne
060 * @author Christian Siefkes
061 */
062 public class AbstractHashedMap extends AbstractMap implements IterableMap {
063
064 protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
065 protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
066 protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
067 protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
068 protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
069 protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
070
071 /** The default capacity to use */
072 protected static final int DEFAULT_CAPACITY = 16;
073 /** The default threshold to use */
074 protected static final int DEFAULT_THRESHOLD = 12;
075 /** The default load factor to use */
076 protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
077 /** The maximum capacity allowed */
078 protected static final int MAXIMUM_CAPACITY = 1 << 30;
079 /** An object for masking null */
080 protected static final Object NULL = new Object();
081
082 /** Load factor, normally 0.75 */
083 protected transient float loadFactor;
084 /** The size of the map */
085 protected transient int size;
086 /** Map entries */
087 protected transient HashEntry[] data;
088 /** Size at which to rehash */
089 protected transient int threshold;
090 /** Modification count for iterators */
091 protected transient int modCount;
092 /** Entry set */
093 protected transient EntrySet entrySet;
094 /** Key set */
095 protected transient KeySet keySet;
096 /** Values */
097 protected transient Values values;
098
099 /**
100 * Constructor only used in deserialization, do not use otherwise.
101 */
102 protected AbstractHashedMap() {
103 super();
104 }
105
106 /**
107 * Constructor which performs no validation on the passed in parameters.
108 *
109 * @param initialCapacity the initial capacity, must be a power of two
110 * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f
111 * @param threshold the threshold, must be sensible
112 */
113 protected AbstractHashedMap(int initialCapacity, float loadFactor, int threshold) {
114 super();
115 this.loadFactor = loadFactor;
116 this.data = new HashEntry[initialCapacity];
117 this.threshold = threshold;
118 init();
119 }
120
121 /**
122 * Constructs a new, empty map with the specified initial capacity and
123 * default load factor.
124 *
125 * @param initialCapacity the initial capacity
126 * @throws IllegalArgumentException if the initial capacity is less than one
127 */
128 protected AbstractHashedMap(int initialCapacity) {
129 this(initialCapacity, DEFAULT_LOAD_FACTOR);
130 }
131
132 /**
133 * Constructs a new, empty map with the specified initial capacity and
134 * load factor.
135 *
136 * @param initialCapacity the initial capacity
137 * @param loadFactor the load factor
138 * @throws IllegalArgumentException if the initial capacity is less than one
139 * @throws IllegalArgumentException if the load factor is less than or equal to zero
140 */
141 protected AbstractHashedMap(int initialCapacity, float loadFactor) {
142 super();
143 if (initialCapacity < 1) {
144 throw new IllegalArgumentException("Initial capacity must be greater than 0");
145 }
146 if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
147 throw new IllegalArgumentException("Load factor must be greater than 0");
148 }
149 this.loadFactor = loadFactor;
150 initialCapacity = calculateNewCapacity(initialCapacity);
151 this.threshold = calculateThreshold(initialCapacity, loadFactor);
152 this.data = new HashEntry[initialCapacity];
153 init();
154 }
155
156 /**
157 * Constructor copying elements from another map.
158 *
159 * @param map the map to copy
160 * @throws NullPointerException if the map is null
161 */
162 protected AbstractHashedMap(Map map) {
163 this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
164 putAll(map);
165 }
166
167 /**
168 * Initialise subclasses during construction, cloning or deserialization.
169 */
170 protected void init() {
171 }
172
173 //-----------------------------------------------------------------------
174 /**
175 * Gets the value mapped to the key specified.
176 *
177 * @param key the key
178 * @return the mapped value, null if no match
179 */
180 public Object get(Object key) {
181 key = convertKey(key);
182 int hashCode = hash(key);
183 HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
184 while (entry != null) {
185 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
186 return entry.getValue();
187 }
188 entry = entry.next;
189 }
190 return null;
191 }
192
193 /**
194 * Gets the size of the map.
195 *
196 * @return the size
197 */
198 public int size() {
199 return size;
200 }
201
202 /**
203 * Checks whether the map is currently empty.
204 *
205 * @return true if the map is currently size zero
206 */
207 public boolean isEmpty() {
208 return (size == 0);
209 }
210
211 //-----------------------------------------------------------------------
212 /**
213 * Checks whether the map contains the specified key.
214 *
215 * @param key the key to search for
216 * @return true if the map contains the key
217 */
218 public boolean containsKey(Object key) {
219 key = convertKey(key);
220 int hashCode = hash(key);
221 HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
222 while (entry != null) {
223 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
224 return true;
225 }
226 entry = entry.next;
227 }
228 return false;
229 }
230
231 /**
232 * Checks whether the map contains the specified value.
233 *
234 * @param value the value to search for
235 * @return true if the map contains the value
236 */
237 public boolean containsValue(Object value) {
238 if (value == null) {
239 for (int i = 0, isize = data.length; i < isize; i++) {
240 HashEntry entry = data[i];
241 while (entry != null) {
242 if (entry.getValue() == null) {
243 return true;
244 }
245 entry = entry.next;
246 }
247 }
248 } else {
249 for (int i = 0, isize = data.length; i < isize; i++) {
250 HashEntry entry = data[i];
251 while (entry != null) {
252 if (isEqualValue(value, entry.getValue())) {
253 return true;
254 }
255 entry = entry.next;
256 }
257 }
258 }
259 return false;
260 }
261
262 //-----------------------------------------------------------------------
263 /**
264 * Puts a key-value mapping into this map.
265 *
266 * @param key the key to add
267 * @param value the value to add
268 * @return the value previously mapped to this key, null if none
269 */
270 public Object put(Object key, Object value) {
271 key = convertKey(key);
272 int hashCode = hash(key);
273 int index = hashIndex(hashCode, data.length);
274 HashEntry entry = data[index];
275 while (entry != null) {
276 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
277 Object oldValue = entry.getValue();
278 updateEntry(entry, value);
279 return oldValue;
280 }
281 entry = entry.next;
282 }
283
284 addMapping(index, hashCode, key, value);
285 return null;
286 }
287
288 /**
289 * Puts all the values from the specified map into this map.
290 * <p>
291 * This implementation iterates around the specified map and
292 * uses {@link #put(Object, Object)}.
293 *
294 * @param map the map to add
295 * @throws NullPointerException if the map is null
296 */
297 public void putAll(Map map) {
298 int mapSize = map.size();
299 if (mapSize == 0) {
300 return;
301 }
302 int newSize = (int) ((size + mapSize) / loadFactor + 1);
303 ensureCapacity(calculateNewCapacity(newSize));
304 for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
305 Map.Entry entry = (Map.Entry) it.next();
306 put(entry.getKey(), entry.getValue());
307 }
308 }
309
310 /**
311 * Removes the specified mapping from this map.
312 *
313 * @param key the mapping to remove
314 * @return the value mapped to the removed key, null if key not in map
315 */
316 public Object remove(Object key) {
317 key = convertKey(key);
318 int hashCode = hash(key);
319 int index = hashIndex(hashCode, data.length);
320 HashEntry entry = data[index];
321 HashEntry previous = null;
322 while (entry != null) {
323 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
324 Object oldValue = entry.getValue();
325 removeMapping(entry, index, previous);
326 return oldValue;
327 }
328 previous = entry;
329 entry = entry.next;
330 }
331 return null;
332 }
333
334 /**
335 * Clears the map, resetting the size to zero and nullifying references
336 * to avoid garbage collection issues.
337 */
338 public void clear() {
339 modCount++;
340 HashEntry[] data = this.data;
341 for (int i = data.length - 1; i >= 0; i--) {
342 data[i] = null;
343 }
344 size = 0;
345 }
346
347 //-----------------------------------------------------------------------
348 /**
349 * Converts input keys to another object for storage in the map.
350 * This implementation masks nulls.
351 * Subclasses can override this to perform alternate key conversions.
352 * <p>
353 * The reverse conversion can be changed, if required, by overriding the
354 * getKey() method in the hash entry.
355 *
356 * @param key the key convert
357 * @return the converted key
358 */
359 protected Object convertKey(Object key) {
360 return (key == null ? NULL : key);
361 }
362
363 /**
364 * Gets the hash code for the key specified.
365 * This implementation uses the additional hashing routine from JDK1.4.
366 * Subclasses can override this to return alternate hash codes.
367 *
368 * @param key the key to get a hash code for
369 * @return the hash code
370 */
371 protected int hash(Object key) {
372 // same as JDK 1.4
373 int h = key.hashCode();
374 h += ~(h << 9);
375 h ^= (h >>> 14);
376 h += (h << 4);
377 h ^= (h >>> 10);
378 return h;
379 }
380
381 /**
382 * Compares two keys, in internal converted form, to see if they are equal.
383 * This implementation uses the equals method and assumes neither key is null.
384 * Subclasses can override this to match differently.
385 *
386 * @param key1 the first key to compare passed in from outside
387 * @param key2 the second key extracted from the entry via <code>entry.key</code>
388 * @return true if equal
389 */
390 protected boolean isEqualKey(Object key1, Object key2) {
391 return (key1 == key2 || key1.equals(key2));
392 }
393
394 /**
395 * Compares two values, in external form, to see if they are equal.
396 * This implementation uses the equals method and assumes neither value is null.
397 * Subclasses can override this to match differently.
398 *
399 * @param value1 the first value to compare passed in from outside
400 * @param value2 the second value extracted from the entry via <code>getValue()</code>
401 * @return true if equal
402 */
403 protected boolean isEqualValue(Object value1, Object value2) {
404 return (value1 == value2 || value1.equals(value2));
405 }
406
407 /**
408 * Gets the index into the data storage for the hashCode specified.
409 * This implementation uses the least significant bits of the hashCode.
410 * Subclasses can override this to return alternate bucketing.
411 *
412 * @param hashCode the hash code to use
413 * @param dataSize the size of the data to pick a bucket from
414 * @return the bucket index
415 */
416 protected int hashIndex(int hashCode, int dataSize) {
417 return hashCode & (dataSize - 1);
418 }
419
420 //-----------------------------------------------------------------------
421 /**
422 * Gets the entry mapped to the key specified.
423 * <p>
424 * This method exists for subclasses that may need to perform a multi-step
425 * process accessing the entry. The public methods in this class don't use this
426 * method to gain a small performance boost.
427 *
428 * @param key the key
429 * @return the entry, null if no match
430 */
431 protected HashEntry getEntry(Object key) {
432 key = convertKey(key);
433 int hashCode = hash(key);
434 HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
435 while (entry != null) {
436 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
437 return entry;
438 }
439 entry = entry.next;
440 }
441 return null;
442 }
443
444 //-----------------------------------------------------------------------
445 /**
446 * Updates an existing key-value mapping to change the value.
447 * <p>
448 * This implementation calls <code>setValue()</code> on the entry.
449 * Subclasses could override to handle changes to the map.
450 *
451 * @param entry the entry to update
452 * @param newValue the new value to store
453 */
454 protected void updateEntry(HashEntry entry, Object newValue) {
455 entry.setValue(newValue);
456 }
457
458 /**
459 * Reuses an existing key-value mapping, storing completely new data.
460 * <p>
461 * This implementation sets all the data fields on the entry.
462 * Subclasses could populate additional entry fields.
463 *
464 * @param entry the entry to update, not null
465 * @param hashIndex the index in the data array
466 * @param hashCode the hash code of the key to add
467 * @param key the key to add
468 * @param value the value to add
469 */
470 protected void reuseEntry(HashEntry entry, int hashIndex, int hashCode, Object key, Object value) {
471 entry.next = data[hashIndex];
472 entry.hashCode = hashCode;
473 entry.key = key;
474 entry.value = value;
475 }
476
477 //-----------------------------------------------------------------------
478 /**
479 * Adds a new key-value mapping into this map.
480 * <p>
481 * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
482 * and <code>checkCapacity()</code>.
483 * It also handles changes to <code>modCount</code> and <code>size</code>.
484 * Subclasses could override to fully control adds to the map.
485 *
486 * @param hashIndex the index into the data array to store at
487 * @param hashCode the hash code of the key to add
488 * @param key the key to add
489 * @param value the value to add
490 */
491 protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
492 modCount++;
493 HashEntry entry = createEntry(data[hashIndex], hashCode, key, value);
494 addEntry(entry, hashIndex);
495 size++;
496 checkCapacity();
497 }
498
499 /**
500 * Creates an entry to store the key-value data.
501 * <p>
502 * This implementation creates a new HashEntry instance.
503 * Subclasses can override this to return a different storage class,
504 * or implement caching.
505 *
506 * @param next the next entry in sequence
507 * @param hashCode the hash code to use
508 * @param key the key to store
509 * @param value the value to store
510 * @return the newly created entry
511 */
512 protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
513 return new HashEntry(next, hashCode, key, value);
514 }
515
516 /**
517 * Adds an entry into this map.
518 * <p>
519 * This implementation adds the entry to the data storage table.
520 * Subclasses could override to handle changes to the map.
521 *
522 * @param entry the entry to add
523 * @param hashIndex the index into the data array to store at
524 */
525 protected void addEntry(HashEntry entry, int hashIndex) {
526 data[hashIndex] = entry;
527 }
528
529 //-----------------------------------------------------------------------
530 /**
531 * Removes a mapping from the map.
532 * <p>
533 * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
534 * It also handles changes to <code>modCount</code> and <code>size</code>.
535 * Subclasses could override to fully control removals from the map.
536 *
537 * @param entry the entry to remove
538 * @param hashIndex the index into the data structure
539 * @param previous the previous entry in the chain
540 */
541 protected void removeMapping(HashEntry entry, int hashIndex, HashEntry previous) {
542 modCount++;
543 removeEntry(entry, hashIndex, previous);
544 size--;
545 destroyEntry(entry);
546 }
547
548 /**
549 * Removes an entry from the chain stored in a particular index.
550 * <p>
551 * This implementation removes the entry from the data storage table.
552 * The size is not updated.
553 * Subclasses could override to handle changes to the map.
554 *
555 * @param entry the entry to remove
556 * @param hashIndex the index into the data structure
557 * @param previous the previous entry in the chain
558 */
559 protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
560 if (previous == null) {
561 data[hashIndex] = entry.next;
562 } else {
563 previous.next = entry.next;
564 }
565 }
566
567 /**
568 * Kills an entry ready for the garbage collector.
569 * <p>
570 * This implementation prepares the HashEntry for garbage collection.
571 * Subclasses can override this to implement caching (override clear as well).
572 *
573 * @param entry the entry to destroy
574 */
575 protected void destroyEntry(HashEntry entry) {
576 entry.next = null;
577 entry.key = null;
578 entry.value = null;
579 }
580
581 //-----------------------------------------------------------------------
582 /**
583 * Checks the capacity of the map and enlarges it if necessary.
584 * <p>
585 * This implementation uses the threshold to check if the map needs enlarging
586 */
587 protected void checkCapacity() {
588 if (size >= threshold) {
589 int newCapacity = data.length * 2;
590 if (newCapacity <= MAXIMUM_CAPACITY) {
591 ensureCapacity(newCapacity);
592 }
593 }
594 }
595
596 /**
597 * Changes the size of the data structure to the capacity proposed.
598 *
599 * @param newCapacity the new capacity of the array (a power of two, less or equal to max)
600 */
601 protected void ensureCapacity(int newCapacity) {
602 int oldCapacity = data.length;
603 if (newCapacity <= oldCapacity) {
604 return;
605 }
606 if (size == 0) {
607 threshold = calculateThreshold(newCapacity, loadFactor);
608 data = new HashEntry[newCapacity];
609 } else {
610 HashEntry oldEntries[] = data;
611 HashEntry newEntries[] = new HashEntry[newCapacity];
612
613 modCount++;
614 for (int i = oldCapacity - 1; i >= 0; i--) {
615 HashEntry entry = oldEntries[i];
616 if (entry != null) {
617 oldEntries[i] = null; // gc
618 do {
619 HashEntry next = entry.next;
620 int index = hashIndex(entry.hashCode, newCapacity);
621 entry.next = newEntries[index];
622 newEntries[index] = entry;
623 entry = next;
624 } while (entry != null);
625 }
626 }
627 threshold = calculateThreshold(newCapacity, loadFactor);
628 data = newEntries;
629 }
630 }
631
632 /**
633 * Calculates the new capacity of the map.
634 * This implementation normalizes the capacity to a power of two.
635 *
636 * @param proposedCapacity the proposed capacity
637 * @return the normalized new capacity
638 */
639 protected int calculateNewCapacity(int proposedCapacity) {
640 int newCapacity = 1;
641 if (proposedCapacity > MAXIMUM_CAPACITY) {
642 newCapacity = MAXIMUM_CAPACITY;
643 } else {
644 while (newCapacity < proposedCapacity) {
645 newCapacity <<= 1; // multiply by two
646 }
647 if (newCapacity > MAXIMUM_CAPACITY) {
648 newCapacity = MAXIMUM_CAPACITY;
649 }
650 }
651 return newCapacity;
652 }
653
654 /**
655 * Calculates the new threshold of the map, where it will be resized.
656 * This implementation uses the load factor.
657 *
658 * @param newCapacity the new capacity
659 * @param factor the load factor
660 * @return the new resize threshold
661 */
662 protected int calculateThreshold(int newCapacity, float factor) {
663 return (int) (newCapacity * factor);
664 }
665
666 //-----------------------------------------------------------------------
667 /**
668 * Gets the <code>next</code> field from a <code>HashEntry</code>.
669 * Used in subclasses that have no visibility of the field.
670 *
671 * @param entry the entry to query, must not be null
672 * @return the <code>next</code> field of the entry
673 * @throws NullPointerException if the entry is null
674 * @since Commons Collections 3.1
675 */
676 protected HashEntry entryNext(HashEntry entry) {
677 return entry.next;
678 }
679
680 /**
681 * Gets the <code>hashCode</code> field from a <code>HashEntry</code>.
682 * Used in subclasses that have no visibility of the field.
683 *
684 * @param entry the entry to query, must not be null
685 * @return the <code>hashCode</code> field of the entry
686 * @throws NullPointerException if the entry is null
687 * @since Commons Collections 3.1
688 */
689 protected int entryHashCode(HashEntry entry) {
690 return entry.hashCode;
691 }
692
693 /**
694 * Gets the <code>key</code> field from a <code>HashEntry</code>.
695 * Used in subclasses that have no visibility of the field.
696 *
697 * @param entry the entry to query, must not be null
698 * @return the <code>key</code> field of the entry
699 * @throws NullPointerException if the entry is null
700 * @since Commons Collections 3.1
701 */
702 protected Object entryKey(HashEntry entry) {
703 return entry.key;
704 }
705
706 /**
707 * Gets the <code>value</code> field from a <code>HashEntry</code>.
708 * Used in subclasses that have no visibility of the field.
709 *
710 * @param entry the entry to query, must not be null
711 * @return the <code>value</code> field of the entry
712 * @throws NullPointerException if the entry is null
713 * @since Commons Collections 3.1
714 */
715 protected Object entryValue(HashEntry entry) {
716 return entry.value;
717 }
718
719 //-----------------------------------------------------------------------
720 /**
721 * Gets an iterator over the map.
722 * Changes made to the iterator affect this map.
723 * <p>
724 * A MapIterator returns the keys in the map. It also provides convenient
725 * methods to get the key and value, and set the value.
726 * It avoids the need to create an entrySet/keySet/values object.
727 * It also avoids creating the Map.Entry object.
728 *
729 * @return the map iterator
730 */
731 public MapIterator mapIterator() {
732 if (size == 0) {
733 return EmptyMapIterator.INSTANCE;
734 }
735 return new HashMapIterator(this);
736 }
737
738 /**
739 * MapIterator implementation.
740 */
741 protected static class HashMapIterator extends HashIterator implements MapIterator {
742
743 protected HashMapIterator(AbstractHashedMap parent) {
744 super(parent);
745 }
746
747 public Object next() {
748 return super.nextEntry().getKey();
749 }
750
751 public Object getKey() {
752 HashEntry current = currentEntry();
753 if (current == null) {
754 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
755 }
756 return current.getKey();
757 }
758
759 public Object getValue() {
760 HashEntry current = currentEntry();
761 if (current == null) {
762 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
763 }
764 return current.getValue();
765 }
766
767 public Object setValue(Object value) {
768 HashEntry current = currentEntry();
769 if (current == null) {
770 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
771 }
772 return current.setValue(value);
773 }
774 }
775
776 //-----------------------------------------------------------------------
777 /**
778 * Gets the entrySet view of the map.
779 * Changes made to the view affect this map.
780 * To simply iterate through the entries, use {@link #mapIterator()}.
781 *
782 * @return the entrySet view
783 */
784 public Set entrySet() {
785 if (entrySet == null) {
786 entrySet = new EntrySet(this);
787 }
788 return entrySet;
789 }
790
791 /**
792 * Creates an entry set iterator.
793 * Subclasses can override this to return iterators with different properties.
794 *
795 * @return the entrySet iterator
796 */
797 protected Iterator createEntrySetIterator() {
798 if (size() == 0) {
799 return EmptyIterator.INSTANCE;
800 }
801 return new EntrySetIterator(this);
802 }
803
804 /**
805 * EntrySet implementation.
806 */
807 protected static class EntrySet extends AbstractSet {
808 /** The parent map */
809 protected final AbstractHashedMap parent;
810
811 protected EntrySet(AbstractHashedMap parent) {
812 super();
813 this.parent = parent;
814 }
815
816 public int size() {
817 return parent.size();
818 }
819
820 public void clear() {
821 parent.clear();
822 }
823
824 public boolean contains(Object entry) {
825 if (entry instanceof Map.Entry) {
826 Map.Entry e = (Map.Entry) entry;
827 Entry match = parent.getEntry(e.getKey());
828 return (match != null && match.equals(e));
829 }
830 return false;
831 }
832
833 public boolean remove(Object obj) {
834 if (obj instanceof Map.Entry == false) {
835 return false;
836 }
837 if (contains(obj) == false) {
838 return false;
839 }
840 Map.Entry entry = (Map.Entry) obj;
841 Object key = entry.getKey();
842 parent.remove(key);
843 return true;
844 }
845
846 public Iterator iterator() {
847 return parent.createEntrySetIterator();
848 }
849 }
850
851 /**
852 * EntrySet iterator.
853 */
854 protected static class EntrySetIterator extends HashIterator {
855
856 protected EntrySetIterator(AbstractHashedMap parent) {
857 super(parent);
858 }
859
860 public Object next() {
861 return super.nextEntry();
862 }
863 }
864
865 //-----------------------------------------------------------------------
866 /**
867 * Gets the keySet view of the map.
868 * Changes made to the view affect this map.
869 * To simply iterate through the keys, use {@link #mapIterator()}.
870 *
871 * @return the keySet view
872 */
873 public Set keySet() {
874 if (keySet == null) {
875 keySet = new KeySet(this);
876 }
877 return keySet;
878 }
879
880 /**
881 * Creates a key set iterator.
882 * Subclasses can override this to return iterators with different properties.
883 *
884 * @return the keySet iterator
885 */
886 protected Iterator createKeySetIterator() {
887 if (size() == 0) {
888 return EmptyIterator.INSTANCE;
889 }
890 return new KeySetIterator(this);
891 }
892
893 /**
894 * KeySet implementation.
895 */
896 protected static class KeySet extends AbstractSet {
897 /** The parent map */
898 protected final AbstractHashedMap parent;
899
900 protected KeySet(AbstractHashedMap parent) {
901 super();
902 this.parent = parent;
903 }
904
905 public int size() {
906 return parent.size();
907 }
908
909 public void clear() {
910 parent.clear();
911 }
912
913 public boolean contains(Object key) {
914 return parent.containsKey(key);
915 }
916
917 public boolean remove(Object key) {
918 boolean result = parent.containsKey(key);
919 parent.remove(key);
920 return result;
921 }
922
923 public Iterator iterator() {
924 return parent.createKeySetIterator();
925 }
926 }
927
928 /**
929 * KeySet iterator.
930 */
931 protected static class KeySetIterator extends EntrySetIterator {
932
933 protected KeySetIterator(AbstractHashedMap parent) {
934 super(parent);
935 }
936
937 public Object next() {
938 return super.nextEntry().getKey();
939 }
940 }
941
942 //-----------------------------------------------------------------------
943 /**
944 * Gets the values view of the map.
945 * Changes made to the view affect this map.
946 * To simply iterate through the values, use {@link #mapIterator()}.
947 *
948 * @return the values view
949 */
950 public Collection values() {
951 if (values == null) {
952 values = new Values(this);
953 }
954 return values;
955 }
956
957 /**
958 * Creates a values iterator.
959 * Subclasses can override this to return iterators with different properties.
960 *
961 * @return the values iterator
962 */
963 protected Iterator createValuesIterator() {
964 if (size() == 0) {
965 return EmptyIterator.INSTANCE;
966 }
967 return new ValuesIterator(this);
968 }
969
970 /**
971 * Values implementation.
972 */
973 protected static class Values extends AbstractCollection {
974 /** The parent map */
975 protected final AbstractHashedMap parent;
976
977 protected Values(AbstractHashedMap parent) {
978 super();
979 this.parent = parent;
980 }
981
982 public int size() {
983 return parent.size();
984 }
985
986 public void clear() {
987 parent.clear();
988 }
989
990 public boolean contains(Object value) {
991 return parent.containsValue(value);
992 }
993
994 public Iterator iterator() {
995 return parent.createValuesIterator();
996 }
997 }
998
999 /**
1000 * Values iterator.
1001 */
1002 protected static class ValuesIterator extends HashIterator {
1003
1004 protected ValuesIterator(AbstractHashedMap parent) {
1005 super(parent);
1006 }
1007
1008 public Object next() {
1009 return super.nextEntry().getValue();
1010 }
1011 }
1012
1013 //-----------------------------------------------------------------------
1014 /**
1015 * HashEntry used to store the data.
1016 * <p>
1017 * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code>
1018 * then you will not be able to access the protected fields.
1019 * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> exist
1020 * to provide the necessary access.
1021 */
1022 protected static class HashEntry implements Map.Entry, KeyValue {
1023 /** The next entry in the hash chain */
1024 protected HashEntry next;
1025 /** The hash code of the key */
1026 protected int hashCode;
1027 /** The key */
1028 protected Object key;
1029 /** The value */
1030 protected Object value;
1031
1032 protected HashEntry(HashEntry next, int hashCode, Object key, Object value) {
1033 super();
1034 this.next = next;
1035 this.hashCode = hashCode;
1036 this.key = key;
1037 this.value = value;
1038 }
1039
1040 public Object getKey() {
1041 return (key == NULL ? null : key);
1042 }
1043
1044 public Object getValue() {
1045 return value;
1046 }
1047
1048 public Object setValue(Object value) {
1049 Object old = this.value;
1050 this.value = value;
1051 return old;
1052 }
1053
1054 public boolean equals(Object obj) {
1055 if (obj == this) {
1056 return true;
1057 }
1058 if (obj instanceof Map.Entry == false) {
1059 return false;
1060 }
1061 Map.Entry other = (Map.Entry) obj;
1062 return
1063 (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
1064 (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
1065 }
1066
1067 public int hashCode() {
1068 return (getKey() == null ? 0 : getKey().hashCode()) ^
1069 (getValue() == null ? 0 : getValue().hashCode());
1070 }
1071
1072 public String toString() {
1073 return new StringBuffer().append(getKey()).append('=').append(getValue()).toString();
1074 }
1075 }
1076
1077 /**
1078 * Base Iterator
1079 */
1080 protected static abstract class HashIterator implements Iterator {
1081
1082 /** The parent map */
1083 protected final AbstractHashedMap parent;
1084 /** The current index into the array of buckets */
1085 protected int hashIndex;
1086 /** The last returned entry */
1087 protected HashEntry last;
1088 /** The next entry */
1089 protected HashEntry next;
1090 /** The modification count expected */
1091 protected int expectedModCount;
1092
1093 protected HashIterator(AbstractHashedMap parent) {
1094 super();
1095 this.parent = parent;
1096 HashEntry[] data = parent.data;
1097 int i = data.length;
1098 HashEntry next = null;
1099 while (i > 0 && next == null) {
1100 next = data[--i];
1101 }
1102 this.next = next;
1103 this.hashIndex = i;
1104 this.expectedModCount = parent.modCount;
1105 }
1106
1107 public boolean hasNext() {
1108 return (next != null);
1109 }
1110
1111 protected HashEntry nextEntry() {
1112 if (parent.modCount != expectedModCount) {
1113 throw new ConcurrentModificationException();
1114 }
1115 HashEntry newCurrent = next;
1116 if (newCurrent == null) {
1117 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
1118 }
1119 HashEntry[] data = parent.data;
1120 int i = hashIndex;
1121 HashEntry n = newCurrent.next;
1122 while (n == null && i > 0) {
1123 n = data[--i];
1124 }
1125 next = n;
1126 hashIndex = i;
1127 last = newCurrent;
1128 return newCurrent;
1129 }
1130
1131 protected HashEntry currentEntry() {
1132 return last;
1133 }
1134
1135 public void remove() {
1136 if (last == null) {
1137 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
1138 }
1139 if (parent.modCount != expectedModCount) {
1140 throw new ConcurrentModificationException();
1141 }
1142 parent.remove(last.getKey());
1143 last = null;
1144 expectedModCount = parent.modCount;
1145 }
1146
1147 public String toString() {
1148 if (last != null) {
1149 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
1150 } else {
1151 return "Iterator[]";
1152 }
1153 }
1154 }
1155
1156 //-----------------------------------------------------------------------
1157 /**
1158 * Writes the map data to the stream. This method must be overridden if a
1159 * subclass must be setup before <code>put()</code> is used.
1160 * <p>
1161 * Serialization is not one of the JDK's nicest topics. Normal serialization will
1162 * initialise the superclass before the subclass. Sometimes however, this isn't
1163 * what you want, as in this case the <code>put()</code> method on read can be
1164 * affected by subclass state.
1165 * <p>
1166 * The solution adopted here is to serialize the state data of this class in
1167 * this protected method. This method must be called by the
1168 * <code>writeObject()</code> of the first serializable subclass.
1169 * <p>
1170 * Subclasses may override if they have a specific field that must be present
1171 * on read before this implementation will work. Generally, the read determines
1172 * what must be serialized here, if anything.
1173 *
1174 * @param out the output stream
1175 */
1176 protected void doWriteObject(ObjectOutputStream out) throws IOException {
1177 out.writeFloat(loadFactor);
1178 out.writeInt(data.length);
1179 out.writeInt(size);
1180 for (MapIterator it = mapIterator(); it.hasNext();) {
1181 out.writeObject(it.next());
1182 out.writeObject(it.getValue());
1183 }
1184 }
1185
1186 /**
1187 * Reads the map data from the stream. This method must be overridden if a
1188 * subclass must be setup before <code>put()</code> is used.
1189 * <p>
1190 * Serialization is not one of the JDK's nicest topics. Normal serialization will
1191 * initialise the superclass before the subclass. Sometimes however, this isn't
1192 * what you want, as in this case the <code>put()</code> method on read can be
1193 * affected by subclass state.
1194 * <p>
1195 * The solution adopted here is to deserialize the state data of this class in
1196 * this protected method. This method must be called by the
1197 * <code>readObject()</code> of the first serializable subclass.
1198 * <p>
1199 * Subclasses may override if the subclass has a specific field that must be present
1200 * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
1201 *
1202 * @param in the input stream
1203 */
1204 protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
1205 loadFactor = in.readFloat();
1206 int capacity = in.readInt();
1207 int size = in.readInt();
1208 init();
1209 threshold = calculateThreshold(capacity, loadFactor);
1210 data = new HashEntry[capacity];
1211 for (int i = 0; i < size; i++) {
1212 Object key = in.readObject();
1213 Object value = in.readObject();
1214 put(key, value);
1215 }
1216 }
1217
1218 //-----------------------------------------------------------------------
1219 /**
1220 * Clones the map without cloning the keys or values.
1221 * <p>
1222 * To implement <code>clone()</code>, a subclass must implement the
1223 * <code>Cloneable</code> interface and make this method public.
1224 *
1225 * @return a shallow clone
1226 */
1227 protected Object clone() {
1228 try {
1229 AbstractHashedMap cloned = (AbstractHashedMap) super.clone();
1230 cloned.data = new HashEntry[data.length];
1231 cloned.entrySet = null;
1232 cloned.keySet = null;
1233 cloned.values = null;
1234 cloned.modCount = 0;
1235 cloned.size = 0;
1236 cloned.init();
1237 cloned.putAll(this);
1238 return cloned;
1239
1240 } catch (CloneNotSupportedException ex) {
1241 return null; // should never happen
1242 }
1243 }
1244
1245 /**
1246 * Compares this map with another.
1247 *
1248 * @param obj the object to compare to
1249 * @return true if equal
1250 */
1251 public boolean equals(Object obj) {
1252 if (obj == this) {
1253 return true;
1254 }
1255 if (obj instanceof Map == false) {
1256 return false;
1257 }
1258 Map map = (Map) obj;
1259 if (map.size() != size()) {
1260 return false;
1261 }
1262 MapIterator it = mapIterator();
1263 try {
1264 while (it.hasNext()) {
1265 Object key = it.next();
1266 Object value = it.getValue();
1267 if (value == null) {
1268 if (map.get(key) != null || map.containsKey(key) == false) {
1269 return false;
1270 }
1271 } else {
1272 if (value.equals(map.get(key)) == false) {
1273 return false;
1274 }
1275 }
1276 }
1277 } catch (ClassCastException ignored) {
1278 return false;
1279 } catch (NullPointerException ignored) {
1280 return false;
1281 }
1282 return true;
1283 }
1284
1285 /**
1286 * Gets the standard Map hashCode.
1287 *
1288 * @return the hash code defined in the Map interface
1289 */
1290 public int hashCode() {
1291 int total = 0;
1292 Iterator it = createEntrySetIterator();
1293 while (it.hasNext()) {
1294 total += it.next().hashCode();
1295 }
1296 return total;
1297 }
1298
1299 /**
1300 * Gets the map as a String.
1301 *
1302 * @return a string version of the map
1303 */
1304 public String toString() {
1305 if (size() == 0) {
1306 return "{}";
1307 }
1308 StringBuffer buf = new StringBuffer(32 * size());
1309 buf.append('{');
1310
1311 MapIterator it = mapIterator();
1312 boolean hasNext = it.hasNext();
1313 while (hasNext) {
1314 Object key = it.next();
1315 Object value = it.getValue();
1316 buf.append(key == this ? "(this Map)" : key)
1317 .append('=')
1318 .append(value == this ? "(this Map)" : value);
1319
1320 hasNext = it.hasNext();
1321 if (hasNext) {
1322 buf.append(',').append(' ');
1323 }
1324 }
1325
1326 buf.append('}');
1327 return buf.toString();
1328 }
1329 }