commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "James Strachan" <>
Subject [collections] Re: MultiHashMap
Date Tue, 16 Apr 2002 04:21:53 GMT
Hi Brian

Sorry for the late response; still catching up on mail after a vacation. I
thought I'd CC the list to see if anyone had any thoughts...

----- Original Message -----
From: "Brian Runk" <>
> Hello James-
> I got your email address from the HashMultiMap API docs. I have an idea
> regarding an alternative implementation of MultiMap. Basically
> internally you'd have a Map member and a doubly linked list (but not
> java.util.LinkedList, you have to build your own). You then have a
> MapEntry class which is the value in the Map. MapEntry has a head, tail,
> and modCount members. head and tail point to the specific nodes in the
> list where elements for a specific key start and end. get() returns a
> failsafe iterator (that uses modCount to be fail safe) that is a view
> into the values in the linked list for the specified key (and also
> decodes the node value). Basically looks like this:
> Map                List
> key -> MapEntry +-> Node
>           head --+    prev --> ...
>           tail --+    next ---+
>           modCnt |    value   |
>                  |            |
>                  +-> Node <---+
>                       next --> ...
>                       prev --> ...
>                       value
> Not sure if I explained it well. Does that make sense? I think this will
> be more efficient memory wise in the case where most keys do not have
> multiple values. I'm not sure about speedwise, possibly slower on
> average insert for large value sets with many multi-value keys, probably
> faster on initial insert. I'm interested to find out though.
> Some questions:
> Obviously, my idea of returning an Iterator instead of a Collection does
> not fit into the description in the MultiMap class docs. Is the MultiMap
> interface intended use carved in stone (i.e. does this prevent this idea
> from being a MultiMap implementation)? I'm not sure about the idea of
> being able to directly manipulate the Map through the result of get() as
> is possible with the current implementation. What was the reason for
> that? My thought is for the returned Iterators to be read only views and
> changes to the map go through the map api. But it could pretty easily
> support remove() and add() from the (List)Iterator interface if we
> wanted to go that route. Alternatively, a read only Collection
> implementation could be returned.
> If this is something that sounds interesting to you and might be
> supportable in a future release of Collections, we would be willing to
> work with you on it or even write the code and see what you think.
> Your feedback is welcome. I look forward to hearing from you.
> Thanks for your time,
> -Brian Runk


Do You Yahoo!?
Get your free address at

To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message