1 /* LinkedHashMap.java -- a class providing hashtable data structure,
2 mapping Object --> Object, with linked list traversal
3 Copyright (C) 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GNU Classpath.
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)
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.
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., 59 Temple Place, Suite 330, Boston, MA
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
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. */
43 * This class provides a hashtable-backed implementation of the
44 * Map interface, with predictable traversal order.
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.
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>.
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>.
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.
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.
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>
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.
99 * @author Eric Blake (ebb9@email.byu.edu)
100 * @see Object#hashCode()
107 * @status updated to 1.4
109 public class LinkedHashMap
extends HashMap
112 * Compatible with JDK 1.4.
114 private static final long serialVersionUID
= 3801124242820219131L;
117 * The oldest Entry to begin iteration at.
119 transient LinkedHashEntry root
;
122 * The iteration order of this linked hash map: <code>true</code> for
123 * access-order, <code>false</code> for insertion-order.
125 * @serial true for access order traversal
127 final boolean accessOrder
;
130 * Class to represent an entry in the hash table. Holds a single key-value
131 * pair and the doubly-linked insertion order list.
133 class LinkedHashEntry
extends HashEntry
136 * The predecessor in the iteration list. If this entry is the root
137 * (eldest), pred points to the newest entry.
139 LinkedHashEntry pred
;
141 /** The successor in the iteration list, null if this is the newest. */
142 LinkedHashEntry succ
;
145 * Simple constructor.
148 * @param value the value
150 LinkedHashEntry(Object key
, Object value
)
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.
173 if (accessOrder
&& succ
!= null)
194 * Called when this entry is removed from the map. This version does
195 * the necessary bookkeeping to keep the doubly-linked list in order.
197 * @return the value of this key as it is removed
207 else if (succ
== null)
219 } // class LinkedHashEntry
222 * Construct a new insertion-ordered LinkedHashMap with the default
223 * capacity (11) and the default load factor (0.75).
225 public LinkedHashMap()
232 * Construct a new insertion-ordered LinkedHashMap from the given Map,
233 * with initial capacity the greater of the size of <code>m</code> or
237 * Every element in Map m will be put into this new HashMap, in the
238 * order of m's iterator.
240 * @param m a Map whose key / value pairs will be put into
241 * the new HashMap. <b>NOTE: key / value pairs
242 * are not cloned in this constructor.</b>
243 * @throws NullPointerException if m is null
245 public LinkedHashMap(Map m
)
252 * Construct a new insertion-ordered LinkedHashMap with a specific
253 * inital capacity and default load factor of 0.75.
255 * @param initialCapacity the initial capacity of this HashMap (>= 0)
256 * @throws IllegalArgumentException if (initialCapacity < 0)
258 public LinkedHashMap(int initialCapacity
)
260 super(initialCapacity
);
265 * Construct a new insertion-orderd LinkedHashMap with a specific
266 * inital capacity and load factor.
268 * @param initialCapacity the initial capacity (>= 0)
269 * @param loadFactor the load factor (> 0, not NaN)
270 * @throws IllegalArgumentException if (initialCapacity < 0) ||
271 * ! (loadFactor > 0.0)
273 public LinkedHashMap(int initialCapacity
, float loadFactor
)
275 super(initialCapacity
, loadFactor
);
280 * Construct a new LinkedHashMap with a specific inital capacity, load
281 * factor, and ordering mode.
283 * @param initialCapacity the initial capacity (>=0)
284 * @param loadFactor the load factor (>0, not NaN)
285 * @param accessOrder true for access-order, false for insertion-order
286 * @throws IllegalArgumentException if (initialCapacity < 0) ||
287 * ! (loadFactor > 0.0)
289 public LinkedHashMap(int initialCapacity
, float loadFactor
,
292 super(initialCapacity
, loadFactor
);
293 this.accessOrder
= accessOrder
;
297 * Clears the Map so it has no keys. This is O(1).
306 * Returns <code>true</code> if this HashMap contains a value
307 * <code>o</code>, such that <code>o.equals(value)</code>.
309 * @param value the value to search for in this HashMap
310 * @return <code>true</code> if at least one key maps to the value
312 public boolean containsValue(Object value
)
314 LinkedHashEntry e
= root
;
317 if (equals(value
, e
.value
))
325 * Return the value in this Map associated with the supplied key,
326 * or <code>null</code> if the key maps to nothing. If this is an
327 * access-ordered Map and the key is found, this performs structural
328 * modification, moving the key to the newest end of the list. NOTE:
329 * Since the value could also be null, you must use containsKey to
330 * see if this key actually maps to something.
332 * @param key the key for which to fetch an associated value
333 * @return what the key maps to, if present
334 * @see #put(Object, Object)
335 * @see #containsKey(Object)
337 public Object
get(Object key
)
340 HashEntry e
= buckets
[idx
];
343 if (equals(key
, e
.key
))
354 * Returns <code>true</code> if this map should remove the eldest entry.
355 * This method is invoked by all calls to <code>put</code> and
356 * <code>putAll</code> which place a new entry in the map, providing
357 * the implementer an opportunity to remove the eldest entry any time
358 * a new one is added. This can be used to save memory usage of the
359 * hashtable, as well as emulating a cache, by deleting stale entries.
362 * For example, to keep the Map limited to 100 entries, override as follows:
364 * private static final int MAX_ENTRIES = 100;
365 * protected boolean removeEldestEntry(Map.Entry eldest)
367 * return size() > MAX_ENTRIES;
371 * Typically, this method does not modify the map, but just uses the
372 * return value as an indication to <code>put</code> whether to proceed.
373 * However, if you override it to modify the map, you must return false
374 * (indicating that <code>put</code> should leave the modified map alone),
375 * or you face unspecified behavior. Remember that in access-order mode,
376 * even calling <code>get</code> is a structural modification, but using
377 * the collections views (such as <code>keySet</code>) is not.
380 * This method is called after the eldest entry has been inserted, so
381 * if <code>put</code> was called on a previously empty map, the eldest
382 * entry is the one you just put in! The default implementation just
383 * returns <code>false</code>, so that this map always behaves like
384 * a normal one with unbounded growth.
386 * @param eldest the eldest element which would be removed if this
387 * returns true. For an access-order map, this is the least
388 * recently accessed; for an insertion-order map, this is the
389 * earliest element inserted.
390 * @return true if <code>eldest</code> should be removed
392 protected boolean removeEldestEntry(Map
.Entry eldest
)
398 * Helper method called by <code>put</code>, which creates and adds a
399 * new Entry, followed by performing bookkeeping (like removeEldestEntry).
401 * @param key the key of the new Entry
402 * @param value the value
403 * @param idx the index in buckets where the new Entry belongs
404 * @param callRemove whether to call the removeEldestEntry method
405 * @see #put(Object, Object)
406 * @see #removeEldestEntry(Map.Entry)
407 * @see LinkedHashEntry#LinkedHashEntry(Object, Object)
409 void addEntry(Object key
, Object value
, int idx
, boolean callRemove
)
411 LinkedHashEntry e
= new LinkedHashEntry(key
, value
);
412 e
.next
= buckets
[idx
];
414 if (callRemove
&& removeEldestEntry(root
))
419 * Helper method, called by clone() to reset the doubly-linked list.
421 * @param m the map to add entries from
424 void putAllInternal(Map m
)
427 super.putAllInternal(m
);
431 * Generates a parameterized iterator. This allows traversal to follow
432 * the doubly-linked list instead of the random bin order of HashMap.
434 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
435 * @return the appropriate iterator
437 Iterator
iterator(final int type
)
439 return new Iterator()
441 /** The current Entry. */
442 LinkedHashEntry current
= root
;
444 /** The previous Entry returned by next(). */
445 LinkedHashEntry last
;
447 /** The number of known modifications to the backing Map. */
448 int knownMod
= modCount
;
451 * Returns true if the Iterator has more elements.
453 * @return true if there are more elements
454 * @throws ConcurrentModificationException if the HashMap was modified
456 public boolean hasNext()
458 if (knownMod
!= modCount
)
459 throw new ConcurrentModificationException();
460 return current
!= null;
464 * Returns the next element in the Iterator's sequential view.
466 * @return the next element
467 * @throws ConcurrentModificationException if the HashMap was modified
468 * @throws NoSuchElementException if there is none
472 if (knownMod
!= modCount
)
473 throw new ConcurrentModificationException();
475 throw new NoSuchElementException();
477 current
= current
.succ
;
478 return type
== VALUES ? last
.value
: type
== KEYS ? last
.key
: last
;
482 * Removes from the backing HashMap the last element which was fetched
483 * with the <code>next()</code> method.
485 * @throws ConcurrentModificationException if the HashMap was modified
486 * @throws IllegalStateException if called when there is no last element
490 if (knownMod
!= modCount
)
491 throw new ConcurrentModificationException();
493 throw new IllegalStateException();
494 LinkedHashMap
.this.remove(last
.key
);
500 } // class LinkedHashMap