src/share/classes/java/util/LinkedHashMap.java

Print this page
rev 5431 : 7126277: Alternative hashing implementation


 219      *
 220      * @param  initialCapacity the initial capacity
 221      * @param  loadFactor      the load factor
 222      * @param  accessOrder     the ordering mode - <tt>true</tt> for
 223      *         access-order, <tt>false</tt> for insertion-order
 224      * @throws IllegalArgumentException if the initial capacity is negative
 225      *         or the load factor is nonpositive
 226      */
 227     public LinkedHashMap(int initialCapacity,
 228                          float loadFactor,
 229                          boolean accessOrder) {
 230         super(initialCapacity, loadFactor);
 231         this.accessOrder = accessOrder;
 232     }
 233 
 234     /**
 235      * Called by superclass constructors and pseudoconstructors (clone,
 236      * readObject) before any entries are inserted into the map.  Initializes
 237      * the chain.
 238      */

 239     void init() {
 240         header = new Entry<>(-1, null, null, null);
 241         header.before = header.after = header;
 242     }
 243 
 244     /**
 245      * Transfers all entries to new table array.  This method is called
 246      * by superclass resize.  It is overridden for performance, as it is
 247      * faster to iterate using our linked list.
 248      */

 249     @SuppressWarnings("unchecked")
 250     void transfer(HashMap.Entry[] newTable) {
 251         int newCapacity = newTable.length;
 252         for (Entry<K,V> e = header.after; e != header; e = e.after) {
 253             int index = indexFor(e.hash, newCapacity);
 254             e.next = (HashMap.Entry<K,V>)newTable[index];
 255             newTable[index] = e;
 256         }
 257     }
 258 
 259 
 260     /**
 261      * Returns <tt>true</tt> if this map maps one or more keys to the
 262      * specified value.
 263      *
 264      * @param value value whose presence in this map is to be tested
 265      * @return <tt>true</tt> if this map maps one or more keys to the
 266      *         specified value
 267      */
 268     public boolean containsValue(Object value) {


 404 
 405     private class ValueIterator extends LinkedHashIterator<V> {
 406         public V next() { return nextEntry().value; }
 407     }
 408 
 409     private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
 410         public Map.Entry<K,V> next() { return nextEntry(); }
 411     }
 412 
 413     // These Overrides alter the behavior of superclass view iterator() methods
 414     Iterator<K> newKeyIterator()   { return new KeyIterator();   }
 415     Iterator<V> newValueIterator() { return new ValueIterator(); }
 416     Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
 417 
 418     /**
 419      * This override alters behavior of superclass put method. It causes newly
 420      * allocated entry to get inserted at the end of the linked list and
 421      * removes the eldest entry if appropriate.
 422      */
 423     void addEntry(int hash, K key, V value, int bucketIndex) {
 424         createEntry(hash, key, value, bucketIndex);
 425 
 426         // Remove eldest entry if instructed, else grow capacity if appropriate
 427         Entry<K,V> eldest = header.after;
 428         if (removeEldestEntry(eldest)) {
 429             removeEntryForKey(eldest.key);
 430         } else {
 431             if (size >= threshold)
 432                 resize(2 * table.length);
 433         }
 434     }
 435 
 436     /**
 437      * This override differs from addEntry in that it doesn't resize the
 438      * table or remove the eldest entry.
 439      */
 440     void createEntry(int hash, K key, V value, int bucketIndex) {
 441         @SuppressWarnings("unchecked")
 442             HashMap.Entry<K,V> old = (HashMap.Entry<K,V>)table[bucketIndex];
 443         Entry<K,V> e = new Entry<>(hash, key, value, old);
 444         table[bucketIndex] = e;
 445         e.addBefore(header);
 446         size++;
 447     }
 448 
 449     /**
 450      * Returns <tt>true</tt> if this map should remove its eldest entry.
 451      * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
 452      * inserting a new entry into the map.  It provides the implementor




 219      *
 220      * @param  initialCapacity the initial capacity
 221      * @param  loadFactor      the load factor
 222      * @param  accessOrder     the ordering mode - <tt>true</tt> for
 223      *         access-order, <tt>false</tt> for insertion-order
 224      * @throws IllegalArgumentException if the initial capacity is negative
 225      *         or the load factor is nonpositive
 226      */
 227     public LinkedHashMap(int initialCapacity,
 228                          float loadFactor,
 229                          boolean accessOrder) {
 230         super(initialCapacity, loadFactor);
 231         this.accessOrder = accessOrder;
 232     }
 233 
 234     /**
 235      * Called by superclass constructors and pseudoconstructors (clone,
 236      * readObject) before any entries are inserted into the map.  Initializes
 237      * the chain.
 238      */
 239     @Override
 240     void init() {
 241         header = new Entry<>(-1, null, null, null);
 242         header.before = header.after = header;
 243     }
 244 
 245     /**
 246      * Transfers all entries to new table array.  This method is called
 247      * by superclass resize.  It is overridden for performance, as it is
 248      * faster to iterate using our linked list.
 249      */
 250     @Override
 251     @SuppressWarnings("unchecked")
 252     void transfer(HashMap.Entry[] newTable) {
 253         int newCapacity = newTable.length;
 254         for (Entry<K,V> e = header.after; e != header; e = e.after) {
 255             int index = indexFor(e.hash, newCapacity);
 256             e.next = (HashMap.Entry<K,V>)newTable[index];
 257             newTable[index] = e;
 258         }
 259     }
 260 
 261 
 262     /**
 263      * Returns <tt>true</tt> if this map maps one or more keys to the
 264      * specified value.
 265      *
 266      * @param value value whose presence in this map is to be tested
 267      * @return <tt>true</tt> if this map maps one or more keys to the
 268      *         specified value
 269      */
 270     public boolean containsValue(Object value) {


 406 
 407     private class ValueIterator extends LinkedHashIterator<V> {
 408         public V next() { return nextEntry().value; }
 409     }
 410 
 411     private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
 412         public Map.Entry<K,V> next() { return nextEntry(); }
 413     }
 414 
 415     // These Overrides alter the behavior of superclass view iterator() methods
 416     Iterator<K> newKeyIterator()   { return new KeyIterator();   }
 417     Iterator<V> newValueIterator() { return new ValueIterator(); }
 418     Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
 419 
 420     /**
 421      * This override alters behavior of superclass put method. It causes newly
 422      * allocated entry to get inserted at the end of the linked list and
 423      * removes the eldest entry if appropriate.
 424      */
 425     void addEntry(int hash, K key, V value, int bucketIndex) {
 426         super.addEntry(hash, key, value, bucketIndex);
 427         
 428         // Remove eldest entry if instructed
 429         Entry<K,V> eldest = header.after;
 430         if (removeEldestEntry(eldest)) {
 431             removeEntryForKey(eldest.key);



 432         }
 433     }
 434 
 435     /**
 436      * This override differs from addEntry in that it doesn't resize the
 437      * table or remove the eldest entry.
 438      */
 439     void createEntry(int hash, K key, V value, int bucketIndex) {
 440         @SuppressWarnings("unchecked")
 441             HashMap.Entry<K,V> old = (HashMap.Entry<K,V>)table[bucketIndex];
 442         Entry<K,V> e = new Entry<>(hash, key, value, old);
 443         table[bucketIndex] = e;
 444         e.addBefore(header);
 445         size++;
 446     }
 447 
 448     /**
 449      * Returns <tt>true</tt> if this map should remove its eldest entry.
 450      * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
 451      * inserting a new entry into the map.  It provides the implementor