This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Java in General and the fly likes  LinkedHashMap  and LRU cache Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark " LinkedHashMap  and LRU cache" Watch " LinkedHashMap  and LRU cache" New topic
Author

LinkedHashMap and LRU cache

Steve Jiang
Ranch Hand

Joined: May 17, 2004
Posts: 107
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

Joined: Feb 25, 2007
Posts: 1638

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 ]

apigee, a better way to API!
Lukasz Bajzel
Greenhorn

Joined: Dec 03, 2007
Posts: 26
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

Joined: May 17, 2004
Posts: 107
Nitesh, Lukasz

Thanks a lot for your explaination!
 
Consider Paul's rocket mass heater.
 
subject: LinkedHashMap and LRU cache
 
Similar Threads
LinkedHashMap and HashMap
HashMap
ArrayList versus HashMap
Hashtable Problem
order of Map