how to prevent duplicate objects in HashMap???

P

pembed2003

Hi all,
I have been trying to do something really simple but I could find any
solutions to it! I have the following:

class P{

int id;

P(int i){id = i;}

public int hashCode(){return id;}

public boolean equals(P o){return id = o.id;}

public static void main(String[] args){
HashMap m = new HashMap();
m.put(new P(1),new Integer(1));
m.put(new P(1),new Integer(2));
Set k = m.entrySet();
Iterator i = k.iterator();
while(i.hasNext()){
System.out.println(i.next());
}
}
}

The program prints out 2 lines which I am not sure I understand. My P
class has a hashCode method which simply returns the id of the object.
I put 2 'new P(1)' instance into m but why doesn't HashMap reject the
second one or overwrite the first one becasue they have the same hash
code??? I though the purpose of hashCode is to let you reject or
detect dup objects, no?

In generaly, I found it difficult to do something like:

//
// insert a bunch of objects into a HashMap
//

later:

//
// how to check if HashMap has a P object with id 1???
//

this:

if(m.containsKey(new P(1)){
}

ALWAYS return false even I have a lot of P objects with id 1! How do I
solve that? Thanks!
 
S

Steve W. Jackson

:Hi all,
:I have been trying to do something really simple but I could find any
:solutions to it! I have the following:
:
:class P{
:
: int id;
:
: P(int i){id = i;}
:
: public int hashCode(){return id;}
:
: public boolean equals(P o){return id = o.id;}
:
: public static void main(String[] args){
: HashMap m = new HashMap();
: m.put(new P(1),new Integer(1));
: m.put(new P(1),new Integer(2));
: Set k = m.entrySet();
: Iterator i = k.iterator();
: while(i.hasNext()){
: System.out.println(i.next());
: }
: }
:}
:
:The program prints out 2 lines which I am not sure I understand. My P
:class has a hashCode method which simply returns the id of the object.
:I put 2 'new P(1)' instance into m but why doesn't HashMap reject the
:second one or overwrite the first one becasue they have the same hash
:code??? I though the purpose of hashCode is to let you reject or
:detect dup objects, no?
:
:In generaly, I found it difficult to do something like:
:
://
:// insert a bunch of objects into a HashMap
://
:
:later:
:
://
:// how to check if HashMap has a P object with id 1???
://
:
:this:
:
:if(m.containsKey(new P(1)){
:}
:
:ALWAYS return false even I have a lot of P objects with id 1! How do I
:solve that? Thanks!

I can't say with any certainty since I'm not expert at the bit shifting
aspects of Java (or any other language, for that matter). But the
source code for HashMap is included in your J2SDK and shows how
containsKey is implemented. It does not simply use hashCode(), but
instead starts with it and then applies what the comments call a
"supplemental hash function". The results of this action are then
looked up in the internal table of entries. The best guess I could make
is that the address in memory is somehow being brought into play, so
that each of these are indeed unique from the others.

= Steve =
 
M

Marco Schmidt

pembed2003:

[...]
ALWAYS return false even I have a lot of P objects with id 1! How do I
solve that? Thanks!

(I'm just guessing:) Try to override equals(Object), not create
equals(P).

Regards,
Marco
 
C

Chris Uppal

pembed2003 said:
The program prints out 2 lines which I am not sure I understand. My P
class has a hashCode method which simply returns the id of the object.
I put 2 'new P(1)' instance into m but why doesn't HashMap reject the
second one or overwrite the first one becasue they have the same hash
code??? I though the purpose of hashCode is to let you reject or
detect dup objects, no?

That's not really true. The purpose of the hash code is as a *hint* to let the
implementation find object that are equal. It would be perfectly possible to
write a conforming implementation that didn't actually use the hash code at
all, but just looped through the collection trying equals() on everything.
(That implementation would be too slow for general use, but would probably be
more efficient for very small collections)

The real implementation does make use of the hash code and it depends crucially
on the assumptions that if two object have different hash codes then they are
not equal(), and that if they *are* equal then they have the same hash codes.

What it does *not* require is that two object with the same hash code are
equal(). In fact it is perfectly legal for *every* object to have the same
hash code (33, say). That would make hashed collections very inefficient, but
they'd still work correctly.

In your example code you *seem* to be correctly implementing hashCode() and
equals() to work together in the way that hashed collections require, but
actually there's a small bug ;-) Your definition of equals() takes a P as
parameter, and so it doesn't override the definition in Object (which takes an
Object parameter). Hence the HashMap is using your definition of hashCode(),
but the definition of equals() from Object (which uses identity comparison).
So it doesn't quite work...

-- chris
 
P

pembed2003

[snip]
In your example code you *seem* to be correctly implementing hashCode() and
equals() to work together in the way that hashed collections require, but
actually there's a small bug ;-) Your definition of equals() takes a P as
parameter, and so it doesn't override the definition in Object (which takes an
Object parameter). Hence the HashMap is using your definition of hashCode(),
but the definition of equals() from Object (which uses identity comparison).
So it doesn't quite work...

-- chris

Your explaination makes sense. I will correct the bug and give it
another try. Thanks Chris!
 

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,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top