Can I compare references (in a sense of compareTo method)?

C

chucky

When testing two objects for equality (with == operator), the
references are compared. But it is not allowed to compare the objects
(references) with <, <=, >, >= operators.

Is it possible somehow to get the address of an object and then
compare it?

What I want to do is to have each instance of my class unique, so that
two objects are equal only if they are the same object. This is easy,
I can make equals method to compare references. But I would like to
use these objects in TreeSet/TreeMap and therefore implement the
compareTo method in a way that would be consistent with respect to
equals.

I can think of one workaround: the class having an additional integer
field id and creating the instances with a synchronized factory
method. But just want to know if it is possible without that extra
field.

Thanks for replies!

Tomas
 
D

Daniel Pitts

When testing two objects for equality (with == operator), the
references are compared. But it is not allowed to compare the objects
(references) with <, <=, >, >= operators.

Is it possible somehow to get the address of an object and then
compare it?

What I want to do is to have each instance of my class unique, so that
two objects are equal only if they are the same object. This is easy,
I can make equals method to compare references. But I would like to
use these objects in TreeSet/TreeMap and therefore implement the
compareTo method in a way that would be consistent with respect to
equals.

I can think of one workaround: the class having an additional integer
field id and creating the instances with a synchronized factory
method. But just want to know if it is possible without that extra
field.

Thanks for replies!

Tomas

See System.identityHashCode(object)

Now, the questions remains, if they don't have inherent order, why use
them in a TreeSet or TreeMap? Why not a standard HashSet/HashMap?
The main benefit of Tree* is that it maintains the order for you.
 
K

Knute Johnson

chucky said:
When testing two objects for equality (with == operator), the
references are compared. But it is not allowed to compare the objects
(references) with <, <=, >, >= operators.

Is it possible somehow to get the address of an object and then
compare it?

What I want to do is to have each instance of my class unique, so that
two objects are equal only if they are the same object. This is easy,
I can make equals method to compare references. But I would like to
use these objects in TreeSet/TreeMap and therefore implement the
compareTo method in a way that would be consistent with respect to
equals.

I can think of one workaround: the class having an additional integer
field id and creating the instances with a synchronized factory
method. But just want to know if it is possible without that extra
field.

Thanks for replies!

Tomas

Do you not have access to the docs? It has nothing to do with == or the
address of the object. You need to look at TreeMap and Comparator.

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

A Red-Black tree based NavigableMap implementation. The map is sorted
according to the natural ordering of its keys, or by a Comparator
provided at map creation time, depending on which constructor is used.
 
D

Daniel Pitts

Do you not have access to the docs? It has nothing to do with == or the
address of the object. You need to look at TreeMap and Comparator.

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

A Red-Black tree based NavigableMap implementation. The map is sorted
according to the natural ordering of its keys, or by a Comparator
provided at map creation time, depending on which constructor is used.

Whether or not the OP reads the docs, you should try reading the post
before you reply.

He has an object that he wants its equals identity to match its ==
identity. He also wants to use said object (for some bewildering
reason) in Tree based collections.

He's probably misguided in that approach, and I've tried to suggest
alternatives to him.
 
K

Knute Johnson

Daniel said:
Whether or not the OP reads the docs, you should try reading the post
before you reply.

I did. He wants to compare unique objects with their references. And
for some unknown reason he wants to order them in a TreeMap.
He has an object that he wants its equals identity to match its ==
identity. He also wants to use said object (for some bewildering
reason) in Tree based collections.

That is why I suggested (and supplied the salient part) he read the
docs. He obviously doesn't know what a TreeMap is for.
He's probably misguided in that approach, and I've tried to suggest
alternatives to him.

I think so too. And your suggestion would have been excellent had he
not had a unique set of objects. A list will do just fine.

In any case == isn't going to be the solution to whatever his problem
is. I'll even put five bucks behind that statement.

I think his real problem is in not describing the problem he is
attempting to solve but just his method for solving it. This is a
common problem that posters on this list have. I know I've been there.
It can be very difficult to provide a concise problem description that
will get you to where you need to be.
 
D

Daniel Pitts

I did. He wants to compare unique objects with their references. And
for some unknown reason he wants to order them in a TreeMap.


That is why I suggested (and supplied the salient part) he read the
docs. He obviously doesn't know what a TreeMap is for.


I think so too. And your suggestion would have been excellent had he
not had a unique set of objects. A list will do just fine.

In any case == isn't going to be the solution to whatever his problem
is. I'll even put five bucks behind that statement.

I think his real problem is in not describing the problem he is
attempting to solve but just his method for solving it. This is a
common problem that posters on this list have. I know I've been there. I think we all have.
It can be very difficult to provide a concise problem description that
will get you to where you need to be.
It's less difficult if you are able to step back from *how* you want
to solve it, and look at *what* you're trying to solve.
 
C

chucky

Thank you guys, seems you have answered my question indirectly --
there is no way to get the address of an object :).

Now, the questions remains, if they don't have inherent order, why use
them in a TreeSet or TreeMap? Why not a standard HashSet/HashMap?
The main benefit of Tree* is that it maintains the order for you.

I don't care about the actual ordering, but I wanted to use Tree*
since I thought it would have smaller memory overhead than Hash*. I
don't care much about logarithmic complexity (which is btw.
guaranteed, while Hash operations don't guarantee constant
complexity), since I want to use it for small collections (<20
elements).

Why is HashSet/HashMap more standard than TreeSet/TreeMap?

T.
 
L

Lasse Reichstein Nielsen

chucky said:
I don't care about the actual ordering, but I wanted to use Tree*
since I thought it would have smaller memory overhead than Hash*.

Not by much. A TreeMap has a node per element with (probably) four or
five references and a boolean, whereas a HashMap has a lookup array of
references and a node per element with three references (a
single-linked list).

....
Why is HashSet/HashMap more standard than TreeSet/TreeMap?

It doesn't require its keys to be Comparable, or have a Comparator.

/L
 
L

Lew

It doesn't require its keys to be Comparable, or have a Comparator.

"Premature optimization is the root of all evil." - Knuth

You are mistaken about "Hash [sic] operations don't guarantee constant
complexity".

This implementation provides constant-time performance for
the basic operations (get and put), assuming the hash function
disperses the elements properly among the buckets.

Whereas
 
C

Chris Smith

Lew said:
You are mistaken about "Hash [sic] operations don't guarantee constant
complexity".

I don't agree with this. If one has chosen a bad hash function for the
particular distribution of objects in use, then some operations on
HashMap will degrade to linear time, which is *far* worse than
logarithmic. The chance of this is very small, but since hash functions
in Java are constant and chosen at build time, it's always feasible for
any type of data in which there are far more possible values of that
data structure than there are hash buckets.

There are techniques for avoiding this: one can randomize hash functions
to get a true probablistic "expected constant time", but Java's has
functions don't do that. (I suppose one could do it, but it would be
quite uncommon). And one can generate perfect hash functions given data
ahead of time, but that's not normally done either. Certainly someone
just saying "use HashMap" can't be interpreted as talking about either
of these techniques; so in practice, HashMap does not guarantee its
amortized constant running time.

Regarding the Knuth quote, it's important to note that from context,
Knuth was talking about "small" inefficiencies; i.e., if this is the
defining characteristic of the problem, then it may be quite worthwhile
to consider in advance if "probably constant, depending on input" or
"always logarithmic" is better.
 
L

Lew

Chris said:
... if this is the
defining characteristic of the problem, then it may be quite worthwhile
to consider in advance if "probably constant, depending on input" or
"always logarithmic" is better.

You are correct. They also have to weigh if "additional complexity introduced
by the need to spuriously define a Comparator" is a worthwhile cost. Perhaps
the effort is better spent writing a good implementation of hashCode() for the
key class.

I'd weigh the costs of possible O(n) response time with odds of what, ten to
the negative umpteenth?, against the cost of difficulties from spurious
algorithmic warts, with near certainty if the program is maintained. For
nearly all problems I predict the mathematical expectation favors HashMap with
a well-designed key hashCode() override, over TreeMap with the additional
maintenance cost of imputing an order.
 
P

Patricia Shanahan

chucky said:
Thank you guys, seems you have answered my question indirectly --
there is no way to get the address of an object :).

It isn't even guaranteed that an object has an address.
I don't care about the actual ordering, but I wanted to use Tree*
since I thought it would have smaller memory overhead than Hash*. I
don't care much about logarithmic complexity (which is btw.
guaranteed, while Hash operations don't guarantee constant
complexity), since I want to use it for small collections (<20
elements).

Why is HashSet/HashMap more standard than TreeSet/TreeMap?

They are both completely standard, but they are different classes with
different purposes. The Tree structures are designed for ordered access,
and you are having to stretch to try to apply them to your unordered
objects.

For very small collections, I would also consider ArrayList.

Patricia
 
D

Daniel Pitts

Thank you guys, seems you have answered my question indirectly --
there is no way to get the address of an object :).



I don't care about the actual ordering, but I wanted to use Tree*
since I thought it would have smaller memory overhead than Hash*. I
don't care much about logarithmic complexity (which is btw.
guaranteed, while Hash operations don't guarantee constant
complexity), since I want to use it for small collections (<20
elements).

Why is HashSet/HashMap more standard than TreeSet/TreeMap?

T.

Hash doesn't have a huge memory overhead, and generally you shouldn't
worry about such things until they become a problem.

If you declare your sets/maps using the interface "Set<MyThing>" and
"Map<MyThing, OtherThing>", then you can switch between different
implementations.

HashSet and HashMap are the default choice, because they are on
average O(1) operations. TreeSet and TreeMap have a very specific
purpose, and that purpose is to guarantee and ordering of elements.
 
C

chucky


As I stated in the title of this topic and in first paragraph of my
original post, I was intrested in comparing the addresses in sense of
ordering. So the page you linked does not answer the question neither
positively nor negatively.

Moreover, it states that "The default hashCode() method uses the 32-
bit internal JVM address of the Object as its hashCode."
But http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode()
says:

"As much as is reasonably practical, the hashCode method defined by
class Object does return distinct integers for distinct objects. (This
is typically implemented by converting the internal address of the
object into an integer, but this implementation technique is not
required by the JavaTM programming language.)"

So the default hashCode() does not necessarily involve adresses.

Regards,
Tomas
 
C

chucky

If you declare your sets/maps using the interface "Set<MyThing>" and
"Map<MyThing, OtherThing>", then you can switch between different
implementations.

And then I will have to implement Comparable or provide a
Comparator:)

Anyway, I got my answer already, thank you for sharing your ideas!

Tomas
 
L

Lew

As I stated in the title of this topic and in first paragraph of my
original post, I was intrested in comparing the addresses in sense of
ordering. So the page you linked does not answer the question neither
positively nor negatively.
It isn't even guaranteed that an object has an address.

Even when an object does have an "address", that "address" can change during
the lifetime of the object, for example after a garbage collection.
So the default hashCode() does not necessarily involve adresses.

and cannot, really, for the reasons cited.

I think Sun made a huge mistake referring to "address" in the docs for
hashCode(). There is no meaningful numeric interpretation of an object's
"address" in the JVM. Even so, the Javadocs do use the terminology
"/converting/ the internal address of the object" (emph. added), indicating
that even with this undefined concept of "address" it isn't even necessarily a
direct correspondence.

The hashCode() normally will not change unless the contents of the object
change. That means any tenuous association between the object's "address",
whatever that is, and its hashCode() will be broken at the next GC, assuming
no intervening changes in the object's values.

And assuming the object hasn't been optimized away entirely, thus eliminating
its "address" altogether.

The point is that Java as a language deliberately prevents the programmer from
doing direct address manipulation, preferring object-oriented reference
semantics. You cannot in general produce a consistent "address" for an object.
 
P

Patricia Shanahan

chucky said:
As I stated in the title of this topic and in first paragraph of my
original post, I was intrested in comparing the addresses in sense of
ordering. So the page you linked does not answer the question neither
positively nor negatively.

If you really want to use TreeSet to do HashSet's job, it does not
matter whether the order is an actual address order or not, as long as
it is consistent.

The real problem is the risk that the hashCode() results will not be
unique. I believe it is a theoretical possibility in a 32 bit JVM.
However, in a 64 bit JVM there could be more objects of a given type
than there are int values.

Patricia
 
C

chucky

If you really want to use TreeSet to do HashSet's job, it does not
matter whether the order is an actual address order or not, as long as
it is consistent.

The real problem is the risk that the hashCode() results will not be
unique. I believe it is a theoretical possibility in a 32 bit JVM.
However, in a 64 bit JVM there could be more objects of a given type
than there are int values.

I didn't mean to compare hashCodes. I didn't realize that the address
can change in lifetime of an object, so now I'm discouraged enough
from wanting to obtain it.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top