From: James Strachan [mailto:[EMAIL PROTECTED]]
> I've also been pondering a solution to the LRU issue that
> preserves the
> efficiency of the bubble list (and avoids expensive tree or
> count-indexing
> data structuers) but solves the problem that Aaron found.
> Still not had any
> bright ideas yet :-(
If my SequencedHashMap patch ever gets applied, there's a simple
extension to that which can be used to have an efficient, true LRU map
(as in least *recently* used -- least access count is a bit stickier).
My latest SequencedHashMap patch includes methods "getFirst" and
"getLast" which allow you to access the first and last entry (or key or
value) of the map. An LRU map could just extend SequencedHashMap,
override the "get" and "put" methods like so:
public Object get(Object key) {
Object value = null;
if(containsKey(key)) { // hashtable lookup -- O(1)
value = super.remove(key); // hashtable remove -- O(1)
super.put(key, value); // hashtable add -- O(1)
}
return value;
}
public Object put(Object key, Object value) {
Object oldValue = super.put(key, value); // hashtable add -- O(1)
if(size() > MAX_SIZE) { // size? I assume this is O(1)
// remove least recently used
remove(getLastKey()); // getLastKey is O(1)
// remove is hashtable remove -- O(1)
}
return oldValue;
}
Note: Need to use the containsKey in the get because you can't just
test for a null value to see if the mapping existed. It's possible and
allowable to have a key that maps to a null value. containsKey is the
only way to determine whether a mapping exists for a particular key when
null values are allowed.
> Maybe renaming it to FastLRUMap that approximates LRU but
> isn't totally
> accurate in all circumstances might help?
To me, that makes it even more confusing.
> James
regards,
michael
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
