TreeSet and HashSet
 

Hello

There is a very useful functionality, that I think should be implemented in
TreeSet nad HashSet
that is the method: Object get(Object o).
The method should return the same object from colletion as the parameter
object.
In TreeSet complexity would be log(n), in HashSet would be constant.
With lack of this functionality one must implement collections on maps, so
the unnecessary and more complex type will be used.

What do you think about this?

Regards
Marcin

Re: New functionality in the Set<T> interface.(was: TreeSet and HashSet)
 

On Feb 2, 11:40 am, "Marcin" <e...@email.com> wrote:
> Hello
>
> There is a very useful functionality, that I think should be implemented in
> TreeSet nad HashSet
> that is the method: Object get(Object o).
> The method should return the same object from colletion as the parameter
> object.
> In TreeSet complexity would be log(n), in HashSet would be constant.
> With lack of this functionality one must implement collections on maps, so
> the unnecessary and more complex type will be used.
>
> What do you think about this?
>
> Regards
> Marcin
What would be the use case of this?
would it return null if the set didn't contain the object o?
Also, this should be in the Set interface, if anywhere.

Whats so hard about using boolean contains(Object o)?

Or, are you basically using a Set<SomeTypeThatHasBothKeyAndValue>?
In that case, you SHOULD use a Map. Thats the whole point on maps, is
that you can key on the value.

If you want to have an AssociativeSet<T>, thats something a little
different than a standard Set

class AssociativeSet<T> implements Set<T> {
final Map<T, T> associations;
public AssociativeSet() {
associations = new HashMat<T, T>();
}

public AssociativeSet(Map<T, T> backingMap) {
associations = backingMap;
}

public T get(T o) {
return associations.get(o);
}
// TODO: delegate most of the Set methods to associations keySet
method.
}

Re: TreeSet and HashSet
 

On Feb 2, 11:40 am, "Marcin" <e...@email.com> wrote:
> Hello
>
> There is a very useful functionality, that I think should be implemented in
> TreeSet nad HashSet
> that is the method: Object get(Object o).
> The method should return the same object from colletion as the parameter
> object.
> In TreeSet complexity would be log(n), in HashSet would be constant.
> With lack of this functionality one must implement collections on maps, so
> the unnecessary and more complex type will be used.
>
> What do you think about this?
>
> Regards
> Marcin

Oh, almost forgot to mention. HashSet is backed by a HashMap, so
you're using a map anyway. Why not just use a Map if thats what you
really want?

Re: New functionality in the Set<T> interface.(was: TreeSet and HashSet)
 

Uzytkownik "Daniel Pitts" <googlegroupie@coloraura.com> napisal w wiadomosci
news:1170446407.708622.99960@v45g2000cwv.googlegro ups.com...
> On Feb 2, 11:40 am, "Marcin" <e...@email.com> wrote:
>> Hello
>>
>> There is a very useful functionality, that I think should be implemented
>> in
>> TreeSet nad HashSet
>> that is the method: Object get(Object o).
>> The method should return the same object from colletion as the parameter
>> object.
>> In TreeSet complexity would be log(n), in HashSet would be constant.
>> With lack of this functionality one must implement collections on maps,
>> so
>> the unnecessary and more complex type will be used.
>>
>> What do you think about this?
>>
>> Regards
>> Marcin
> What would be the use case of this?
> would it return null if the set didn't contain the object o?
> Also, this should be in the Set interface, if anywhere.
>
> Whats so hard about using boolean contains(Object o)?
>
contains does not return object only the information about exisiting of this
object.

> Or, are you basically using a Set<SomeTypeThatHasBothKeyAndValue>?
> In that case, you SHOULD use a Map. Thats the whole point on maps, is
> that you can key on the value.
We can said that almost every class that have implemented the method equals
have both keys and values, where the keys are fields used in the method
equals. But we do not use maps always.
Maps concept should be hide from developer where it is not needed. Maps
concept does not exist in this case directly, and should be ommited in my
opinion. The sets concept is clearer.

>Oh, almost forgot to mention. HashSet is backed by a HashMap, so
>you're using a map anyway. Why not just use a Map if thats what you
>really want?

When you want to use Maps instead of sets you should create the other class
for key objects, when you are dealing with very huge data, space consumed by
key object could be very big. And we have redundant data. The solution like
dividing class into two class: key class, and value class breaks the class
concept. Why used more complicated data type, when adding get method is not
hard, because of sets implementation based on maps?

Marcin

Re: New functionality in the Set<T> interface.(was: TreeSet and HashSet)
 

Marcin wrote On 02/02/07 16:05,:
> [...]
>>Oh, almost forgot to mention. HashSet is backed by a HashMap, so
>>you're using a map anyway. Why not just use a Map if thats what you
>>really want?
>
>
> When you want to use Maps instead of sets you should create the other class
> for key objects, when you are dealing with very huge data, space consumed by
> key object could be very big. [...]

Note that a Map, like any Collection, only stores
references and not actual object instances. If you create
an object that has a megabyte key:

class Thing {
private byte[] key = new byte[1024*1024];
...
}

.... and insert it in a Map as both key and value:

Thing thing = new Thing();
map.put(thing, thing);

.... there's still only one copy of the megabyte key
floating around.

--
Eric.Sosman@sun.com

Re: New functionality in the Set<T> interface.(was: TreeSet and HashSet)
 

On Feb 2, 1:05 pm, "Marcin" <e...@email.com> wrote:
> Uzytkownik "Daniel Pitts" <googlegrou...@coloraura.com> napisal w wiadomoscinews:1170446407.708622.99960@v45g2000cwv .googlegroups.com...
>
> > On Feb 2, 11:40 am, "Marcin" <e...@email.com> wrote:
> >> Hello
>
> >> There is a very useful functionality, that I think should be implemented
> >> in
> >> TreeSet nad HashSet
> >> that is the method: Object get(Object o).
> >> The method should return the same object from colletion as the parameter
> >> object.
> >> In TreeSet complexity would be log(n), in HashSet would be constant.
> >> With lack of this functionality one must implement collections on maps,
> >> so
> >> the unnecessary and more complex type will be used.
>
> >> What do you think about this?
>
> >> Regards
> >> Marcin
> > What would be the use case of this?
> > would it return null if the set didn't contain the object o?
> > Also, this should be in the Set interface, if anywhere.
>
> > Whats so hard about using boolean contains(Object o)?
>
> contains does not return object only the information about exisiting of this
> object.
>
> > Or, are you basically using a Set<SomeTypeThatHasBothKeyAndValue>?
> > In that case, you SHOULD use a Map. Thats the whole point on maps, is
> > that you can key on the value.
>
> We can said that almost every class that have implemented the method equals
> have both keys and values, where the keys are fields used in the method
> equals. But we do not use maps always.
> Maps concept should be hide from developer where it is not needed. Maps
> concept does not exist in this case directly, and should be ommited in my
> opinion. The sets concept is clearer.
>
> >Oh, almost forgot to mention. HashSet is backed by a HashMap, so
> >you're using a map anyway. Why not just use a Map if thats what you
> >really want?
>
> When you want to use Maps instead of sets you should create the other class
> for key objects, when you are dealing with very huge data, space consumed by
> key object could be very big. And we have redundant data. The solution like
> dividing class into two class: key class, and value class breaks the class
> concept. Why used more complicated data type, when adding get method is not
> hard, because of sets implementation based on maps?
>
> Marcin
For one thing, adding a "get" method is likely to break any existing
implementations of the "Set" interface, including third-party code.

Secondly, it is perfectly okay to have a Map<T, T> for your particular
usecase, which is "query-by-example". And, low-and-behold actually has
a T get(Object o) method!

a Map isn't more complicated than a Set to use. I also gave you code
that will help you extends Set the way you want to, even though I
disagree with the need.

Re: New functionality in the Set<T> interface.(was: TreeSet and HashSet)
 

> Note that a Map, like any Collection, only stores
> references and not actual object instances. If you create
> an object that has a megabyte key:
>
> class Thing {
> private byte[] key = new byte[1024*1024];
> ...
> }
>
> ... and insert it in a Map as both key and value:
>
> Thing thing = new Thing();
> map.put(thing, thing);
>
> ... there's still only one copy of the megabyte key
> floating around.

When we want to put new key objects with chosen fields the problem exists
with unwrapped type like
char, int, long, float, double, etc. But in your solution you're right,
there is only need to store references. But i'm not sure if this solution is
safe, because we have references to the same important data from two sets
keySet and valueSet, so we have to be careful with them. Mapping object to
the same object does not have a big sense, for example what about the method
put when the key already exist, after this operation we have a map where key
and value are different, so we have inconsistent data. I'm not sure is
this concept is perfect. For example in the implementation of sets java
language developers were used mapping from object to dummy object instead of
object to the same object, maybe there were some important reasons?

Marcin

Re: TreeSet and HashSet
 

>There is a very useful functionality, that I think should be implemented in
>TreeSet nad HashSet that is the method: Object get(Object o).

I echo what others have said: if anywhere, it should go on the Set interface.
I'd call it a convenience, but probably not worth a non-backward-compatible
change (all implementations and subclasses now break).

>The method should return the same object from colletion as the parameter
>object.

Well, no. If it was sane, it would return the object in the collection which
is equal() to the parameter object (or null). This wouldn't necessarily be
the same object as the parameter.

This is important because one use of this would be to normalize equivalent
immutable objects to avoid a bunch of unnecessary copies that are equal() but
not ==. Currently, you do this with a map whose keys and values are the same.

If you're willing to live with getting back the parameter object instead of
the object in the collection, you can do
set.contains(o) ? o : null
anyplace you'd want a get() method, but I can't think of a use for that.

>With lack of this functionality one must implement collections on maps, so
>the unnecessary and more complex type will be used.

The implementations in java.util use maps, so there's not much reason for you
not to do the same.
--
Mark Rafn dagon@dagon.net <http://www.dagon.net/>

Re: TreeSet and HashSet
 

U¿ytkownik "Mark Rafn" <dagon@dagon.net> napisa³ w wiadomo¶ci
news:8dvc94-j4c.ln1@hydra.dagon.net...
> >There is a very useful functionality, that I think should be implemented
> >in
>>TreeSet nad HashSet that is the method: Object get(Object o).
>
> I echo what others have said: if anywhere, it should go on the Set
> interface.
> I'd call it a convenience, but probably not worth a
> non-backward-compatible
> change (all implementations and subclasses now break).
>
What about subinterface of set?

>>The method should return the same object from colletion as the parameter
>>object.
>
> Well, no. If it was sane, it would return the object in the collection
> which
> is equal() to the parameter object (or null). This wouldn't necessarily
> be
> the same object as the parameter.

I mean "equal object", not the same.

> This is important because one use of this would be to normalize equivalent
> immutable objects to avoid a bunch of unnecessary copies that are equal()
> but
> not ==. Currently, you do this with a map whose keys and values are the
> same.
>
> If you're willing to live with getting back the parameter object instead
> of
> the object in the collection, you can do
> set.contains(o) ? o : null
> anyplace you'd want a get() method, but I can't think of a use for that.
>
>>With lack of this functionality one must implement collections on maps, so
>>the unnecessary and more complex type will be used.
>
> The implementations in java.util use maps, so there's not much reason for
> you
> not to do the same.

You write a code, and operate on sets. But after some time there is a need
to update some data, and you have a set of new objects, that have the same
keys as existing objects in the collection. You can do this in linear time
by using iterator, so you don't need maps to have get functionality. The
problem is with linear time, it is too much. So in order to achieve
logarithmic time, you must change many lines of codes to use maps, even
then,
you don't need maps, you need only the better time to get object. The all
changes is because of lack of get method.

So when you write a code using sets you must think if you will need get
method for example after some years. You can't use sets anymore because you
are not sure about this.
So the sets are useless in most cases, because the changes to maps in the
feature are expensive tasks. And even when you operate with sets in your
code specification, you implement all things with maps.

Marcin

Re: New functionality in the Set<T> interface.(was: TreeSet and HashSet)
 

Marcin wrote:
>> Note that a Map, like any Collection, only stores
>> references and not actual object instances. If you create
>> an object that has a megabyte key:
>>
>> class Thing {
>> private byte[] key = new byte[1024*1024];
>> ...
>> }
>>
>> ... and insert it in a Map as both key and value:
>>
>> Thing thing = new Thing();
>> map.put(thing, thing);
>>
>> ... there's still only one copy of the megabyte key
>> floating around.
>
> When we want to put new key objects with chosen fields the problem exists
> with unwrapped type like
> char, int, long, float, double, etc.

... but you wrote about "very huge data, space consumed by
key object could be very big." If the key is a wrapped primitive,
it isn't "very big."

> But in your solution you're right,
> there is only need to store references. But i'm not sure if this solution is
> safe, because we have references to the same important data from two sets
> keySet and valueSet, so we have to be careful with them. Mapping object to
> the same object does not have a big sense, for example what about the method
> put when the key already exist, after this operation we have a map where key
> and value are different, so we have inconsistent data.

But what do you provide as the second argument to put()? If
you always write put(obj,obj) there will never be any kind of
mismatch. Yes, sometimes put(obj,obj) might replace an existing
oldobj->oldobj mapping -- but if you didn't want that to happen,
you shouldn't have called put() in the first place!

As for the set of keys and the set (collection, really) of
values, yes: you must "be careful with them." But this is no
different from being "careful" with the members of a Set! If you
add a mutable object to a Set and then mutate it in a way that
violates the Set's requirements, you're already in trouble. Using
a Map doesn't make things worse in any way I can think of.

> I'm not sure is
> this concept is perfect. For example in the implementation of sets java
> language developers were used mapping from object to dummy object instead of
> object to the same object, maybe there were some important reasons?

Maybe. It might be nothing more than a convenience: using a
special object as the "value" makes it easy to allow null as an
actual member of the set.

--
Eric Sosman
esosman@acm-dot-org.invalid