commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Smith" <mich...@iammichael.org>
Subject RE: Silly Question
Date Thu, 24 Jan 2002 12:54:24 GMT
> -----Original Message-----
> From: Scott Sanders [mailto:ssanders@nextance.com]
> Sent: Thursday, January 24, 2002 12:01 AM
> To: commons-dev@jakarta.apache.org
> Subject: Silly Question
>
> In the sanbox in utils, there exists a SequencedHashtable.
>
> Other than the obvious, why is this not in commons-collections?
> Are we saying that something has to implement/extend the
> Collections API
> to be included?

There already is a SequencedHashtable in collections (as
SequencedHashMap).  But since you ask about extending the Collections
API, here's a (slightly modified) submission from November 13, 2001
where I patched SequencedHashMap to implement Map correctly.

regards,
michael

-------

The implementation of SequencedHashMap suffers from problems:  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 attached it to this
message.  Since there is a preexisting class, I've kept it
backwards-compatible by adding implementations of all the existing
methods (And retained it inheriting from HashMap, even though it should
inherit from AbstractMap).

To simplify the commit of the rewriten SequencedHashMap, I have also
attached a diff.



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

Mime
View raw message