TreeSet/TreeMap equivalent for HashSet/HashMap (custom hasher)

Question

TreeSet has a constructor that takes a comparator, meaning even if the objects you store aren't Comparable objects by themselves, you can provide a custom comparator.

Is there an analogous implementation of a nonordered set? (e.g. an alternative to HashSet<T> that takes a "hasher" object that calculates equals() and hashCode() for objects T that may be different from the objects' own implementations?)

C++ std::hash_set gives you this, just wondering if there's something for Java.

---

Edit: @Max brings up a good technical point about equals() -- fair enough; and it's true for TreeMap and HashMap keys via Map.containsKey(). But are there other well-known data structures out there that allow organization by custom hashers?

Answer 1

No, having a "hasher" object is not supported by the Collections specifications. You can certainly implement your own collection that supports this but another way to do this is to consider the Hasher to be a wrapping object that you store in your HashSet instead.

Set<HasherWrapper<Foo>> set = new HashSet<HasherWrapper<Foo>>();
set.add(new HasherWrapper(foo));
...

The wrapper class would then look something like:

private class HasherWrapper<T> {
    T wrappedObject;
    public HasherWrapper(T wrappedObject) {
        this.wrappedObject = wrappedObject;
    }
    @Override
    public int hashCode() {
        // special hash code calculations go here
    }
    @Override
    public boolean equals(Object obj) {
        // special equals code calculations go here
    }
}

Answer 2

There is no such implementation in the standard library, but it doesn't prevent you from rolling your own. This is something i've often wanted to have myself.

See http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4771660 for the reason:

We wanted to avoid the complexity. We seriously entertained this notion at the time the collections framework was designed, but rejected it. The power-to-weight ration seemed to low. We felt that equals was what you wanted 95% of the time; ==, 4%; and something else 1%. Writing sensible contracts for bulk operations when is very tricky when equality predicates differ.

Answer 3

No, there is not and there can not be by specification. Moreover, you misunderstood the way TreeSet uses it's Comparator.

From TreeSet Javadoc:

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. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

From Comparable javadoc:

The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C. Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.

From Collection javadoc:

boolean contains(Object o)

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

Therefore, by specification there can not be any kind of class that implements Collection<E> interface and fully depend on some external Comparator-style object to insert objects. All Collections should use equals method of an Object class to verify if the object is already inserted.

Answer 4

There is definitely nothing like that, hashcode() and equals() are defining attributes of an object and should not be changed. They define what makes an object equal to each other and this shouldn't be different from one set to another. The only way to do what you are talking about is to subclass the object and write a new hashcode() and equals() and this would only really make sense to do if the subclass had a defining variable that should be added in addition to the super class' hashcode() and equals(). I know this may not be what you are aiming for but I hope this helps. If you explain your reasoning more for wanting this then it might help to find a better solution if there exists one.