> -----Original Message----- > From: Scott Sanders [mailto:[EMAIL PROTECTED]] > Sent: Thursday, January 24, 2002 12:01 AM > To: [EMAIL PROTECTED] > 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
tests.patch
Description: Binary data
test-results.pre
Description: Binary data
sequencedhashmap.patch
Description: Binary data
SequencedHashMap.java
Description: Binary data
test-results.post
Description: Binary data
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
