HashTable

[George]

Dear All,

I am using a HashTable with HashSets as the keys (they point to integers
and it has to be that way round because of an algorithm I am
implementing).

I calculate the HashSet from a different method and then I use
hashtablename.containsKey(hashset). The problem is that altough the values
of the hashset are identical containsKey will fail.

Any ideas as to how I might get the correct results?

George

 

[Gordon Beaton]

I am using a HashTable with HashSets as the keys (they point to
integers and it has to be that way round because of an algorithm I
am implementing).

I calculate the HashSet from a different method and then I use
hashtablename.containsKey(hashset). The problem is that altough the
values of the hashset are identical containsKey will fail.

Any ideas as to how I might get the correct results?

Have you modified the HashSet in any way (added or removed elements)
after storing it in the HashTable?

Have you confirmed that the HashSet in the HashTable and the object
you use to find it with, in fact have the same hashCode()? Are they
equals()?

What kind of objects are stored in the HashSet, and did you remember
to implement hashCode() and equals() methods properly in *those*
objects?

/gordon

--

 

[George]

On Tue, 17 Jul 2007 Lekeas GK wrote...

|From: Gordon Beaton <[email protected]>
|Date: 17 Jul 2007 12:42:37 GMT
|Subject: Re: HashTable
|
|On Tue, 17 Jul 2007 13:33:31 +0100, George wrote:
|> I am using a HashTable with HashSets as the keys (they point to
|> integers and it has to be that way round because of an algorithm I
|> am implementing).
|>
|> I calculate the HashSet from a different method and then I use
|> hashtablename.containsKey(hashset). The problem is that altough the
|> values of the hashset are identical containsKey will fail.
|>
|> Any ideas as to how I might get the correct results?
|
|Have you modified the HashSet in any way (added or removed elements)
|after storing it in the HashTable?
No, they have not been modified at all.
|
|Have you confirmed that the HashSet in the HashTable and the object
|you use to find it with, in fact have the same hashCode()? Are they
|equals()?

They contain two objects each, which are exactly the same. Does that not
make equal?
|
|What kind of objects are stored in the HashSet, and did you remember
|to implement hashCode() and equals() methods properly in *those*
|objects?

HashSet stores SigElement objects (custom datatype but simple - a couple
of string objects really). But would they not get these methods from the
Object class?
|
|/gordon
|
|--
|

 

[Lew]

Have you modified the HashSet in any way (added or removed elements)
after storing it in the HashTable?

Have you confirmed that the HashSet in the HashTable and the object
you use to find it with, in fact have the same hashCode()?

Assuming java.util.HashSet, the hashCode() calculation is completely reliable.

Are they equals()?

Ay, there's the rub. They aren't.

What kind of objects are stored in the HashSet, and did you remember
to implement hashCode() and equals() methods properly in *those*
objects?

Irrelevant. He's comparing HashSets, not their contents.

It's hard to be sure without an SSCCE, but a couple of things might be wrong:

First of all, who provides the HashTable class? Maybe there is something
strange about it. (Unless you meant java.utilHashtable, but your spelling
says otherwise. If you did mean Hashtable, why are you using that Map
implementation? Is synchronization needed?)

Second, what is the definition of HashSet.equals()? As it happens, you're
guaranteeing that the HashSet in the HashTable (sic) is different from the one
you're querying. That's why the lookup is failing.

 

[Lew]

Gordon Beaton:

|Have you confirmed that the HashSet in the HashTable and the object
|you use to find it with, in fact have the same hashCode()? Are they
|equals()?

They contain two objects each, which are exactly the same. Does that not
make equal?

Yes, that does /not/ make the HashSets equal.

What is the definition of HashSet.equals()?

 

[Gordon Beaton]

Irrelevant. He's comparing HashSets, not their contents.

The hashcode of the HashSet is based on the hashcodes of the elements
it contains. A second HashSet containing supposedly identical objects,
but whose hashcodes are different, will itself have a different
HashCode. How can Hashtable.containsKey() succeed?

/gordon

--

 

[Lew]

The hashcode of the HashSet is based on the hashcodes of the elements
it contains. A second HashSet containing supposedly identical objects,
but whose hashcodes are different, will itself have a different
HashCode. How can Hashtable.containsKey() succeed?

You're absolutely right.

 

[Gordon Beaton]

Assuming java.util.HashSet, the hashCode() calculation is completely reliable.

What makes you think I implied that it wasn't?

/gordon

--

 

[Lew]

What makes you think I implied that it wasn't?

Bad thinking on my part. Sorry.

 

[Gordon Beaton]

HashSet stores SigElement objects (custom datatype but simple - a
couple of string objects really). But would they not get these
methods from the Object class?

They do unless you've overridden the methods, which you should always
do when you store your own object types in any collection that uses
hashCode() and equals() on its contents. The default methods don't
work in most realistic situations.

Here's a test: create two distinct SigElements objects with the same
contents. Display their hashcodes and the results of s1.equals(s2). Do
they appear to be equivalent?

/gordon

--

 

[George]

I am refering to the classes available from java.util, you are right. But
if you construct a hashset containing objects o1 and o2 (assume any type
of objects) and a second hashset containing their clones, would the
hashcodes of the objects (and hence the hashcode of the hashset containing
them) be the same?

It would seem logical to me that the answer to this question should be
positive, but the results of my code suggest otherwise...

By overiding equals and hashCode, I get something more closer to the
result I want but a bit further from what I would assume as correct
behaviour. If you could provide any explanation as to why the answer to my
assumption above shoulbe no, I would be grateful.

Thanks,
George

On Tue, 17 Jul 2007 Lekeas GK wrote...

|From: Lew <[email protected]>
|Date: Tue, 17 Jul 2007 09:08:32 -0400
|Subject: Re: HashTable
|
|Gordon Beaton wrote:
|> On Tue, 17 Jul 2007 08:53:05 -0400, Lew wrote:
|>> Gordon Beaton wrote:
|>>> Have you confirmed that the HashSet in the HashTable and the object
|>>> you use to find it with, in fact have the same hashCode()?
|>> Assuming java.util.HashSet, the hashCode() calculation is completely reliable.
|>
|> What makes you think I implied that it wasn't?
|
|Bad thinking on my part. Sorry.
|
|--
|Lew
|

 

[Chris Dollin]

I am refering to the classes available from java.util, you are right. But
if you construct a hashset containing objects o1 and o2 (assume any type
of objects) and a second hashset containing their clones, would the
hashcodes of the objects (and hence the hashcode of the hashset containing
them) be the same?

No. (Well, it /could/ be. By coincidence. But likely not.)

It would seem logical to me that the answer to this question should be
positive, but the results of my code suggest otherwise...

The default hashcode is a magic number (something like the original
address of the object, or maybe an allocation count, or something).
It's nothing to do with any members you may have in the object. Also
the default .equals is ==.

 

[Lew]

I am refering to the classes available from java.util, you are right. But
if you construct a hashset [sic] containing objects o1 and o2 (assume any type
of objects) and a second hashset [sic] containing their clones, would the
hashcodes [sic] of the objects (and hence the hashcode [sic] of the hashset [sic] containing
them) be the same?

Only if the class of the objects in the set overrode equals() to indicate
value equality instead of the default reference equality.

So, for example, given a class that does not override equals():

public class Foo
{
private String f;
private String g;
// public accessor and mutator methods ...
}

two distinct Foo objects f1 and f2 aren't equal even if f1.f.equals( f2.f )
and f1.g.equals( f2.g ). f1 != f2 even if f1.f == f2.f and f1.g == f2.g.

Btw, it's "HashSet".

 

[Lew]

f1 != f2 even if f1.f == f2.f and f1.g == f2.g.

I meant, "! f1.equals( f2 ) even if ...".

 

[Lew]

No. (Well, it /could/ be. By coincidence. But likely not.)

Even if the hash codes of the two HashSets (not "hashset") were the same, the
two would still not be equals() unless the objects were equals().

Similarly for any two objects. Even if the hash codes are the same, they
don't necessarily equals() each other.

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

George schreef:

I am refering to the classes available from java.util, you are right. But
if you construct a hashset containing objects o1 and o2 (assume any type
of objects) and a second hashset containing their clones, would the
hashcodes of the objects (and hence the hashcode of the hashset containing
them) be the same?

Ah, here’s the catch: clones are not == equal. I.e. obj.clone() != obj.
But if you override equals (which you should), then
obj.clone().equals(obj) should be true. (Make it true!)

By overiding equals and hashCode, I get something more closer to the
result I want but a bit further from what I would assume as correct
behaviour. If you could provide any explanation as to why the answer to my
assumption above shoulbe no, I would be grateful.

Then you are doing something wrong. Read the link in my sig if you want
more help.

And did you consider Lew’s advice to use HashMap instead of Hashtable?

H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGnNGye+7xMGD3itQRAv4sAJsHsgFHdo7T2N+oCiSbJSxJM0VVgwCeIdb3
4Ipb7JC9MwipX2JR1c+Y73c=
=bjFT
-----END PGP SIGNATURE-----

 

[rossum]

Dear All,

I am using a HashTable with HashSets as the keys (they point to integers
and it has to be that way round because of an algorithm I am
implementing).

I calculate the HashSet from a different method and then I use
hashtablename.containsKey(hashset). The problem is that altough the values
of the hashset are identical containsKey will fail.

Any ideas as to how I might get the correct results?

George

Have a look at Item 8: "Always override hashCode when you override
equals" in Chapter 3 of "Effective Java":
http://developer.java.sun.com/developer/Books/effectivejava/Chapter3.pdf

rossum

 

[Patricia Shanahan]

I am refering to the classes available from java.util, you are right. But
if you construct a hashset containing objects o1 and o2 (assume any type
of objects) and a second hashset containing their clones, would the
hashcodes of the objects (and hence the hashcode of the hashset containing
them) be the same?

It would seem logical to me that the answer to this question should be
positive, but the results of my code suggest otherwise...

These paragraphs strongly imply that you consider clones to be equal.
That means two distinct instances of your class can be equal, so the
Object equals and hashCode behavior is completely wrong for that class.
You do need to override.

By overiding equals and hashCode, I get something more closer to the
result I want but a bit further from what I would assume as correct
behaviour. If you could provide any explanation as to why the answer to my
assumption above shoulbe no, I would be grateful.

"something more closer" suggests that you are not there yet. If so, I
suggest doing the following:

1. Write a trivial hashCode() that always returns zero.

2. Concentrate on equals. Think carefully about what determines whether
an instance of your class is equal to another object, and implement that
test as your equals method.

The hash-based collections work correctly, but inefficiently, with a
trivial hashCode().

Once you are sure equals is correct, go back and implement hashCode so
that all equal instances have the same hashCode while minimizing
collisions between unequal objects.

Patricia

 

[George]

That is not really the case in my program - I will briefly try to explain
the situation.

I have a custom data structure, say custom1, made up of two string fields
and another custom data type, say custom2. So, there is a series of
custom2 objects creation, then used for a series of custom1 object
creation. The custom1 class also has a static HashTable field, indexed by
a HashSet. The HashSet is constructed in a separate method which has
statements of the type hashsetname.add(new custom3(...)).

When this method finishes, before insertion into the main HashTable I run
a check with containsKey - the problem is that it fails even for custom3
objects with exactly the same fields.

Please offer some advice if you can, as I am stuck at this point for about
a week now and it brought all my work to a halt.

Regards,
George

On Tue, 17 Jul 2007 Lekeas GK wrote...

|From: Patricia Shanahan <[email protected]>
|Date: Tue, 17 Jul 2007 13:18:19 -0700
|Subject: Re: HashTable
|
|George wrote:
|> I am refering to the classes available from java.util, you are right. But
|> if you construct a hashset containing objects o1 and o2 (assume any type
|> of objects) and a second hashset containing their clones, would the
|> hashcodes of the objects (and hence the hashcode of the hashset containing
|> them) be the same?
|>
|> It would seem logical to me that the answer to this question should be
|> positive, but the results of my code suggest otherwise...
|
|These paragraphs strongly imply that you consider clones to be equal.
|That means two distinct instances of your class can be equal, so the
|Object equals and hashCode behavior is completely wrong for that class.
|You do need to override.
|
|> By overiding equals and hashCode, I get something more closer to the
|> result I want but a bit further from what I would assume as correct
|> behaviour. If you could provide any explanation as to why the answer to my
|> assumption above shoulbe no, I would be grateful.
|
|"something more closer" suggests that you are not there yet. If so, I
|suggest doing the following:
|
|1. Write a trivial hashCode() that always returns zero.
|
|2. Concentrate on equals. Think carefully about what determines whether
|an instance of your class is equal to another object, and implement that
|test as your equals method.
|
|The hash-based collections work correctly, but inefficiently, with a
|trivial hashCode().
|
|Once you are sure equals is correct, go back and implement hashCode so
|that all equal instances have the same hashCode while minimizing
|collisions between unequal objects.
|
|Patricia
|

 

[Lew]

That is not really the case in my program - I will briefly try to explain
the situation.

Please do not top-post - it makes it harder to understand to what you are
responding.

/What/ is really not the case? That you need to override equals()? But you
most certainly do need to.

I have a custom data structure, say custom1, made up of two string fields
and another custom data type, say custom2. So, there is a series of
custom2 objects creation, then used for a series of custom1 object
creation. The custom1 class also has a static HashTable field, indexed by

Again, it's "Hashtable", not "HashTable".

a HashSet. The HashSet is constructed in a separate method which has
statements of the type hashsetname.add(new custom3(...)).

Thus guaranteeing that the inserted objects do not == objects in another Set.

When this method finishes, before insertion into the main HashTable I run
a check with containsKey - the problem is that it fails even for custom3
objects with exactly the same fields.

Because you did not override equals(), as has been repeatedly explained.

Please offer some advice if you can, as I am stuck at this point for about
a week now and it brought all my work to a halt.

My advice is to follow the advice you've already been given.