commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Smith" <mich...@iammichael.org>
Subject RE: [Collections] Insertion Ordered Map
Date Sun, 04 Nov 2001 03:06:03 GMT
> -----Original Message-----
> From: Lavandowska [mailto:flanandowska@yahoo.com]
>
> Some while ago there was discussion about HashMaps that maintained
> their insertion order (and what the name of such a thing should be).
>
> I've taken a stab at implementing what I call a FIFOMap.  Because the
> Sets returned by entrySet and keySet must also maintain the insertion
> order, I've also created a FIFOSet.
>
> Please find the two classes attached for your consideration.

I just glanced through those two classes, and while they may actually work as you specify,
I don't think they qualify as a  "HashMap
that maintains their insertion order".  Although you inherit from HashMap, you are not retaining
the HashMap characteristics, most
notably fast lookup and removal.  When you are looking for the value for a particular key,
you potentially need to search through
the entire list.  The time to complete such an operation increases as the size of the map
increases.

Also, the map does not follow the contract defined by the Map interface.  The sets returned
by entrySet(), keySet(), and the
collection returned by values() are supposed to be backed by the map itself, so updates to
the map are reflected in the sets  and
collection, and removals from the sets and collection are reflected in the map.  See the API
docs for Map.entrySet(), Map.keySet(),
and Map.values()

Since I was bored tonight, I implemented a "HashMap that maintains its insertion order". 
It keeps a "fast" lookup and removal while
maintaining entries in the order in which they were added.  I named mine "OrderedHashMap"
just 'cause I think this is a more
appropriate name, although it probably would confuse just as many people as "FIFOMap"; there
really is no "perfect" name for such a
map.

It compiles, but I didn't do any real testing, so use at your own risk.

If this is something that would be worthwhile to have in commons, a committer is more than
welcome to attach the Apache license and
commit it -- just keep my name on it.  :)

regards,
michael

p.s. Since you admitted in the top of FIFOMap that you don't know how to implement a real
HashMap, you may want to check out Chapter
12 in "Introduction To Algorithms" by Cormen, Leiserson, and Rivest.  It's kind of an expensive
book, but well worth it.  ISBN#
0-07-013143-0

Mime
View raw message