How LinkedHashMap works internally - Java

The data structure of LinkedHashMap extends that of HashMap.
In HashMap, the data structure is based on array and linked list. An entry finds its location in the array based on its hash value. If an array element is already occupied, the new entry replaces the old entry and the old entry is linked to the new one.
In HashMap, there is no control on the iteration order.
In LinkedHashMap, the iteration order is defined, either by the insertion order or access order.
LinkedHashMap differs from HashMap in that it maintains a doubly-linked list running through all of its entries. The below one is a modified example of the above data structure. It defines the iteration ordering based on the order in which keys were inserted into the map. In order to do so, the entry element is extended to keep track of the after and before element. A zero size LinkedHashMap contains just the Head element with before and after pointing to itself.
LinkedHashMap data structure
LinkedHashMap data strutcture
Below is the HashMap data structure:
HashMap Data Structure
HashMap data structure

 Entry

LinkedHashMap's Entry extends the HashMap's Entry so it also inherits the same properties key, value, hash and the next Entry sharing the index. Other than these, it also has couple of additional properties to maintain the double-linked list, after and before entries.
LinkedHashMap Entry class
LinkedHashMap Entry class

New Entry

LinkedHashMap inherits HashMap so its internal data structure is same as that of HashMap. Apart from that it also maintains a double-linked list which is circularly linked via the sentinel node called head. Each node contains references to the previous and to the next node . A new node is always added to the end of the list. In order to do so, the last node’s and the header node’s links have to be adjusted.
  1. The new node’s next reference will point to the head.
  2. The new node’s previous reference will point to the current last node.
  3. The current last node’s next reference will point to the new node instead of head.
  4. Head’s previous reference will point to the new node.
?
1
2
3
4
after  = head;
before = head.before;
before.after = this;
after.before = this;
Double linked-list
Double linked-list
Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list.

Access Ordered

A special LinkedHashMap(capacity, loadFactor, accessOrderBoolean) constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently. Invoking the put or get method results in an access to the corresponding entry. If the enclosing Map is access-ordered, it moves the entry to the end of the list; otherwise, it does nothing.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void testLinkedHashMap() {
    LinkedHashMap lru = new LinkedHashMap(16, 0.75f, true);
    lru.put("one", null);
    lru.put("two", null);
    lru.put("three", null);
 
    Iterator itr = lru.keySet().iterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
 
    System.out.println("** Access one, will move it to end **");
    lru.get("one");
 
    itr = lru.keySet().iterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
 
    System.out.println("** Access two, will move it to end **");
    lru.put("two", "two");
 
    itr = lru.keySet().iterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}
?
1
2
3
4
5
6
7
8
9
10
11
12
Result:
one
two
three
** Access one, will move it to end **
two
three
one
** Access two, will move it to end **
three
one
two
Thus in access-ordered linked hash maps, merely querying the map with get is a structural modification.

Ref: http://javarticles.com/2012/06/linkedhashmap.html

Comments

Post a Comment

Popular posts from this blog

EJB - Stateful vs Stateless

For  stateless session beans  the server can maintain a variable amount of instances in a pool. Each time a client requests such a stateless bean (e.g. through a method) a random instance is chosen to serve that request. That means if the client does two subsequent requests it is possible that two different instances of the stateless bean serve the requests. In fact there is no conversational state between the two requests. Also if the client disappears, the stateless bean does not get destroyed and can serve the next request from another client. On the other hand a  stateful session bean  is closely connected to the client. Each instance is created and bounded to a single client and serves only requests from that particular client. So happens that if you do two subsequent requests on a stateful bean, your request will be served always from the same instance of the bean. That means you can maintain a conversational state between the requests. At the end of the li...
Read more

Mirror binay tree - Java

public class TreeNode {     private TreeNode left;     private TreeNode right;     private Object value;     public TreeNode getLeft() {         return left;     }     public TreeNode setLeft(TreeNode left) {         this.left = left;         return this;     }     public TreeNode getRight() {         return right;     }     public TreeNode setRight(TreeNode right) {         this.right = right;         return this;     }     public Object getValue() {         return value;     }     public TreeNode setValue(Object value) {         this.value = value;         return this;     } } public class Mirror {     public stat...
Read more