Correct way to implement Map>

Question

I was asked this in interview. using Google Guava or MultiMap is not an option. I have a class

public class Alpha
{
     String company;
     int local;
     String title;
}

I have many instances of this class (in order of millions). I need to process them and at the end find the unique ones and their duplicates. e.g.

instance --> instance1, instance5, instance7 (instance1 has instance5 and instance7 as duplicates)
instance2 --> instance2 (no duplicates for instance 2)

My code works fine

declare datastructure

HashMap<Alpha,ArrayList<Alpha>> hashmap = new HashMap<Alpha,ArrayList<Alpha>>();

Add instances

for (Alpha x : arr)
{
    ArrayList<Alpha> list = hashmap.get(x); ///<<<<---- doubt about this. comment#1
    if (list == null)
    {
        list = new ArrayList<Alpha>();
        hashmap.put(x, list);
    }
        list.add(x);
}

Print instances and their duplicates.

for (Alpha x : hashmap.keySet())
{
    ArrayList<Alpha> list = hashmap.get(x); //<<< doubt about this. comment#2
    System.out.println(x + "<---->");
    for(Alpha y : list)
    {
        System.out.print(y);
    }
    System.out.println();
}

Question: My code works, but why? when I do hashmap.get(x); (comment#1 in code). it is possible that two different instances might have same hashcode. In that case, I will add 2 different objects to the same List.

When I retrieve, I should get a List which has 2 different instances. (comment#2) and when I iterate over the list, I should see at least one instance which is not duplicate of the key but still exists in the list. I don't. Why?. I tried returning constant value from my hashCode function, it works fine.

If you want to see my implementation of equals and hashCode,let me know.

Bonus question: Any way to optimize it?

Edit:

@Override
    public boolean equals(Object obj) {
        if (obj==null || obj.getClass()!=this.getClass())
            return false;
        if (obj==this)
            return true;
        Alpha guest = (Alpha)obj;
        return guest.getLocal()==this.getLocal()
                && guest.getCompany()  == this.getCompany()
                && guest.getTitle() == this.getTitle();
    }

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + (title==null?0:title.hashCode());
    result = prime * result + local;
    result = prime * result + (company==null?0:company.hashCode());
    return result;
}

Answer 1

it is possible that two different instances might have same hashcode

Yes, but hashCode method is used to identify the index to store the element. Two or more keys could have the same hashCode but that's why they are also evaluated using equals.

From Map#containsKey javadoc:

Returns true if this map contains a mapping for the specified key. More formally, returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k)). (There can be at most one such mapping.)

---

Some enhancements to your current code:

• Code oriented to interfaces. Use Map and instantiate it by HashMap. Similar to List and ArrayList.

• Compare Strings and Objects in general using equals method. == compares references, equals compares the data stored in the Object depending the implementation of this method. So, change the code in Alpha#equals:

  public boolean equals(Object obj) {
      if (obj==null || obj.getClass()!=this.getClass())
          return false;
      if (obj==this)
          return true;
      Alpha guest = (Alpha)obj;
      return guest.getLocal().equals(this.getLocal())
              && guest.getCompany().equals(this.getCompany())
              && guest.getTitle().equals(this.getTitle());
  }
  

• When navigating through all the elements of a map in pairs, use Map#entrySet instead, you can save the time used by Map#get (since it is supposed to be O(1) you won't save that much but it is better):

  for (Map.Entry<Alpha, List<Alpha>> entry : hashmap.keySet()) {
      List<Alpha> list = entry.getValuee();
      System.out.println(entry.getKey() + "<---->");
      for(Alpha y : list) {
          System.out.print(y);
      }
      System.out.println();
  }
  

Answer 2

Use equals along with hashCode to solve the collision state.

Steps:

• First compare on the basis of title in hashCode()
• If the title is same then look into equals() based on company name to resolve the collision state.

Sample code

class Alpha {
    String company;
    int local;
    String title;

    public Alpha(String company, int local, String title) {
        this.company = company;
        this.local = local;
        this.title = title;
    }

    @Override
    public int hashCode() {
        return title.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Alpha) {
            return this.company.equals(((Alpha) obj).company);
        }
        return false;
    }
}

...

Map<Alpha, ArrayList<Alpha>> hashmap = new HashMap<Alpha, ArrayList<Alpha>>();

hashmap.put(new Alpha("a", 1, "t1"), new ArrayList<Alpha>());
hashmap.put(new Alpha("b", 2, "t1"), new ArrayList<Alpha>());
hashmap.put(new Alpha("a", 3, "t1"), new ArrayList<Alpha>());

System.out.println("Size : "+hashmap.size());

Output

Size : 2