> -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED]]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 methods. To simplify the commit of the rewriten SequencedHashMap, I have also attached a diff against the current CVS version. regards, michael 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]>
