LRU and Hashtable/HashMap

[Ted Nordea]

Hello,

I have a LRU/hashtable question for you.
I'm implementing a cache for requested www pages.
All requested pages are put to hashtable. Hashtable's key is page's name
and actual data object is a class containing page's content and timestamp telling when it was last accessed. Nothing special yet.

This cache has also a maximum size in bytes and after it is achieved
oldest items should be removed from cache (for making more room) when
new web pages are requested.

My question: is Hashtable/Hashmap proper data structure for
that kind of purpose? I have not succeeded to manage LRU based algoritm
to remove those oldiest items because only way I know to get information
of timestamps is using Iterator for the whole Hashtable (I do not like idea of iterating whole Hastable).

So, has anyone any idea how to get access to timestamp fields in Hashtable
and then remove the oldiest items there. I mean more elegant way than iterating all objects in Hashtable and checking their timestamp fields.

I found a class file named LRUHashtable.java with google.com from
Internet using Hashtable for LRU caching but did not understood how
it actually managed removing oldiest items. Not using timestamp at all, I thing.

So, is my approach using Hashtable for this purpose wrong. Like to
hear your advices and points to get more information.

Best Regards!

TN

[Warren Dew]

The HashMap is fine for accessing cache items and determining cach hits and misses. However, if you want to improve cache management efficiency, you might want to use a separate data structure to manage removal of the cache items.

A linked list would probably work well for LRU - just add items to the head of the list, move items back to the head of the list when they are used again, and drop items from the tail of the list when you need space. This would also eliminate the need for a timestamp.

[Ted Nordea]

A linked list would probably work well for LRU - just add items to the head of the list, move items back to the head of the list when they are used again, and drop items from the tail of the list when you need space. This would also eliminate the need for a timestamp.

Yes, now I understood that linked list type solution!
So simple way to resolve this kind on problem without timestamp, Thanks to you!

BTW I'm looking good Java algorithm books, can anyone suggest me good ones?
I'm not looking for books like Core Java/Horstman (which is a good book)
rather books telling different kind of algorithms/data structures. I have
read Cormen's book when I was studying but code it that book is pseudocode
and it does not offer as much examples considering e.g. graphs, searching etc. that I would like to read.

Best Regards!