Java: How to workaround the lack of Equatable interface?

Question

As far as I know, things such as SortedMap or SortedSet, use compareTo (rather than equals) on Comparable<?> types for checking equality (contains, containsKey).

But what if certain types are equatable by concept, but not comparable?
(Hash codes, memory addresses, ...)

I have to declare a Comparator<?> and override the method int compareTo(T o1, To2). OK, I can return 0 for instances which are considered equal. But, for unqeual instances, what do I return when an order is not evident?

Is the approach of using SortedMap or SortedSet on equatable but (by concept) not comparable types good anyway?

Thank you!

EDIT:
I don't want to store things sorted, but would I use "usual" Map and Set, I couldn't "override" the equality-behavior.

EDIT 2:
Why I can't just override equals(...):
I need to alter the equality-behavior of a foreign class. I can't edit it.

EDIT 3:
Just think of .NET: They have IEquatable interface which cat alter the equality-behavior without touching the comparable behavior.

EDIT 4:
Can't I just make compareTo return 0 for equal and 1 for non-equal instances? What's the big problem? I've dome some tests, it seems that SortedMap/SortedSet call compareTo on a pair of instances once. Yes, the order would not make sense, but why should it be my problem? I don't need the order. *I just need altered equality-behavior. Sadly most people just can't understand this.
NOTE: The concept of returning 1 for non-equal instances now was proven wrong.

EDIT 5:
Altering equality-behavior of foreign classes is a bad concept? Sure? I don't think so: Why then am I allowed to alter comparison-behavior of foreign classes using Comparator?

EDIT 6:
Thanks to Mark Peters and waxwing for the idea of wrapping the key type in a custom class. This way, I can override equals and hashCode, thus altering the equality-behavior.

Answer 1

Consider wrapping your foreign class inside your own instead.

public class Foreign {
  // undesired equals() and hashCode() implementation
}


public class ForeignWrapper {
   private Foreign foreign;

   public ForeignWrapper(Foreign foreign) {
      this.foreign = foreign;
   }

   public void equals() {
       // your equals implementation, using fields from foreign
   }

   public int hashCode() {
       // your hashCode implementation, using fields from foreign
   }

}

Then add new ForeignWrapper(foreign) to the standard HashSet / HashMap. Not applicable in all situations, but maybe in yours.