> -----Original Message-----
> From: Lavandowska [mailto:[EMAIL PROTECTED]]
>
> 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
OrderedHashMap.java
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
