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 }