HashMap with object value as key

You could solve this (if I am understanding this right) by overriding the equals and hashcode methods in the Node object to use the same criteria as the compareTo method.

You should use TreeSet as it relies on ordering, not on hashing.

Update (WRONG! See update 3): But you still have to make sure a.compareTo(b)==0 iff a.equals(b) because the implementation of contains actually finds the corresponding element by the ordering, and then checks equality using equals!

Update 2: To use only the ordering, you could make the first list sorted (Collections.sort(listA)) and then check the result of Collections.binarySearch(listA, nodeB) for each nodeB from listB. When the result is >=0 the nodeB was in listA, w.r.t their ordering. The implementation of binarySearch uses only ordering, no equals involved. The complexity of this approach is O(n log(n)) since each binary search is O(log(n)) (n being size of the bigger of the lists -- sorting list A is also O(n log(n))), that is the same complexity as using TreeSet (O(log n) for both insert/contains).

Update 3: As pointed out in the comments, the TreeSet should do the work, as the equals is not used in the TreeMap's containsKey, but somewhere else. But the JavaDoc says:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface.

And docs for the contains method for TreeSet (!) says:

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

So it is still not a good idea to use TreeSet with incosistent API. Who knows what another Java implementation may do in such a case. So I suggest sticking with the Update 2 solution.

My suggestion would be to make your own subclass of HashMap that overrides the containsValue(object value) function with one that fits your criteria.

Use TreeSet/TreeMap. It uses compareTo() method instead of equals() and hashcode() which is what used while assigning Nodes in HashMap/HashSet.

Look at the following code:

import java.util.HashSet; import java.util.TreeSet; public class TestMaps { public static void main(String[] args) { TreeSet<Node> set1 = new TreeSet<>(); HashSet<Node> set2 = new HashSet<>(); Node node1 = new Node(0, "First"); Node node2 = new Node(0, "Second"); System.out.println(set1.add(node1)); //Node1 added in TreeSet System.out.println(set2.add(node1));//Node1 added in HashSet System.out.println(set1.add(node2));//Node2 added in TreeSet System.out.println(set2.add(node2));//Node2 added in HashSet } } class Node implements Comparable<Node>{ int i; String name; Node(int i, String n){ this.i = i; this.name = n; } @Override public int compareTo(Node o) { return this.i - o.i; } } 

Running this results into :

true true false true 

Hope it helps!!