• Post Reply Bookmark Topic Watch Topic
  • New Topic

Data Structure  RSS feed

 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

I am implementing a cache to store objects, and the user can also pass an algorithm to use for the cache to remove elements when it's full. So, I've implemented an interface and extended it for the different strategies like LRU etc. and overridden the remove() method.

I am using a hashmap internally to store all cache objects and then when I need to call an algorithm, I pass the hashmap as parameter. But, for LRU specifically, I am calling the remove() method everytime my cache is accessed ( for add() and get() methods). The cache takes the key and the hashmap as the parameters. I pass the key because I have a linked list in the cache to maintain the order in which the keys are inserted and accessed. Then when it's time to remove, I do something like h.remove(list.poll()) so that the 1st element in the list (least recently used key) is removed from the hashmap along with its value.

Also, I update the linked list every time by doing a remove() and then add() whenever a key is accessed. Is there a better data structure to use here instead of the linked list?

Here is my remove() code for LRU:

q is my linked list.



I call this method for every add or get operation done to my cache.



Thanks,
Prasanna
 
Campbell Ritchie
Marshal
Posts: 56562
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What's LRU?
I went through the Map interface and the Collection interface but couldn't see any implementing classes which demonstrate the functionality of losing oldest elements when the Map reaches a particular size.
You can try a weak map, or a linked map. In the case of a linked map, you iterate in insertion order and you can use the remove method of the iterator.
There might be a map which removes its oldest elements automatically in Apache Commons.

There is something strange about that remove method. Why are you passing the Map as a parameter and returning the same Map as a return type? Why HashMap rather than Map? Why haven't you parameterised the Map?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:What's LRU?

Least Recently Used - at least that's what I understand it as.

@Prasanna: Did you look at my comment on one of your other posts? Because LinkedHashMap has documented behaviour specifically designed for LRU-caches.

Winston
 
Campbell Ritchie
Marshal
Posts: 56562
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It was a linked map, after all.
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Winston,

Yes, I did look at your post there, sorry I should have referred to it here. In fact that's what prompted my question here. I don't understand how I can make use of a linked hashmap in my scenario for Least Recently Used algorithm. Would I just use a linkedhashmap in place of a linked list there? If so, what performance difference does it make?
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Campbell - Sorry, LRU is Least Recently Used.

Why is the method strange? Is something wrong about passing a hashmap, making some changes to it and returning the same hashmap? Actually, I did parameterize it later, it should be <Object, Object> there.
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Campbell - Does this code look better?



Also, if I used another map instead of my linked list, is it not going to offer the same performance? Or, is it better?
 
Campbell Ritchie
Marshal
Posts: 56562
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You would appear not to have read the previous posts. Particularly Winston Gutkowski's.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:I don't understand how I can make use of a linked hashmap in my scenario for Least Recently Used algorithm. Would I just use a linkedhashmap in place of a linked list there?

Pretty much. As I said, the only difference is that LHM won't allow you to store duplicate values; but from what I see, that shouldn't be a problem. I already told you where to look in the other thread, so read the docs first and come back if there's something specific you don't understand.

If so, what performance difference does it make?

Since the docs make no mention of it, my guess is: not a lot - but I have to admit to never having done any serious benchmarks. I've always found it perfectly adequate, and one presumes that the designers wouldn't have built in the facility if it affects performance so badly that people won't use it.

However, that's the last question you should be concerning yourself with at the moment. Worry about performance when (or if) you find it's too slow.

Winston
 
Campbell Ritchie
Marshal
Posts: 56562
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Entering and removing the first or last elements in a linked list, and entering or removing anywhere in a hash map, all run in constant time, so I can't see that there would be a performance problem.
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I did read the LinkedHashMap specification and I can't understand how to use it here.

The spec says that the removeEldestEntry() method is automatically called by the put() and putAll() methods, but I also have a get method() in Cache. Accessing the get() method should also make an entry "used".
 
Campbell Ritchie
Marshal
Posts: 56562
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It says it returns whether the oldest entry should be removed. So I suspect you should override itThen you use that in an if statement to remove the oldest, which you can get from getFirst or getLast from the linked list or more precisely from an Iterator.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!