Why not allow an external interface to provide hashCode/equals for a HashMap?

With a TreeMap it's trivial to provide a custom Comparator, thus overriding the semantics provided by Comparable objects added to the map. HashMaps however cannot be controlled in this manner; the functions providing hash values and equality checks cannot be 'side-loaded'.

I suspect it would be both easy and useful to design an interface and to retrofit this into HashMap (or a new class)? Something like this, except with better names:

  interface Hasharator<T> {
    int alternativeHashCode(T t);
    boolean alternativeEquals(T t1, T t2);

  class HasharatorMap<K, V> {
    HasharatorMap(Hasharator<? super K> hasharator) { ... }

  class HasharatorSet<T> {
    HasharatorSet(Hasharator<? super T> hasharator) { ... }

The case insensitive Map problem gets a trivial solution:

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

Would this be doable, or can you see any fundamental problems with this approach?

Is the approach used in any existing (non-JRE) libs? (Tried google, no luck.)

EDIT: Nice workaround presented by hazzen, but I'm afraid this is the workaround I'm trying to avoid... ;)

EDIT: Changed title to no longer mention "Comparator"; I suspect this was a bit confusing.

EDIT: Accepted answer with relation to performance; would love a more specific answer!

EDIT: There is an implementation; see the accepted answer below.

EDIT: Rephrased the first sentence to indicate more clearly that it's the side-loading I'm after (and not ordering; ordering does not belong in HashMap).

Asked by: Kelvin517 | Posted: 28-01-2022

Answer 1

.NET has this via IEqualityComparer (for a type which can compare two objects) and IEquatable (for a type which can compare itself to another instance).

In fact, I believe it was a mistake to define equality and hashcodes in java.lang.Object or System.Object at all. Equality in particular is hard to define in a way which makes sense with inheritance. I keep meaning to blog about this...

But yes, basically the idea is sound.

Answered by: Kelvin628 | Posted: 01-03-2022

Answer 2

A bit late for you, but for future visitors, it might be worth knowing that commons-collections has an AbstractHashedMap (in 3.2.2 and with generics in 4.0). You can override these protected methods to achieve your desired behaviour:

protected int hash(Object key) { ... }
protected boolean isEqualKey(Object key1, Object key2) { ... }
protected boolean isEqualValue(Object value1, Object value2) { ... }
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... }

An example implementation of such an alternative HashedMap is commons-collections' own IdentityMap (only up to 3.2.2 as Java has its own since 1.4).

This is not as powerful as providing an external "Hasharator" to a Map instance. You have to implement a new map class for every hashing strategy (composition vs. inheritance striking back...). But it's still good to know.

Answered by: David660 | Posted: 01-03-2022

Answer 3

HashingStrategy is the concept you're looking for. It's a strategy interface that allows you to define custom implementations of equals and hashcode.

public interface HashingStrategy<E>
    int computeHashCode(E object);
    boolean equals(E object1, E object2);

You can't use a HashingStrategy with the built in HashSet or HashMap. GS Collections includes a java.util.Set called UnifiedSetWithHashingStrategy and a java.util.Map called UnifiedMapWithHashingStrategy.

Let's look at an example.

public class Data
    private final int id;

    public Data(int id)
        this.id = id;

    public int getId()
        return id;

    // No equals or hashcode

Here's how you might set up a UnifiedSetWithHashingStrategy and use it.

java.util.Set<Data> set =
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId));
Assert.assertTrue(set.add(new Data(1)));

// contains returns true even without hashcode and equals
Assert.assertTrue(set.contains(new Data(1)));

// Second call to add() doesn't do anything and returns false
Assert.assertFalse(set.add(new Data(1)));

Why not just use a Map? UnifiedSetWithHashingStrategy uses half the memory of a UnifiedMap, and one quarter the memory of a HashMap. And sometimes you don't have a convenient key and have to create a synthetic one, like a tuple. That can waste more memory.

How do we perform lookups? Remember that Sets have contains(), but not get(). UnifiedSetWithHashingStrategy implements Pool in addition to Set, so it also implements a form of get().

Here's a simple approach to handle case-insensitive Strings.

UnifiedSetWithHashingStrategy<String> set = 
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase));
Assert.assertEquals("ABC", set.get("aBc"));

This shows off the API, but it's not appropriate for production. The problem is that the HashingStrategy constantly delegates to String.toLowerCase() which creates a bunch of garbage Strings. Here's how you can create an efficient hashing strategy for case-insensitive Strings.

public static final HashingStrategy<String> CASE_INSENSITIVE =
  new HashingStrategy<String>()
    public int computeHashCode(String string)
      int hashCode = 0;
      for (int i = 0; i < string.length(); i++)
        hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i));
      return hashCode;

    public boolean equals(String string1, String string2)
      return string1.equalsIgnoreCase(string2);

Note: I am a developer on GS collections.

Answered by: Melissa436 | Posted: 01-03-2022

Answer 4

Trove4j has the feature I'm after and they call it hashing strategies.

Their map has an implementation with different limitations and thus different prerequisites, so this does not implicitly mean that an implementation for Java's "native" HashMap would be feasible.

Answered by: Samantha761 | Posted: 01-03-2022

Answer 5

Note: As noted in all other answers, HashMaps don't have an explicit ordering. They only recognize "equality". Getting an order out of a hash-based data structure is meaningless, as each object is turned into a hash - essentially a random number.

You can always write a hash function for a class (and often times must), as long as you do it carefully. This is a hard thing to do properly because hash-based data structures rely on a random, uniform distribution of hash values. In Effective Java, there is a large amount of text devoted to properly implementing a hash method with good behaviour.

With all that being said, if you just want your hashing to ignore the case of a String, you can write a wrapper class around String for this purpose and insert those in your data structure instead.

A simple implementation:

public class LowerStringWrapper {
    public LowerStringWrapper(String s) {
        this.s = s;
        this.lowerString = s.toLowerString();

    // getter methods omitted

    // Rely on the hashing of String, as we know it to be good.
    public int hashCode() { return lowerString.hashCode(); }

    // We overrode hashCode, so we MUST also override equals. It is required
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must
    // restore that invariant.
    public boolean equals(Object obj) {
        if (obj instanceof LowerStringWrapper) {
            return lowerString.equals(((LowerStringWrapper)obj).lowerString;
        } else {
            return lowerString.equals(obj);

    private String s;
    private String lowerString;

Answered by: David419 | Posted: 01-03-2022

Answer 6

good question, ask josh bloch. i submitted that concept as an RFE in java 7, but it was dropped, i believe the reason was something performance related. i agree, though, should have been done.

Answered by: Brianna802 | Posted: 01-03-2022

Answer 7

I suspect this has not been done because it would prevent hashCode caching?

I attempted creating a generic Map solution where all keys are silently wrapped. It turned out that the wrapper would have to hold the wrapped object, the cached hashCode and a reference to the callback interface responsible for equality-checks. This is obviously not as efficient as using a wrapper class, where you'd only have to cache the original key plus one more object (see hazzens answer).

(I also bumped into a problem related to generics; the get-method accepts Object as input, so the callback interface responsible for hashing would have to perform an additional instanceof-check. Either that, or the map class would have to know the Class of its keys.)

Answered by: Aida632 | Posted: 01-03-2022

Answer 8

This is an interesting idea, but it's absolutely horrendous for performance. The reason for this is quite fundamental to the idea of a hashtable: the ordering cannot be relied upon. Hashtables are very fast (constant time) because of the way in which they index elements in the table: by computing a pseudo-unique integer hash for that element and accessing that location in an array. It's literally computing a location in memory and directly storing the element.

This contrasts with a balanced binary search tree (TreeMap) which must start at the root and work its way down to the desired node every time a lookup is required. Wikipedia has some more in-depth analysis. To summarize, the efficiency of a tree map is dependent upon a consistent ordering, thus the order of the elements is predictable and sane. However, because of the performance hit imposed by the "traverse to your destination" approach, BSTs are only able to provide O(log(n)) performance. For large maps, this can be a significant performance hit.

It is possible to impose a consistent ordering on a hashtable, but to do so involves using techniques similar to LinkedHashMap and manually maintaining the ordering. Alternatively, two separate data structures can be maintained internally: a hashtable and a tree. The table can be used for lookups, while the tree can be used for iteration. The problem of course is this uses more than double the required memory. Also, insertions are only as fast as the tree: O(log(n)). Concurrent tricks can bring this down a bit, but that isn't a reliable performance optimization.

In short, your idea sounds really good, but if you actually tried to implement it, you would see that to do so would impose massive performance limitations. The final verdict is (and has been for decades): if you need performance, use a hashtable; if you need ordering and can live with degraded performance, use a balanced binary search tree. I'm afraid there's really no efficiently combining the two structures without losing some of the guarantees of one or the other.

Answered by: Kevin271 | Posted: 01-03-2022

Answer 9

There's such a feature in com.google.common.collect.CustomConcurrentHashMap, unfortunately, there's currently no public way how to set the Equivalence (their Hasharator). Maybe they're not yet done with it, maybe they don't consider the feature to be useful enough. Ask at the guava mailing list.

I wonder why it haven't happened yet, as it was mentioned in this talk over two years ago.

Answered by: Haris654 | Posted: 01-03-2022

Similar questions

java - JUnit theory for hashCode/equals contract

The following class serve as generic tester for equals/hashCode contract. It is a part of a home grown testing framework. What do you think about? How can I (strong) test this class? It is a good use of Junit theories? The class: @Ignore @RunWith(Theories.class) public abstract class ObjectTest { // For any non-null reference value x, x.equals(x) shou...

java - What are ways to keep hashCode/equals consistent with the business definition of the class?

Object javadocs and Josh Bloch tell us a great deal about how hashCode/equals should be implemented, and good IDEs will handle fields of various types correctly. Some discussion about all that is here. This question is about the next step: How do you make sure that they remain good? In particul...

java - Custom hashcode/equals operation for HashMap

Is there a an implementation of the HashMap class (or Map interface) that will allow me to use alternate hashcode and equals operations... Similar to how collections of the same type can be sorted in multiple ways using the Comparator in Collections.sort(list, comparator). I would like to avoid if possible, creating a key wrapper providing the desired hashcode and equals operations. In my case, one of...

java - Hashcode/Equals override with number range rather than direct equals?

Let's say I have an object that has a number range as two properties, a start and an end to define a numeric band. I want to load these objects into a HashMap. But when I look up on the hashcode and equals with a key object, I want to match on a given number that falls into the range. So I want the hashcode and equals to take any number in a key, and return the object where it falls between the startRange and endRange. So ...

java - Does the compiler, or JVM, enforce the hashCode/equals contract?

The object I'm storing in the HashMap as the key overrides equals() but not hashCode(); When I put an object in the map, the equals() method is not being invoked. If I also override hashCode(), the equals() method is invoked. Why is that? Why am I unable to utilize a custom equals method, to possibly prevent the addition of an object to a map, regardless of whether I override hashCode()? Thanks.

java - HashMap returning null even though hashCode/equals are overriden

I have a HashMap that maps a custom object TokenDocumentPair to a Double. The TokenDocumentPair is as follows: static class TokenDocumentPair { int documentNum; String token; public TokenDocumentPair(String token, int documentNum) { this.token = token; this.documentNum = documentNum; } public boolean equals(TokenDocumentPair other) { ...

java - Intellij Plugin to generate getter/setter, hashcode/equals, toString

Hi is there any plugin for IntelliJ, which can generate getter/setter, hashcode/equals, toString in one click?

Still can't find your answer? Check out these amazing Java communities for help...

Java Reddit Community | Java Help Reddit Community | Dev.to Java Community | Java Discord | Java Programmers (Facebook) | Java developers (Facebook)