You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Stephen Colebourne <sc...@btopenworld.com> on 2004/04/11 01:09:30 UTC
[collections] MultiKeyMap
I am currently developing a MultiKeyMap for [collections]. This class
operates like a Map, but has multiple keys instead of one.
get(key1, key2, key3)
put(key1, key2, key3, value)
(choice of 2-5 keys as per MultiKey)
I have made the class implement Map, however no-one will want to ever use it
as a Map (ie. hold it in a Map variable). So, I could
1) Place the class in the map subpackage, because its map-like
2) Place the class in the main package, alongside MultiMap (the multi value
map)
3) Create a new subpackage, together with a new interface
#3 seems like a lot of work, especially as we have little evidence of what
the interface really needs to be. #1 would make sense, except that every
other class in the map subpackage truly is a map. So I'm tending towards #2,
to join ArrayStack, BeanMap and MultiHashMap as the weird collections ;-)
Any other views?
Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] MultiKeyMap
Posted by "matthew.hawthorne" <ma...@apache.org>.
Michael Heuer wrote:
> Might you also be able to use an unmutable MultiKey for storage in the
> hashed map and a mutable MultiKey for lookups, with matching equals and
> hashCode implementations?
>
> void put(Obj a, Obj b, ...) {
> map.put(new MultiKey(a, b, ..));
> }
>
> private MutableMultiKey lookupKey = new MutableMultiKey();
>
> Object get(Obj a, Obj b, ...) {
> lookupKey.setKeys(a, b, ..));
> return map.get(lookupKey);
> }
>
> I have something that works this way lying around somewhere.
I'm not 100% sure, but I don't think this is thread safe, since multiple
threads may be calling the get method at the same time and thus
modifying the lookupKey instance var.
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] MultiKeyMap
Posted by Phil Steitz <ph...@steitz.com>.
Stephen Colebourne wrote:
>>Why do you we need this when we have MultiKeys available -- i.e., what do
>>you gain by using multiple keys instead of a single MultiKey? Sorry if I
>>am being dense here, but I don't understand what disaggregation of the
>>MultiKey is buying us.
>
>
> Me not being clear. To use MultiKey as keys in the map has an overhead. For
> every get/contains/remove you have to create a new MultiKey object which is
> then thrown away once the operation is complete. This was a performance
> hotspot in some recent testing I did.
>
> With MultiKeyMap the get/containsKey/remove operations do not create the
> temporary MultiKey object, they query the data directly. put still creates
> the MultiKey as that is what is actually stored in the hashed map.
Interesting. So you somehow have optimized the comparison operation to
see if e.g., <key1, key2> "equals" a MultiKey that you have in the KeySet.
Does this create a dependency on the internals of MultiKey that we need
to worry about?
In answer to your original question, I guess I would agree with the "odd
collections" package placement; though if you look at it the right way
(take off glasses, so keys merge into a MultiKey) it really is a map ;-)
In fact, if you limit the interface to just take Object[] arrays as keys,
it is just a (directly implemented, not decorated) TypedMap. I assume the
<key1, key2, key3> stuff here and in MultiKey is also for optimization.
Phil
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] MultiKeyMap
Posted by Michael Heuer <he...@acm.org>.
On Sun, 11 Apr 2004, Stephen Colebourne wrote:
> > Why do you we need this when we have MultiKeys available -- i.e., what do
> > you gain by using multiple keys instead of a single MultiKey? Sorry if I
> > am being dense here, but I don't understand what disaggregation of the
> > MultiKey is buying us.
>
> Me not being clear. To use MultiKey as keys in the map has an overhead. For
> every get/contains/remove you have to create a new MultiKey object which is
> then thrown away once the operation is complete. This was a performance
> hotspot in some recent testing I did.
>
> With MultiKeyMap the get/containsKey/remove operations do not create the
> temporary MultiKey object, they query the data directly. put still creates
> the MultiKey as that is what is actually stored in the hashed map.
Might you also be able to use an unmutable MultiKey for storage in the
hashed map and a mutable MultiKey for lookups, with matching equals and
hashCode implementations?
void put(Obj a, Obj b, ...) {
map.put(new MultiKey(a, b, ..));
}
private MutableMultiKey lookupKey = new MutableMultiKey();
Object get(Obj a, Obj b, ...) {
lookupKey.setKeys(a, b, ..));
return map.get(lookupKey);
}
I have something that works this way lying around somewhere.
michael
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] MultiKeyMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
> Why do you we need this when we have MultiKeys available -- i.e., what do
> you gain by using multiple keys instead of a single MultiKey? Sorry if I
> am being dense here, but I don't understand what disaggregation of the
> MultiKey is buying us.
Me not being clear. To use MultiKey as keys in the map has an overhead. For
every get/contains/remove you have to create a new MultiKey object which is
then thrown away once the operation is complete. This was a performance
hotspot in some recent testing I did.
With MultiKeyMap the get/containsKey/remove operations do not create the
temporary MultiKey object, they query the data directly. put still creates
the MultiKey as that is what is actually stored in the hashed map.
Stephen
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] MultiKeyMap
Posted by Phil Steitz <ph...@steitz.com>.
Stephen Colebourne wrote:
> I am currently developing a MultiKeyMap for [collections]. This class
> operates like a Map, but has multiple keys instead of one.
> get(key1, key2, key3)
> put(key1, key2, key3, value)
> (choice of 2-5 keys as per MultiKey)
>
> I have made the class implement Map, however no-one will want to ever use it
> as a Map (ie. hold it in a Map variable). So, I could
>
> 1) Place the class in the map subpackage, because its map-like
>
> 2) Place the class in the main package, alongside MultiMap (the multi value
> map)
>
> 3) Create a new subpackage, together with a new interface
>
> #3 seems like a lot of work, especially as we have little evidence of what
> the interface really needs to be. #1 would make sense, except that every
> other class in the map subpackage truly is a map. So I'm tending towards #2,
> to join ArrayStack, BeanMap and MultiHashMap as the weird collections ;-)
>
> Any other views?
Why do you we need this when we have MultiKeys available -- i.e., what do
you gain by using multiple keys instead of a single MultiKey? Sorry if I
am being dense here, but I don't understand what disaggregation of the
MultiKey is buying us.
Phil
>
> Stephen
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] MultiKeyMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
I have refactored MultiKeyMap to be a decorator instead of an
implementation. This gives many more possibilities without needing to code
extra classes (saving space ;-).
This decorator is different however in that it doesn't use the public Map
API. Instead it uses the protected parts of the AbstractHashedMap. Thus
MultiKeyMap cannot decorate a HashMap, but can decorate a HashedMap.
Even so, it now means that you can have an LRU, Linked or Reference
MultiKeyMap without any additional effort.
Anyone object to decorating in this way?
Stephen
----- Original Message -----
From: "Stephen Colebourne" <sc...@btopenworld.com>
> I have now checked in the map and test into the map subpackage.
>
> After further thought, it would be nice to create a new subpackage for
this
> class, and for MultiValueMaps. It requires a new interface for
MultiValueMap
> and MultiKeyMap, plus a rewrite of the MultiHashMap implementation, moving
> MultiKeyMap, and creating synchronized decorators. This might take some
> time, but is the correct solution :-0 Its needed because MultiKeyMap will
> often need to be synchronized.
>
> Stephen
>
> ----- Original Message -----
> From: "Stephen Colebourne" <sc...@btopenworld.com>
> > I am currently developing a MultiKeyMap for [collections]. This class
> > operates like a Map, but has multiple keys instead of one.
> > get(key1, key2, key3)
> > put(key1, key2, key3, value)
> > (choice of 2-5 keys as per MultiKey)
> >
> > I have made the class implement Map, however no-one will want to ever
use
> it
> > as a Map (ie. hold it in a Map variable). So, I could
> >
> > 1) Place the class in the map subpackage, because its map-like
> >
> > 2) Place the class in the main package, alongside MultiMap (the multi
> value
> > map)
> >
> > 3) Create a new subpackage, together with a new interface
> >
> > #3 seems like a lot of work, especially as we have little evidence of
what
> > the interface really needs to be. #1 would make sense, except that every
> > other class in the map subpackage truly is a map. So I'm tending towards
> #2,
> > to join ArrayStack, BeanMap and MultiHashMap as the weird collections
;-)
> >
> > Any other views?
> >
> > Stephen
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] MultiKeyMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
I have now checked in the map and test into the map subpackage.
After further thought, it would be nice to create a new subpackage for this
class, and for MultiValueMaps. It requires a new interface for MultiValueMap
and MultiKeyMap, plus a rewrite of the MultiHashMap implementation, moving
MultiKeyMap, and creating synchronized decorators. This might take some
time, but is the correct solution :-0 Its needed because MultiKeyMap will
often need to be synchronized.
Stephen
----- Original Message -----
From: "Stephen Colebourne" <sc...@btopenworld.com>
> I am currently developing a MultiKeyMap for [collections]. This class
> operates like a Map, but has multiple keys instead of one.
> get(key1, key2, key3)
> put(key1, key2, key3, value)
> (choice of 2-5 keys as per MultiKey)
>
> I have made the class implement Map, however no-one will want to ever use
it
> as a Map (ie. hold it in a Map variable). So, I could
>
> 1) Place the class in the map subpackage, because its map-like
>
> 2) Place the class in the main package, alongside MultiMap (the multi
value
> map)
>
> 3) Create a new subpackage, together with a new interface
>
> #3 seems like a lot of work, especially as we have little evidence of what
> the interface really needs to be. #1 would make sense, except that every
> other class in the map subpackage truly is a map. So I'm tending towards
#2,
> to join ArrayStack, BeanMap and MultiHashMap as the weird collections ;-)
>
> Any other views?
>
> Stephen
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org