The interview questions
- How is LinkedHashMap ordered
- How do I implement LRU with LinkedHashMap
If you don’t want to see the source code, you can go to the bottom to see the answer
The source code parsing
LinkedHashMap extends Map to provide sequential access. This order is controlled by accessOrder, which can be the insertion order of nodes or the access time order of nodes.
LinkedHashMap also provides the removeEldestEntry method, which can be used to remove the oldest access point.
LRU caching can be implemented with accessOrder and removeEldestEntry.
As shown in the figure, LinkedHashMap implements sequential access in a relatively simple way, maintaining a bidirectional linked list in addition to the HashMap implementation. Whenever a node is inserted, it needs to be maintained not only in the Map, but also in the linked list. The PUT, get, and other methods in HashMap provide hook methods, such as afterNodeAccess, afterNodeInsertion, and visting emoval. In this way, LinkedHashMap can perform some specialized maintenance on these nodes.
Sequential access is achieved by traversing the LinkedHashMap by traversing the linked list instead of traversing the slots in the Map.
Underlying data structure
/** * LinkedHashMap a common list Node that inherits the HashMap Node and adds before and after Pointers to each Node. LinkedHashMap maintains a bidirectional linked list on the basis of HashMap. The nodes in the linked list are each node in the Map. * Through this linked list, LinkedHashMap achieves the purpose of maintaining the order of nodes */
static class Entry<K.V> extends HashMap.Node<K.V> {
Entry<K, V> before, after;
Entry(int hash, K key, V value, Node<K, V> next) {
super(hash, key, value, next); }}/** * the header of the bidirectional list */
transient LinkedHashMap.Entry<K, V> head;
/** * the end of the bidirectional list */
transient LinkedHashMap.Entry<K, V> tail;
/** * true- access order (earliest nodes first) * false- insert order traversal (earliest nodes first) **@serial* /
final boolean accessOrder;
Copy the codeThe Node Node
Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
LinkedHashMap.Entry<K, V> p =
new LinkedHashMap.Entry<K, V>(hash, key, value, e);
// To create a key-value pair, place the LinkedHashMap as well as the map
// The built-in bidirectional list is used to maintain the insertion order
linkNodeLast(p);
return p;
}
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
LinkedHashMap.Entry<K, V> q = (LinkedHashMap.Entry<K, V>) p;
LinkedHashMap.Entry<K, V> t =
new LinkedHashMap.Entry<K, V>(q.hash, q.key, q.value, next);
// Replace q with t in the bidirectional list
transferLinks(q, t);
return t;
}
TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) {
TreeNode<K, V> p = new TreeNode<K, V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
LinkedHashMap.Entry<K, V> q = (LinkedHashMap.Entry<K, V>) p;
TreeNode<K, V> t = new TreeNode<K, V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
Copy the codeUtility methods
// Add nodes at the end of the bidirectional list
private void linkNodeLast(LinkedHashMap.Entry<K, V> p) {
LinkedHashMap.Entry<K, V> last = tail;
tail = p;
if (last == null)
head = p;
else{ p.before = last; last.after = p; }}// Use the DST node to override the SRC node position in the bidirectional list
private void transferLinks(LinkedHashMap.Entry
src, LinkedHashMap.Entry
dst)
,>
,> {
LinkedHashMap.Entry<K, V> b = dst.before = src.before;
LinkedHashMap.Entry<K, V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
/** * Whether the oldest Node needs to be deleted each time a new Node is inserted. * *@returnTrue - removes the oldest node, false- does not remove */
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return false;
}
Copy the codeA constructor
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(a) {
super(a); accessOrder =false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(a); accessOrder =false;
putMapEntries(m, false);
}
/** * specifies the order in which nodes are traversed **@paramAccessOrder true- accessOrder (earliest operated node first) * false- insert order traversal (earliest inserted node first) */
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
Copy the codeHook method
// Override the hook method provided for LinkedHashMap in HashMap
/** * The hook method is called when the HashMap calls remove, with e being the removed node */
void afterNodeRemoval(Node<K, V> e) {
// p = e; b = p.before; a = p.after;
LinkedHashMap.Entry<K, V> p =
(LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after;
// Delete p from the bidirectional list
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
/** * The hook method ** is called when a HashMap calls a put or other method@paramEvict false-table is in create mode (that is, called by constructor) */
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K, V> first;
// If there are elements in the map and need to delete the eldest element, then from the linked list and map
// Delete the bidirectional list header. RemoveEldestEntry is returned by default in LinkedHashMap
/ / false. This method can be used to implement LRU caching
if(evict && (first = head) ! =null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null.false.true); }}/** * This hook method is used to change the last access time when a HashMap calls put, get, etc. * can be used to implement LRU caching * *@paramE The most recently operated node */
void afterNodeAccess(Node<K, V> e) {
LinkedHashMap.Entry<K, V> last;
// If accessOrder is true, the linked list is maintained according to the latest traversal
// move e to the end of the list
if(accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after; p.after =null;
if (b == null)
head = a;
else
b.after = a;
if(a ! =null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else{ p.before = last; last.after = p; } tail = p; ++modCount; }}Copy the codeother
public boolean containsValue(Object value) {
// Because all nodes are maintained in LinkedHashMap using a bidirectional list, only traversal is required
// A bidirectional list traverses all nodes. Instead of iterating through the Map.
for(LinkedHashMap.Entry<K, V> e = head; e ! =null; e = e.after) {
V v = e.value;
if(v == value || (value ! =null && value.equals(v)))
return true;
}
return false;
}
public V get(Object key) {
Node<K, V> e;
// find the corresponding node of the key
if ((e = getNode(hash(key), key)) == null)
return null;
// If you need to sort by access time, update the position of nodes in the bidirectional linked list
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
Node<K, V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public void clear(a) {
super.clear();
head = tail = null;
}
public void forEach(BiConsumer<? super K, ? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
// Overrides the traversal method by traversing a bidirectional list instead of a map, thus implementing sequential traversal.
for(LinkedHashMap.Entry<K, V> e = head; e ! =null; e = e.after)
action.accept(e.key, e.value);
if(modCount ! = mc)throw new ConcurrentModificationException();
}
Copy the codeThe iterator
abstract class LinkedHashIterator {
// The next node to iterate over
LinkedHashMap.Entry<K, V> next;
// The last node traversed
LinkedHashMap.Entry<K, V> current;
/ / version number
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext(a) {
returnnext ! =null;
}
final LinkedHashMap.Entry<K, V> nextNode(a) {
LinkedHashMap.Entry<K, V> e = next;
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
// Iterate over the next node in the bidirectional list
next = e.after;
return e;
}
public final void remove(a) {
Node<K, V> p = current;
if (p == null)
throw new IllegalStateException();
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null.false.false); expectedModCount = modCount; }}Copy the codeInterview Answers
-
How is LinkedHashMap ordered
LinkedHashMap Maintains nodes for each key-value in an additional two-way linked list on top of the HashMap.
LinkedHashMap can be accessed either in insertion order or in traversal order through accessOrder
accessOrder
- False: Sort by insertion order. For each node inserted into the map, place the node at the end of the bidirectional linked list
- True: Sort by access order. When operating on a node in a map, the hook method provided by HashMap (
afterNodeAccess,afterNodeInsertionandafterNodeRemovalFind the node’s position in the list and move it to the end of the list. The first node of the linked list is the node that the list has not accessed for the longest time
When traversing, sequential access is achieved by facilitating bidirectional linked lists instead of traversing each slot of the map.
-
How do I implement LRU with LinkedHashMap
Firstly, the characteristics of LRU algorithm are analyzed
- New data is inserted at the end of the list (representing the latest access);
- Whenever a cache hit (that is, cached data is accessed), the data is moved to the end of the linked list (representing the latest access);
- When the list is full, discard the data in the head of the list (delete the node that has not been accessed for the longest time);
Nodes are maintained in traversal order by setting accessOrder to true as long as the LinkedHashMap keeps them in order.
- The PUT method inserts the node into the end of the bidirectional linked list to achieve LRU property 1;
- Hook method
afterNodeAccessImplement LRU feature 2; - Implement the removeEldestEntry method to delete the node that has not been accessed for the longest time. Implement LRU feature 3;