LinkedHashMap is a map which maintains the order in which keys are inserted into it.
Example usage:
import java.util.Arrays;
import java.util.LinkedHashSet;
public class Test
{
public static void main(String[] args)
{
LinkedHashSet<Integer> lset = new LinkedHashSet<Integer> ();
lset.addAll(Arrays.asList(new Integer[] { 4, 1, 2, 3 }));
System.out.println(lset.toString());
}
}
Result:
4, 1, 2, 3
LinkedHashMap remembers insertion order by maintaining a doubly-linked list of Map.Entry objects.
In a debugger, it may look like this:
Conceptual Implementation
LinkedHashMap derives HashMap and overrides some of its methods to achieve the above functionality.
It also declares LinkedHashMap.Entry class as a derived class of HashMap.Entry to overrides some of its methods too.
Conceptually, this can be visualized by the following code: (Note that this is not full code. It only captures major functions helpful in understanding the concept)
// Base class from which LinkedHashMap derives
class HashMap<K,V> implements Map<K,V>
{
/***********************************************
* HashMap.Entry class has some methods which are
* meant to be overridden by derived classes like
* LinkedHashMap.Entry
***********************************************/
static class Entry<K,V> implements Map.Entry<K,V>
{
// Method called from HashMap.put(K)
void recordAccess(HashMap<K,V> m) {}
// Method called from HashMap.remove(K)
void recordRemoval(HashMap<K,V> m) {}
}
/*********************************************************
* HashMap.createEntry is also overridden by LinkedHashMap
* This allows derived classes to create their own Entry objects
*********************************************************/
void createEntry(int hash, K key, V value, int bucketIndex)
{
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
}
class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
{
// Doubly linked list used to maintain the insertion order
private Entry<K,V> linkedList;
// Boolean to indicate if order of an existing key should be updated
// with subsequent put() calls for the same key.
// i.e. if this flag is true, existing entries move to the front of the
// linked-list when they are put again in the hash-map.
// This provides behavior like a Least Recently Used (LRU) cache if set to true.
private final boolean accessOrder;
/***********************************************
* LinkedHashMap.Entry extends LinkedHashMap.Entry to
* add before/after fields of a linked-list
***********************************************/
static class Entry<K,V> extends HashMap.Entry<K,V>
{
Entry<K,V> before, after;
private void remove()
{
before.after = after;
after.before = before;
}
// Overridden method to record access if
// LRU behavior is desired
void recordAccess(HashMap<K,V> m)
{
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder)
{
lm.modCount++;
remove();
addBefore(lm.linkedList);
}
}
// Overridden method to record removal of an Entry
void recordRemoval(HashMap<K,V> m)
{
remove();
}
}
/*********************************************************
* Method overridden by LinkedHashMap
* This allows creation of LinkedHashMap.Entry instead of HashMap.Entry
*********************************************************/
void createEntry(int hash, K key, V value, int bucketIndex)
{
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(linkedList);
size++;
}
}
Got a thought to share or found a bug in the code? We'd love to hear from you: