commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From <>
Subject RE: [Collections] Insertion Ordered Map
Date Sun, 04 Nov 2001 20:00:59 GMT

I too have assumed the Ordered bit means FIFO (just how many OrderedMap's
are there out there??). I've two immediate thought's I'd like to bring to
the table.

The first is just a passing mention of SequencedHashMap, from the
Commons.Collections package, it appears to be a solution to some of these
issues, and we need to decide what the differences are with Michael's
class. I imagine the biggest is the MapEntry stuff, which tends to get
ignored in Map APIs a lot I think.

The second is why all the panic about the Hash part of it. My view of
extended Collection classes has always been to make a ProxyMap class,
which does nothing but delegate to another Map, and implement Map, and
then extend that. That way if you want a Hash style functionality, you
pass that in, but if you want something else, you pass that in too.
HashMap seems a reasonable default value.

For example, how would you create an OrderedSoftRefHashMap?

It should be:   new OrderedMap(new SoftRefMap(new HashMap()));

with the new HashMap() part being redundant as it's a default. and Ordered
and SoftRef both extending Proxy.

The same style should apply to Lists too.

I would like to see Commons.Collections moving to fit this style,
speed-wise there is a cost of a method call per 'chain', but the extra
power in design makes it a big win for me.

What it would basically mean in implementation terms is:

not extending HashMap, but implementing Map.
wrap a Map, rather than rely on extended methods.
provide 2 constructors, an empty-default, and one for the wrapped Map.

Anyways, any opinions?

I'm not convinced that this class needs any map implementation, but rather
can be built up of already existing building blocks.


On Sun, 4 Nov 2001, Lavandowska wrote:

> Michael,
> I got some time to test OrderedHashMap, and found it was maintaining
> "reverse insertion order" or FILO.  FIFO was *my* desired behaviour,
> but FILO could be desirable in other situations.  Perhaps this
> condition would merit a different naming scheme than "Ordered" (Ordered
> according to what?).
> Getting it to FIFO involved this change:
> private void insertEntry(Entry entry) {
> = sentinel;
>   	entry.prev = sentinel.prev;
> = entry;
>   	sentinel.prev = entry;
> }
> I've attached a little tester class that proves that for large Maps,
> OrderedHashMap is faster (at 1400 keys it is twice as fast).  While it
> doesn't provide proper support for the keySet, entrySet & values
> methods, FIFOMap was faster for small Maps (tested on an order of 10:
> 140 keys vs 1400 keys).  I doubt its worth the investigation to get
> FIFOMap to support these methods properly, but I might do it anyway for
> my own education.
> Lance
> __________________________________________________
> Do You Yahoo!?
> Find a job, post your resume.

To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message