commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Smith" <>
Subject [PATCH] RE: [Collections] Insertion Ordered Map
Date Tue, 13 Nov 2001 07:31:30 GMT
> -----Original Message-----
> From:
> []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

To simplify the commit of the rewriten SequencedHashMap, I have also
attached a diff against the current CVS version.


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 - 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. - results of the test cases after changing

View raw message