How to remove duplicate key from a Hashmap

Question

I have a list of list. There is a list within a list. [[-1, 0, 1], [-1, 2, -1], [0, 1, -1]], name of this list say result. result list contain duplicate elements as a list. [-1,0,1] and [0,1,-1] they are same. I want to make a list which does not contain duplicates. So list result become [[-1,0,1],[-1,2,-1]] or [[-1,2,-1],[0,1,-1]] .

I read that Hashmap can not store duplicate keys but allow duplicate values. So to remove duplicates I was trying Hashmap.

But after writing the code it run well there is no error.

HashMap<List<Integer>,Integer> final_sol=new HashMap<>();
for(int k1=0;k1<result.size();k1++){
       final_sol.put(result.get(k1),k1);
    }
    System.out.println(final_sol);

Output:

{[-1, 2, -1]=1, [0, 1, -1]=2, [-1, 0, 1]=0}

After writing this code blocks I thought my duplicate keys cannot shown only unique keys displayed.

Then how could I make this list unique using Hash map?Fail to understand

When I was using tree map it doesn't compile and gave som eerror.

Answer 1

It is true that Maps do not retain duplicate keys and Sets do not retain duplicate elements, but you need to understand that "duplicate" is defined in terms of keys / elements equals() methods, and that hash-based collections depend on their keys / elements having hashCode() methods that are consistent with their equals() methods.

Now you say

[-1,0,1] and [0,1,-1] they are same.

, but no, they are not the same as far as Lists' definition of equality goes. The order of list elements is significant, and Lists are required to implement equals() in a manner that reflects that. That's why both those lists may appear as keys in the same Map, and both may appear as elements in the same Set.

Then how could I make this list unique using Hash map?

Apparently order is not significant for your purposes, so Lists aren't really the right model for you to work with. If you do not need to accommodate duplicate elements, then you should consider using Sets instead. The standard library provides several implementations, of which HashSet would probably be the most suited to your situation as I understand it. If you do need to accommodate duplicate elements, then you're looking for a multiset. The standard library does not provide an implementation, but there are several available from third parties.

When I was using tree map it doesn't compile and gave some error.

Well yes, it would, unless you provided it with a Comparator by which to determine the relative order of your elements. TreeMap recognizes duplicates as keys that compare equal according to their natural or Comparator-specified order.

Overall, it sounds like instead of a list of lists, you want a set of sets or a set of multisets. I don't see why you would want to bring maps into it.

Answer 2

Try something like this:

List<List<Integer>> result = Arrays.asList(
      Arrays.asList(-1, 0, 1),
      Arrays.asList(-1, 2, -1),
      Arrays.asList(0, 1, -1)
);
HashMap<Set<Integer>, List<Integer>> final_sol = new HashMap<>();

for (List<Integer> list : result) {
  final_sol.put(new HashSet<>(list), list);
}

System.out.println(final_sol.values());

You think, that [-1,0,1] and [0,1,-1] they are same, but this does not hold for lists, because order of elements matters. You need sets for this understanding of equals.

But even then it may not be what you expected, when [0,0,1] and [0,1,1] are same. In this case you must transform each list to a Map which gives you the count of the same Integer in the original list.

Answer 3

It appears that you can do this on-line with a Set<Set<Integer>>. That gives you [[-1, 0, 1], [-1, 2]]; homomorphic to [[-1, 0, 1], [-1, 2, -1]], but not your desired result. The following is for a set of vectors of three integers that compare equal with any permutation, which is consistent with your examples. Per the documentation, overriding equals requires an equivalence relation, and necessarily, hashCode, such that a == b -> hashCode(a) == hashCode(b).

import java.lang.String;
import java.lang.Integer;
import java.util.Set;
import java.util.LinkedHashSet;

class Java {

    public static void main(String args[]) {
        Set<Three> set = new LinkedHashSet<>();
        set.add(new Three(-1, 0, 1));
        set.add(new Three(-1, 2, -1));
        set.add(new Three(0, 1, -1));
        System.out.printf("%s.\n", set);
    }

}

final class Three {
    private int a, b, c;
    public Three(final int a, final int b, final int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
    @Override
    public int hashCode() { return a + b + c; }
    @Override
    public boolean equals(Object o) {
        if(this == o) return true;
        if(!(o instanceof Three)) return false;
        Three t = (Three)o;
        /* Brute force 3! = 6. */
        return a == t.a && b == t.b && c == t.c
            || a == t.a && b == t.c && c == t.b
            || a == t.b && b == t.a && c == t.c
            || a == t.b && b == t.c && c == t.a
            || a == t.c && b == t.a && c == t.b
            || a == t.c && b == t.b && c == t.a;
    }
    @Override
    public String toString() {
        return "["+a+","+b+","+c+"]";
    }
}

This produces,

[[-1,0,1], [-1,2,-1]].

Edit: The following is a replacement for the above code for a set of vectors of three integers that compare equal when put in a set, which is also consistent with your examples.

    /** Hashcode is the sum of the unique numbers. */
    @Override
    public int hashCode() {
        int h = a;
        if(a != b) h += b;
        if(c != a && c != b) h += c;
        return h;
    }
    @Override
    public boolean equals(Object o) {
        if(this == o) return true;
        if(!(o instanceof Three)) return false;
        Three t = (Three)o;
        /* t \in this && this \in t. */
        return (a == t.a || a == t.b || a == t.c)
            && (b == t.a || b == t.b || b == t.c)
            && (c == t.a || c == t.b || c == t.c)
            && (t.a == a || t.a == b || t.a == c)
            && (t.b == a || t.b == b || t.b == c)
            && (t.c == a || t.c == b || t.c == c);
    }