Source for java.util.LinkedHashMap

   1: /* LinkedHashMap.java -- a class providing hashtable data structure,
   2:    mapping Object --> Object, with linked list traversal
   3:    Copyright (C) 2001, 2002, 2005 Free Software Foundation, Inc.
   4: 
   5: This file is part of GNU Classpath.
   6: 
   7: GNU Classpath is free software; you can redistribute it and/or modify
   8: it under the terms of the GNU General Public License as published by
   9: the Free Software Foundation; either version 2, or (at your option)
  10: any later version.
  11: 
  12: GNU Classpath is distributed in the hope that it will be useful, but
  13: WITHOUT ANY WARRANTY; without even the implied warranty of
  14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15: General Public License for more details.
  16: 
  17: You should have received a copy of the GNU General Public License
  18: along with GNU Classpath; see the file COPYING.  If not, write to the
  19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20: 02110-1301 USA.
  21: 
  22: Linking this library statically or dynamically with other modules is
  23: making a combined work based on this library.  Thus, the terms and
  24: conditions of the GNU General Public License cover the whole
  25: combination.
  26: 
  27: As a special exception, the copyright holders of this library give you
  28: permission to link this library with independent modules to produce an
  29: executable, regardless of the license terms of these independent
  30: modules, and to copy and distribute the resulting executable under
  31: terms of your choice, provided that you also meet, for each linked
  32: independent module, the terms and conditions of the license of that
  33: module.  An independent module is a module which is not derived from
  34: or based on this library.  If you modify this library, you may extend
  35: this exception to your version of the library, but you are not
  36: obligated to do so.  If you do not wish to do so, delete this
  37: exception statement from your version. */
  38: 
  39: 
  40: package java.util;
  41: 
  42: /**
  43:  * This class provides a hashtable-backed implementation of the
  44:  * Map interface, with predictable traversal order.
  45:  * <p>
  46:  *
  47:  * It uses a hash-bucket approach; that is, hash collisions are handled
  48:  * by linking the new node off of the pre-existing node (or list of
  49:  * nodes).  In this manner, techniques such as linear probing (which
  50:  * can cause primary clustering) and rehashing (which does not fit very
  51:  * well with Java's method of precomputing hash codes) are avoided.  In
  52:  * addition, this maintains a doubly-linked list which tracks either
  53:  * insertion or access order.
  54:  * <p>
  55:  *
  56:  * In insertion order, calling <code>put</code> adds the key to the end of
  57:  * traversal, unless the key was already in the map; changing traversal order
  58:  * requires removing and reinserting a key.  On the other hand, in access
  59:  * order, all calls to <code>put</code> and <code>get</code> cause the
  60:  * accessed key to move to the end of the traversal list.  Note that any
  61:  * accesses to the map's contents via its collection views and iterators do
  62:  * not affect the map's traversal order, since the collection views do not
  63:  * call <code>put</code> or <code>get</code>.
  64:  * <p>
  65:  *
  66:  * One of the nice features of tracking insertion order is that you can
  67:  * copy a hashtable, and regardless of the implementation of the original,
  68:  * produce the same results when iterating over the copy.  This is possible
  69:  * without needing the overhead of <code>TreeMap</code>.
  70:  * <p>
  71:  *
  72:  * When using this {@link #LinkedHashMap(int, float, boolean) constructor},
  73:  * you can build an access-order mapping.  This can be used to implement LRU
  74:  * caches, for example.  By overriding {@link #removeEldestEntry(Map.Entry)},
  75:  * you can also control the removal of the oldest entry, and thereby do
  76:  * things like keep the map at a fixed size.
  77:  * <p>
  78:  *
  79:  * Under ideal circumstances (no collisions), LinkedHashMap offers O(1) 
  80:  * performance on most operations (<code>containsValue()</code> is,
  81:  * of course, O(n)).  In the worst case (all keys map to the same 
  82:  * hash code -- very unlikely), most operations are O(n).  Traversal is
  83:  * faster than in HashMap (proportional to the map size, and not the space
  84:  * allocated for the map), but other operations may be slower because of the
  85:  * overhead of the maintaining the traversal order list.
  86:  * <p>
  87:  *
  88:  * LinkedHashMap accepts the null key and null values.  It is not
  89:  * synchronized, so if you need multi-threaded access, consider using:<br>
  90:  * <code>Map m = Collections.synchronizedMap(new LinkedHashMap(...));</code>
  91:  * <p>
  92:  *
  93:  * The iterators are <i>fail-fast</i>, meaning that any structural
  94:  * modification, except for <code>remove()</code> called on the iterator
  95:  * itself, cause the iterator to throw a
  96:  * {@link ConcurrentModificationException} rather than exhibit
  97:  * non-deterministic behavior.
  98:  *
  99:  * @author Eric Blake (ebb9@email.byu.edu)
 100:  * @see Object#hashCode()
 101:  * @see Collection
 102:  * @see Map
 103:  * @see HashMap
 104:  * @see TreeMap
 105:  * @see Hashtable
 106:  * @since 1.4
 107:  * @status updated to 1.4
 108:  */
 109: public class LinkedHashMap extends HashMap
 110: {
 111:   /**
 112:    * Compatible with JDK 1.4.
 113:    */
 114:   private static final long serialVersionUID = 3801124242820219131L;
 115: 
 116:   /**
 117:    * The oldest Entry to begin iteration at.
 118:    */
 119:   transient LinkedHashEntry root;
 120: 
 121:   /**
 122:    * The iteration order of this linked hash map: <code>true</code> for
 123:    * access-order, <code>false</code> for insertion-order.
 124:    *
 125:    * @serial true for access order traversal
 126:    */
 127:   final boolean accessOrder;
 128: 
 129:   /**
 130:    * Class to represent an entry in the hash table. Holds a single key-value
 131:    * pair and the doubly-linked insertion order list.
 132:    */
 133:   class LinkedHashEntry extends HashEntry
 134:   {
 135:     /**
 136:      * The predecessor in the iteration list. If this entry is the root
 137:      * (eldest), pred points to the newest entry.
 138:      */
 139:     LinkedHashEntry pred;
 140: 
 141:     /** The successor in the iteration list, null if this is the newest. */
 142:     LinkedHashEntry succ;
 143: 
 144:     /**
 145:      * Simple constructor.
 146:      *
 147:      * @param key the key
 148:      * @param value the value
 149:      */
 150:     LinkedHashEntry(Object key, Object value)
 151:     {
 152:       super(key, value);
 153:       if (root == null)
 154:         {
 155:           root = this;
 156:           pred = this;
 157:         }
 158:       else
 159:         {
 160:           pred = root.pred;
 161:           pred.succ = this;
 162:           root.pred = this;
 163:         }
 164:     }
 165: 
 166:     /**
 167:      * Called when this entry is accessed via put or get. This version does
 168:      * the necessary bookkeeping to keep the doubly-linked list in order,
 169:      * after moving this element to the newest position in access order.
 170:      */
 171:     void access()
 172:     {
 173:       if (accessOrder && succ != null)
 174:         {
 175:           modCount++;
 176:           if (this == root)
 177:             {
 178:               root = succ;
 179:               pred.succ = this;
 180:               succ = null;
 181:             }
 182:           else
 183:             {
 184:               pred.succ = succ;
 185:               succ.pred = pred;
 186:               succ = null;
 187:               pred = root.pred;
 188:               pred.succ = this;
 189:               root.pred = this;
 190:             }
 191:         }
 192:     }
 193: 
 194:     /**
 195:      * Called when this entry is removed from the map. This version does
 196:      * the necessary bookkeeping to keep the doubly-linked list in order.
 197:      *
 198:      * @return the value of this key as it is removed
 199:      */
 200:     Object cleanup()
 201:     {
 202:       if (this == root)
 203:         {
 204:           root = succ;
 205:           if (succ != null)
 206:             succ.pred = pred;
 207:         }
 208:       else if (succ == null)
 209:         {
 210:           pred.succ = null;
 211:           root.pred = pred;
 212:         }
 213:       else
 214:         {
 215:           pred.succ = succ;
 216:           succ.pred = pred;
 217:         }
 218:       return value;
 219:     }
 220:   } // class LinkedHashEntry
 221: 
 222:   /**
 223:    * Construct a new insertion-ordered LinkedHashMap with the default
 224:    * capacity (11) and the default load factor (0.75).
 225:    */
 226:   public LinkedHashMap()
 227:   {
 228:     super();
 229:     accessOrder = false;
 230:   }
 231: 
 232:   /**
 233:    * Construct a new insertion-ordered LinkedHashMap from the given Map,
 234:    * with initial capacity the greater of the size of <code>m</code> or
 235:    * the default of 11.
 236:    * <p>
 237:    *
 238:    * Every element in Map m will be put into this new HashMap, in the
 239:    * order of m's iterator.
 240:    *
 241:    * @param m a Map whose key / value pairs will be put into
 242:    *          the new HashMap.  <b>NOTE: key / value pairs
 243:    *          are not cloned in this constructor.</b>
 244:    * @throws NullPointerException if m is null
 245:    */
 246:   public LinkedHashMap(Map m)
 247:   {
 248:     super(m);
 249:     accessOrder = false;
 250:   }
 251: 
 252:   /**
 253:    * Construct a new insertion-ordered LinkedHashMap with a specific
 254:    * inital capacity and default load factor of 0.75.
 255:    *
 256:    * @param initialCapacity the initial capacity of this HashMap (&gt;= 0)
 257:    * @throws IllegalArgumentException if (initialCapacity &lt; 0)
 258:    */
 259:   public LinkedHashMap(int initialCapacity)
 260:   {
 261:     super(initialCapacity);
 262:     accessOrder = false;
 263:   }
 264: 
 265:   /**
 266:    * Construct a new insertion-orderd LinkedHashMap with a specific
 267:    * inital capacity and load factor.
 268:    *
 269:    * @param initialCapacity the initial capacity (&gt;= 0)
 270:    * @param loadFactor the load factor (&gt; 0, not NaN)
 271:    * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
 272:    *                                     ! (loadFactor &gt; 0.0)
 273:    */
 274:   public LinkedHashMap(int initialCapacity, float loadFactor)
 275:   {
 276:     super(initialCapacity, loadFactor);
 277:     accessOrder = false;
 278:   }
 279: 
 280:   /**
 281:    * Construct a new LinkedHashMap with a specific inital capacity, load
 282:    * factor, and ordering mode.
 283:    *
 284:    * @param initialCapacity the initial capacity (&gt;=0)
 285:    * @param loadFactor the load factor (&gt;0, not NaN)
 286:    * @param accessOrder true for access-order, false for insertion-order
 287:    * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
 288:    *                                     ! (loadFactor &gt; 0.0)
 289:    */
 290:   public LinkedHashMap(int initialCapacity, float loadFactor,
 291:                        boolean accessOrder)
 292:   {
 293:     super(initialCapacity, loadFactor);
 294:     this.accessOrder = accessOrder;
 295:   }
 296: 
 297:   /**
 298:    * Clears the Map so it has no keys. This is O(1).
 299:    */
 300:   public void clear()
 301:   {
 302:     super.clear();
 303:     root = null;
 304:   }
 305: 
 306:   /**
 307:    * Returns <code>true</code> if this HashMap contains a value
 308:    * <code>o</code>, such that <code>o.equals(value)</code>.
 309:    *
 310:    * @param value the value to search for in this HashMap
 311:    * @return <code>true</code> if at least one key maps to the value
 312:    */
 313:   public boolean containsValue(Object value)
 314:   {
 315:     LinkedHashEntry e = root;
 316:     while (e != null)
 317:       {
 318:         if (equals(value, e.value))
 319:           return true;
 320:         e = e.succ;
 321:       }
 322:     return false;
 323:   }
 324: 
 325:   /**
 326:    * Return the value in this Map associated with the supplied key,
 327:    * or <code>null</code> if the key maps to nothing.  If this is an
 328:    * access-ordered Map and the key is found, this performs structural
 329:    * modification, moving the key to the newest end of the list. NOTE:
 330:    * Since the value could also be null, you must use containsKey to
 331:    * see if this key actually maps to something.
 332:    *
 333:    * @param key the key for which to fetch an associated value
 334:    * @return what the key maps to, if present
 335:    * @see #put(Object, Object)
 336:    * @see #containsKey(Object)
 337:    */
 338:   public Object get(Object key)
 339:   {
 340:     int idx = hash(key);
 341:     HashEntry e = buckets[idx];
 342:     while (e != null)
 343:       {
 344:         if (equals(key, e.key))
 345:           {
 346:             e.access();
 347:             return e.value;
 348:           }
 349:         e = e.next;
 350:       }
 351:     return null;
 352:   }
 353: 
 354:   /**
 355:    * Returns <code>true</code> if this map should remove the eldest entry.
 356:    * This method is invoked by all calls to <code>put</code> and
 357:    * <code>putAll</code> which place a new entry in the map, providing
 358:    * the implementer an opportunity to remove the eldest entry any time
 359:    * a new one is added.  This can be used to save memory usage of the
 360:    * hashtable, as well as emulating a cache, by deleting stale entries.
 361:    * <p>
 362:    *
 363:    * For example, to keep the Map limited to 100 entries, override as follows:
 364:    * <pre>
 365:    * private static final int MAX_ENTRIES = 100;
 366:    * protected boolean removeEldestEntry(Map.Entry eldest)
 367:    * {
 368:    *   return size() &gt; MAX_ENTRIES;
 369:    * }
 370:    * </pre><p>
 371:    *
 372:    * Typically, this method does not modify the map, but just uses the
 373:    * return value as an indication to <code>put</code> whether to proceed.
 374:    * However, if you override it to modify the map, you must return false
 375:    * (indicating that <code>put</code> should leave the modified map alone),
 376:    * or you face unspecified behavior.  Remember that in access-order mode,
 377:    * even calling <code>get</code> is a structural modification, but using
 378:    * the collections views (such as <code>keySet</code>) is not.
 379:    * <p>
 380:    *
 381:    * This method is called after the eldest entry has been inserted, so
 382:    * if <code>put</code> was called on a previously empty map, the eldest
 383:    * entry is the one you just put in! The default implementation just
 384:    * returns <code>false</code>, so that this map always behaves like
 385:    * a normal one with unbounded growth.
 386:    *
 387:    * @param eldest the eldest element which would be removed if this
 388:    *        returns true. For an access-order map, this is the least
 389:    *        recently accessed; for an insertion-order map, this is the
 390:    *        earliest element inserted.
 391:    * @return true if <code>eldest</code> should be removed
 392:    */
 393:   protected boolean removeEldestEntry(Map.Entry eldest)
 394:   {
 395:     return false;
 396:   }
 397: 
 398:   /**
 399:    * Helper method called by <code>put</code>, which creates and adds a
 400:    * new Entry, followed by performing bookkeeping (like removeEldestEntry).
 401:    *
 402:    * @param key the key of the new Entry
 403:    * @param value the value
 404:    * @param idx the index in buckets where the new Entry belongs
 405:    * @param callRemove whether to call the removeEldestEntry method
 406:    * @see #put(Object, Object)
 407:    * @see #removeEldestEntry(Map.Entry)
 408:    * @see LinkedHashEntry#LinkedHashEntry(Object, Object)
 409:    */
 410:   void addEntry(Object key, Object value, int idx, boolean callRemove)
 411:   {
 412:     LinkedHashEntry e = new LinkedHashEntry(key, value);
 413:     e.next = buckets[idx];
 414:     buckets[idx] = e;
 415:     if (callRemove && removeEldestEntry(root))
 416:       remove(root.key);
 417:   }
 418: 
 419:   /**
 420:    * Helper method, called by clone() to reset the doubly-linked list.
 421:    *
 422:    * @param m the map to add entries from
 423:    * @see #clone()
 424:    */
 425:   void putAllInternal(Map m)
 426:   {
 427:     root = null;
 428:     super.putAllInternal(m);
 429:   }
 430: 
 431:   /**
 432:    * Generates a parameterized iterator. This allows traversal to follow
 433:    * the doubly-linked list instead of the random bin order of HashMap.
 434:    *
 435:    * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
 436:    * @return the appropriate iterator
 437:    */
 438:   Iterator iterator(final int type)
 439:   {
 440:     return new Iterator()
 441:     {
 442:       /** The current Entry. */
 443:       LinkedHashEntry current = root;
 444: 
 445:       /** The previous Entry returned by next(). */
 446:       LinkedHashEntry last;
 447: 
 448:       /** The number of known modifications to the backing Map. */
 449:       int knownMod = modCount;
 450: 
 451:       /**
 452:        * Returns true if the Iterator has more elements.
 453:        *
 454:        * @return true if there are more elements
 455:        */
 456:       public boolean hasNext()
 457:       {
 458:         return current != null;
 459:       }
 460: 
 461:       /**
 462:        * Returns the next element in the Iterator's sequential view.
 463:        *
 464:        * @return the next element
 465:        * @throws ConcurrentModificationException if the HashMap was modified
 466:        * @throws NoSuchElementException if there is none
 467:        */
 468:       public Object next()
 469:       {
 470:         if (knownMod != modCount)
 471:           throw new ConcurrentModificationException();
 472:         if (current == null)
 473:           throw new NoSuchElementException();
 474:         last = current;
 475:         current = current.succ;
 476:         return type == VALUES ? last.value : type == KEYS ? last.key : last;
 477:       }
 478:       
 479:       /**
 480:        * Removes from the backing HashMap the last element which was fetched
 481:        * with the <code>next()</code> method.
 482:        *
 483:        * @throws ConcurrentModificationException if the HashMap was modified
 484:        * @throws IllegalStateException if called when there is no last element
 485:        */
 486:       public void remove()
 487:       {
 488:         if (knownMod != modCount)
 489:           throw new ConcurrentModificationException();
 490:         if (last == null)
 491:           throw new IllegalStateException();
 492:         LinkedHashMap.this.remove(last.key);
 493:         last = null;
 494:         knownMod++;
 495:       }
 496:     };
 497:   }
 498: } // class LinkedHashMap