Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why am I getting duplicate keys in Java HashMap? [duplicate]

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.

like image 619
dmoon1221 Avatar asked Jul 15 '16 05:07

dmoon1221


People also ask

How does a HashMap find duplicates?

In this method, We use HashMap to find duplicates in array in java. We store the elements of input array as keys of the HashMap and their occurrences as values of the HashMap. If the value of any key is more than one (>1) then that key is duplicate element.

What happens if we insert duplicate key in HashMap?

If you try to insert the duplicate key, it will replace the element of the corresponding key. HashMap is similar to HashTable, but it is unsynchronized. It allows to store the null keys as well, but there should be only one null key object and there can be any number of null values.


3 Answers

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.

like image 130
Svetlin Zarev Avatar answered Oct 09 '22 04:10

Svetlin Zarev


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);
}
like image 27
midor Avatar answered Oct 09 '22 03:10

midor


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;
}
like image 3
Vladimir Avatar answered Oct 09 '22 04:10

Vladimir