You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Lavandowska <fl...@yahoo.com> on 2001/11/03 23:39:31 UTC
[Collections] Insertion Ordered Map
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.
=====
Lance Lavandowska
Http://www.brainopolis.com/
__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com
[PATCH] RE: [Collections] Insertion Ordered Map
Posted by Michael Smith <mi...@iammichael.org>.
> -----Original Message-----
> From: dlr@despot.finemaltcoding.com
> [mailto:dlr@despot.finemaltcoding.com]On Behalf Of Daniel Rall
> > Some while ago there was discussion about HashMaps that maintained
> > their insertion order (and what the name of such a thing should be).
>
> @see org.apache.commons.collections.SequencedHashMap
Hmmm.... Sounds like a more reasonable name, but the implementation of
Sequenced HashMap suffers from some of the the same problem that Lance's
posted version did: Adding and removing from the list are both O(n)
(although adding is O(1) when the key does not already exist, it's O(n)
if it does). A "Hash" map implies that insertions, lookups, and
removals from the mapping are O(1) based on hashed lookups.
Additionally, the sets and collections in SequencedHashMap returned by
keySet(), values(), and entries() are not properly backed by the map.
Removing an element from one of those sets/collections, will cause the
SequencedHashMap to retain objects in its sequence which no longer
appear in the map. That's a bug. Attached is a patch to the test case
to test for such a condition. When running the test cases, I noticed
that the SequencedHashMap tests are already failing due to keySet() not
maintaining order of the keys when cloned.
The implementation that I provided gives true hash map functionality,
including O(1) insertions, lookups and removals, has iterators that are
backed by the underlying map, and fixes the failing tests (both the old
one and my new one). For your reference, I've reattached it to this
message. Since there is a preexisting class, I've kept it
backwards-compatible by adding implementations of all the existing
methods.
To simplify the commit of the rewriten SequencedHashMap, I have also
attached a diff against the current CVS version.
regards,
michael
Attachment summary:
tests.patch - patch against test case to ensure consistency when
removing an element using an iterator on the keySet()
test-results.pre - results of the test cases after adding the new test
case and before any changes to SequencedHashMap
sequencedhashmap.patch - diff for the new version of
SequencedHashMap.java
SequencedHashMap.java - new version of SequencedHashMap that maintains
O(1) insertion, removal, lookup. It also has keySet(), values(), and
entrySet() that are backed by the map correctly.
test-results.post - results of the test cases after changing
SequencedHashMap
Re: [Collections] Insertion Ordered Map
Posted by Daniel Rall <dl...@finemaltcoding.com>.
Lavandowska <fl...@yahoo.com> writes:
> Some while ago there was discussion about HashMaps that maintained
> their insertion order (and what the name of such a thing should be).
@see org.apache.commons.collections.SequencedHashMap
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [Collections] Insertion Ordered Map
Posted by Lavandowska <fl...@yahoo.com>.
--- Michael Smith <mi...@iammichael.org> wrote:
> 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.
Thank you for the corrections. I made my pathetic attempt since no-one
else had ;-)
Lance
__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [Collections] Insertion Ordered Map
Posted by ba...@generationjava.com.
On Sun, 4 Nov 2001, Lavandowska wrote:
> > The first is just a passing mention of SequencedHashMap, from the
> > Commons.Collections package, it appears to be a solution to some of
>
> SequencedHashMap fails in that the Set it returns for keySet does not
> maintain insertion order (believe me, I've tried it).
Yeah, I think you're meant to call sequence(). Not really perfect.
>
> > 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,
>
> I'm not sure if your suggestion would fit or not, but my particular
> concern is a case where a third-party piece of software requires a
> HashMap, but I want to use one that maintains insertion order (not
> something currently supported) rather than random or Natural ordering.
>
> If your ProxyMap solution can provide for both these cases (can be
> recognized as a HashMap and supports "arbitrary ordering") I would
> cheer the flexibility you propose.
Ugh. I hate APIs that enforce a need for HashMap rather than just Map :)
The only solution that leaps out to me is a HashMap which just proxies to
a Map, ie) a HashMapAdaptor. This seems to be sending us on swings nd
roundabouts a bit, but I still prefer it to effectively declaring all
Commons.Collections Map classes to be HashMap and not be chainable.
The other big problem is the single-inheritence of Java. One of my Map
extensions is TypedMap, which enforces that only certain types are added
to the Map. This currently extends AbstractTypedStructure and implements
Map, but I would really like to extend ProxyMap as well. The only obvious
design change is to encapsulate a TypeEnforcer or something and change the
extension.
In the end, the ProxyMap/ProxyList etc bit is less important than making
sure that the user of a class can decide whether to use a
HashMap/TreeMap/Other depending on the situation. One of the reasons
against this is that it allows the user to make a HashMap, tell the class
to use said HashMap, and then change the HashMap without going via the
class, but that's a good thing I think :) Allowing it anyway. Another is
that the initial Map/List may have contents already, so the class has to
decide how to deal with that.
Anyways, my proposed code for you to do your Ordered-by-insertion-map
would be:
HashMap hashmap = new HashMapAdaptor( new OrderedMap( new HashMap() ) );
I don't know how ugly that looks to you, if we say that OrderedMap is
FIFO, then FILO could be done as:
HashMap hashmap = new HashmapAdaptor( new ReversedMap( new OrderedMap( new
HashMap() ) ) );
Lastly, I'll attach a ListMap I have which is Yet Another Ordered Map.
Never know if it will be of any use.
Bay
RE: [Collections] Insertion Ordered Map
Posted by Lavandowska <fl...@yahoo.com>.
--- bayard@generationjava.com wrote:
> The first is just a passing mention of SequencedHashMap, from the
> Commons.Collections package, it appears to be a solution to some of
SequencedHashMap fails in that the Set it returns for keySet does not
maintain insertion order (believe me, I've tried it).
> 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,
I'm not sure if your suggestion would fit or not, but my particular
concern is a case where a third-party piece of software requires a
HashMap, but I want to use one that maintains insertion order (not
something currently supported) rather than random or Natural ordering.
If your ProxyMap solution can provide for both these cases (can be
recognized as a HashMap and supports "arbitrary ordering") I would
cheer the flexibility you propose.
Lance
__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [Collections] Insertion Ordered Map
Posted by ba...@generationjava.com.
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.
Bay
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) {
> entry.next = sentinel;
> entry.prev = sentinel.prev;
> sentinel.prev.next = 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.
> http://careers.yahoo.com
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [Collections] Insertion Ordered Map
Posted by Lavandowska <fl...@yahoo.com>.
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) {
entry.next = sentinel;
entry.prev = sentinel.prev;
sentinel.prev.next = 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.
http://careers.yahoo.com
RE: [Collections] Insertion Ordered Map
Posted by Michael Smith <mi...@iammichael.org>.
> -----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