commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Smith" <mich...@iammichael.org>
Subject [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Date Sun, 10 Feb 2002 05:53:29 GMT
The patch is essentially a complete rewrite of the SequencedHashMap
class and
fixes the following problems:

 - Adding and removing from the map is O(n) because the linked list
needs to be
traversed to find the object to remove (when adding, the object needs to
be
removed so it can be readded at the front as the most recently used).
There's
been recent discussion on the commons list about a LRU/MRU thing that is
implemented using a linked list/hashtable combination that had similar
performance problems.  This class demonstrates a manner in which the
O(n)
performance of using the LinkedList can be avoided by implementing a
custom
linked list in the map entries themselves.

 - The sets and collections returned by keySet(), values(), and
entrySet() are
not properly backed by the map (in violation of the java.util.Map
contract).

 - Adds "first" and "last" methods for more effiecient mechanisms to
retrieve
the first and last keys, values, and entries of the sequence.

 - Implemented putAll so that we can definitively specify the order in
which
the map's entries are added to the sequenced hash map.

 - Added a bunch of documentation

 - Fixed bug in my last version (containsValue always returned false).

 - Fixed license to specify "Commons" rather than "Turbine", changed
copyright
years.


Regards,
michael

Mime
View raw message