Why am I getting duplicate keys in Java HashMap?

Question

I seem to be getting duplicate keys in the standard Java HashMap. By "duplicate", I mean the keys are equal by their equals() method. Here is the problematic code:

import java.util.Map;
import java.util.HashMap;

public class User {
    private String userId;
    public User(String userId) { 
        this.userId = userId;
    }
    public boolean equals(User other) {
        return userId.equals(other.getUserId());
    }
    public int hashCode() {
        return userId.hashCode();
    }
    public String toString() {
        return userId;
    }

    public static void main(String[] args) {
        User arvo1 = new User("Arvo-Part");
        User arvo2 = new User("Arvo-Part");
        Map<User,Integer> map = new HashMap<User,Integer>();
        map.put(arvo1,1);
        map.put(arvo2,2);

        System.out.println("arvo1.equals(arvo2): " + arvo1.equals(arvo2));
        System.out.println("map: " + map.toString());
        System.out.println("arvo1 hash: " + arvo1.hashCode());
        System.out.println("arvo2 hash: " + arvo2.hashCode());
        System.out.println("map.get(arvo1): " + map.get(arvo1));
        System.out.println("map.get(arvo2): " + map.get(arvo2));
        System.out.println("map.get(arvo2): " + map.get(arvo2));
        System.out.println("map.get(arvo1): " + map.get(arvo1));
    }
}

And here is the resulting output:

arvo1.equals(arvo2): true
map: {Arvo-Part=1, Arvo-Part=2}
arvo1 hash: 164585782
arvo2 hash: 164585782
map.get(arvo1): 1
map.get(arvo2): 2
map.get(arvo2): 2
map.get(arvo1): 1

As you can see, the equals() method on the two User objects is returning true and their hash codes are the same, yet they each form a distinct key in map. Furthermore, map continues to distinguish between the two User keys in the last four get() calls.

This directly contradicts the documentation:

More formally, if this map contains a mapping from a key k to a value v such that (key==null ? k==null : key.equals(k)), then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

Is this a bug? Am I missing something here? I'm running Java version 1.8.0_92, which I installed via Homebrew.

EDIT: This question has been marked as a duplicate of this other question, but I'll leave this question as is because it identifies a seeming inconsistency with equals(), whereas the other question assumes the error lies with hashCode(). Hopefully the presence of this question will make this issue more easily searchable.

Try adding `@Override` to your `equals` and `hashCode` methods (always a best practice) and see if you get any helpful information. — chrylis -cautiouslyoptimistic-, Jul 15 '16 at 05:56
To allow this kind of typos, or mistakes, in the future, always let your IDE generate the methods for you. Then tweak them to make them look like you want. This would have created the correct methods with `@Override` annotations. — Magnilex, Jul 15 '16 at 06:12

score 29 · Accepted Answer · edited Jul 15 '16 at 07:31

29

The issue lies in your equals() method. The signature of Object.equals() is equals(OBJECT), but in your case it is equals(USER), so these are two completely different methods and the hashmap is calling the one with Object parameter. You can verify that by putting an @Override annotation over your equals - it will generate a compiler error.

The equals method should be:

  @Override
  public boolean equals(Object other) {
    if(other instanceof User){
        User user = (User) other;
        return userId.equals(user.userId);
    }

    return false;
}

As a best practice you should always put @Override on the methods you override - it can save you a lot of trouble.

edited Jul 15 '16 at 07:31

T.G

1,913
1
16
29

answered Jul 15 '16 at 06:08

Svetlin Zarev

14,713
4
53
82

The interesting question for me: Shouldn't dynamic typing call the best match for the call? `Object o = new User(); -> o.equals(o)` could be dispatched to the best match for the runtime-types. - But Java uses static compile-time typing to find the right overload, not dynamic runtime-parameters - you could include that in your answer for completeness! – Falco Jul 15 '16 at 12:04
It will be dispatched to the best `compile time' type. java does not have dynamic typing – Svetlin Zarev Jul 15 '16 at 12:06
1

Hmm, you are missing that the hasmap is compiled to call always the `equals(object)`, so if you have `equals(user)` it will never call it. But if you in your code do `User user = new User(); user.equals(new User())`, the `equals(User)` will be called. But if you do as in your example `Object user = new User(); user.equals(new User())` the `equals(object)` will be called. I hope that clears it – Svetlin Zarev Jul 15 '16 at 12:12
That clears it! I think adding it to your answer for other Users could be beneficial :-) – Falco Jul 15 '16 at 12:18
I would avoid instanceof in equals unless it is explicitly guaranteed that derived classes wont be an issue. – josefx Jul 28 '16 at 10:02

score 13 · Answer 2 · answered Jul 15 '16 at 06:08

Your equals method does not override equals, and the types in the Map are erased at runtime, so the actual equals method called is equals(Object). Your equals should look more like this:

@Override
public boolean equals(Object other) {
    if (!(other instanceof User))
        return false;
    User u = (User)other;
    return userId.equals(u.userId);
}

score 3 · Answer 3 · edited Jul 15 '16 at 09:49

OK, so first of all, the code doesn't compile. Missing this method:

other.getUserId()

But aside from that, you'll need to @Override equals method, IDE like Eclipse can also help generating equals and hashCode btw.

@Override
public boolean equals(Object obj)
{
  if(this == obj)
     return true;
  if(obj == null)
     return false;
  if(getClass() != obj.getClass())
     return false;
  User other = (User) obj;
  if(userId == null)
  {
     if(other.userId != null)
        return false;
  }
  else if(!userId.equals(other.userId))
     return false;
  return true;
}

score 2 · Answer 4 · edited May 23 '17 at 10:27

Like others answered you had a problem with the equals method signature. According to Java equals best practice you should implement equals like the following :

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    User user = (User) o;

    return userId.equals(user.userId);
  }

Same thing applies for the hashCode() method. see Overriding equals() and hashCode() method in Java

The Second Problem

you don't have duplicates anymore now, but you have a new problem, your HashMap contains only one element:

map: {Arvo-Part=2}

This is because both User objects are referencing the same String(JVM String Interning), and from the HashMap perspective your two objects are the same, since both objects are equivalent in hashcode and equals methods. so when you add your second object to the HashMap you override your first one. to avoid this problem, make sure you use a unique ID for each User

A simple demonstration on your users :

Why am I getting duplicate keys in Java HashMap?

4 Answers4