You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Scott Sanders <ss...@nextance.com> on 2002/01/24 06:00:56 UTC
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?
The PROPOSAL.html states that collections was intended for ADTs, not
just Collections API stuff.
So can we say that anything collectionesque (ie, hastables, vectors,
etc) should also be included?
I think that commons-collections is small enough to warrant the
inclusion of this SequencedHashtable, and possibly others, as I find
them.
I will start adding these to commons-collections. Can I get some
feedback, maybe even some +1s?
Scott Sanders
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: Silly Question
Posted by Paulo Gaspar <pa...@krankikom.de>.
BTW, the simplest (and possibly most efficient) LRU cache I found is at
Tomcat 3.3 on:
org.apache.tomcat.util.collections.LRUCache
I think it might need a couple of adjustments but it is great for simple
stuff. (Be aware that is just in-memory and very simplistic.)
Have fun,
Paulo Gaspar
http://www.krankikom.de
http://www.ruhronline.de
> -----Original Message-----
> From: Janek Bogucki [mailto:yan@studylink.com]
> Sent: Thursday, January 24, 2002 11:08 AM
> To: Jakarta Commons Developers List
> Subject: Re: Silly Question
>
>
> It's already in commons-collections 1.1-dev as SequencedHashMap, and very
> useful it is too :)
>
> -Janek
>
> > From: "Scott Sanders" <ss...@nextance.com>
> > Reply-To: "Jakarta Commons Developers List"
> <co...@jakarta.apache.org>
> > Date: Wed, 23 Jan 2002 21:00:56 -0800
> > To: <co...@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?
> >
> > The PROPOSAL.html states that collections was intended for ADTs, not
> > just Collections API stuff.
> >
> > So can we say that anything collectionesque (ie, hastables, vectors,
> > etc) should also be included?
> >
> > I think that commons-collections is small enough to warrant the
> > inclusion of this SequencedHashtable, and possibly others, as I find
> > them.
> >
> > I will start adding these to commons-collections. Can I get some
> > feedback, maybe even some +1s?
> >
> > Scott Sanders
> >
> > --
> > To unsubscribe, e-mail:
> <ma...@jakarta.apache.org>
> > For additional commands, e-mail:
> <ma...@jakarta.apache.org>
> >
>
>
> --
> To unsubscribe, e-mail:
> <ma...@jakarta.apache.org>
> For additional commands, e-mail:
> <ma...@jakarta.apache.org>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: Silly Question
Posted by Janek Bogucki <ya...@studylink.com>.
It's already in commons-collections 1.1-dev as SequencedHashMap, and very
useful it is too :)
-Janek
> From: "Scott Sanders" <ss...@nextance.com>
> Reply-To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Date: Wed, 23 Jan 2002 21:00:56 -0800
> To: <co...@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?
>
> The PROPOSAL.html states that collections was intended for ADTs, not
> just Collections API stuff.
>
> So can we say that anything collectionesque (ie, hastables, vectors,
> etc) should also be included?
>
> I think that commons-collections is small enough to warrant the
> inclusion of this SequencedHashtable, and possibly others, as I find
> them.
>
> I will start adding these to commons-collections. Can I get some
> feedback, maybe even some +1s?
>
> Scott Sanders
>
> --
> To unsubscribe, e-mail: <ma...@jakarta.apache.org>
> For additional commands, e-mail: <ma...@jakarta.apache.org>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: Silly Question
Posted by Michael Smith <mi...@iammichael.org>.
> -----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