Re: LinkedHashMap.java: circular?

[Eric Blake]

Ype, feel free to borrow the ideas of LinkedHashMap to write your own 
efficient version of a caching ordered hash table.  Writing your own 
version may be the best in the long run, because you can be more 
efficient (such as actually overriding put(), instead of having to use 
the addEntry() hack to remain API compatible).

However, your question led me into poking around in the code. 
Classpath's current version has a bug in that it changes access order 
via the entrySet().iterator(), when the docs say this should not happen.

Also, I do not feel that the Classpath version can be optimized into a 
circular list, because of the API of removeEldestEntry() - it is 
guaranteed to be called after the insertion but before the deletion, and 
the user has the right to see the list in that state.  Well, maybe a 
circular list is possible, but the list must have one more element than 
what size() normally reports to avoid object creation in the event of a 
likely entry removal.  I'll play with the idea, and see if I can improve 
the code, but I doubt it.

I'll see about fixing my bug in the near future, as well as committing a 
testcase to mauve.


Ype Kingma wrote:
> Eric,
>
> I'm referring to the current cvs version from 
> subversions.gnu.org:/cvsroot/classpath .
>
> The other day I needed a lru cache in jython (ie. python implemented in java)
> and I found that LinkedHashMap.java would do the job well, except that I'm 
> currently forced to use java 1.1 and the collections replacement for 1.1 does 
> not include a LinkedHashMap. 
> That meant I needed to write a linked hash map with a doubly linked list and 
> a maximum capacity in python.
>
> With the maximum capacity constraint I found that when implementing
> the doubly linked list as a circular list the insertion of a new element when 
> the cache is full (ie. the normal case) can be implemented nicely by updating 
> the oldest element and simply moving the list head and tail pointers one 
> element. This also saves the creation of a new list element.
>
> My question:
> Since this is probably a frequent use of LinkedHashMap I wondered whether a 
> circular list might be a good alternative for the current implementation of 
> the LinkedHashMap, in which the head and tail elements have their prev and 
> succ pointers set to null.
>
> Anyway, in case I run into memory problems with my current python 
> implementation I'm probably going to use your LinkedHashMap class in java 1.1 
> as it is.
> For use as list elements, python objects in java are far too large, they have 
> an associated dictionary for their fields.
>
> Thanks and regards,
> Ype


--
This signature intentionally left boring.

Eric Blake             address@hidden
  BYU student, free software programmer