Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

LinkedHashMap and LRU cache

 
Steve Jiang
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
From http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedHashMap.html,

it indicts: "that insertion order is not affected if a key is re-inserted into the map " and " This kind of map is well-suited to building LRU caches"

I understand if the data in LRU cache is hit again, (does it mean the key is reinserted in hashmap??) so the order of key should be updated. then it looks it is different with the description for the reinsertion in LinkedhashMap. Am I wrong here?


Also for the function removeEldestEntry (code below) in above link , I don't understand why it put Map.Entry eldest as input parameter in function, through the input paramert is not used for function.


Anybody help me for the questions?

Thanks,
[ January 17, 2008: Message edited by: Steve Jiang ]
 
Nitesh Kant
Bartender
Posts: 1638
IntelliJ IDE Java MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve: I understand if the data in LRU cache is hit again, (does it mean the key is reinserted in hashmap??) so the order of key should be updated. then it looks it is different with the description for the reinsertion in LinkedhashMap. Am I wrong here?

This just means that if the order of the Map is set as "insertion-order" then replacing an entry does not add the new entry at the end but at the same place as the earlier entry.
This behavior changes when you set the order as "access-order" (for LRU cache )where the new entry will be put at the end. You can set this order using the constructor: LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

Steve:
Also for the function removeEldestEntry (code below) in above link , I don't understand why it put Map.Entry eldest as input parameter in function, through the input paramert is not used for function.




This code is just a simple overridden implementation. There may be some implementation that decide based on the entry whether to remove the eldest entry or not.
[ January 17, 2008: Message edited by: Nitesh Kant ]
 
Lukasz Bajzel
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
LinkedHashMap has a special constructor which takes in the ordering mode which tells the map to maintain the access-order or the insertion order.

//Map linkedMap = new LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);
Map linkedMap = new LinkedHashMap(16,.75f, false);

where
accessOrder = true for access-order (order of entries accessed)
accessOrder = false for insertion-order (order of entries created)

When the accessOrder is specified as true, the map maintains the list in the access order. When it is false, it maintains the order of insertion of the entries. "A call to get(), put(), or putAll() is treated as an access call". An iterator on the map then gets the least-recently accessed to most-recently accessed entries (only if accessOrder = true). So LinkedHashMap is well-suited to building LRU caches.

Hope this helps!

Sincerly,
Your friends at www.javaadvice.com
www.javaadvice.com - The one stop resource for all your Java questions and answers.
 
Steve Jiang
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nitesh, Lukasz

Thanks a lot for your explaination!
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic