Java Map keys should always be Comparable
Tags: java, programming, security
Published: 2018-09-15 02:37:32

---
title: Java Map keys should always be Comparable
published: true
description: If you implement equals() and hashCode(), you should also implement compareTo().
tags: java,programming,security
---

This article is inspired by the discovery years ago that an attacker could manipulate query parameters to turn the map data structure in many web servers into a linked list, by making all the parameter names end up in the same hash bucket, which CVE-2018-0875 reminded me of. You can read about the original discovery in CERT [VU#903934](https://www.kb.cert.org/vuls/id/903934) and the original post in the [Full Disclosure list archives](https://seclists.org/fulldisclosure/2011/Dec/477), or on [YouTube from 28c3](https://www.youtube.com/watch?v=R2Cq3CLI6H8).

In Java, for example, the strings `"fg"`, `"gH"` and `"h)"` all have a hash code of 3265, so an attacker can build query strings like `fgfg=0&fggH=0&fgh)=0&gHfg=0` and so on to waste the server’s time and mount an effective denial of service. It’s not that hard to defend against; I know Jetty still limits form content to 200KB and 1,000 keys, and other servers have similar limits.

Java itself implemented a defense in the `String` class early in the Java 7 releases, described in the [Collections Framework Enhancements in Java 7](https://docs.oracle.com/javase/7/docs/technotes/guides/collections/changes7.html). The `String` class gained a new [`hash32`](http://hg.openjdk.java.net/jdk7u/jdk7u6/jdk/file/8c2c5d63a17e/src/share/classes/java/lang/String.java#l3078) method and field which used MurmurHash3 with a random seed. This is fine for strings and `HashMap`s, but not so good for custom keys.

A better approach was implemented in [JEP 180](http://openjdk.java.net/jeps/180) for Java 8. Now, if too many hash codes map to the same bucket in the map, the list of entries can be changed into a balanced binary tree, sorted first by hash code and then by each key’s `compareTo` method, as long as the keys are `Comparable`. This is obviously the case for strings (and is special-cased in `HashMap`), but it should also be the case for _every_ class used as a map key, especially if the data is potentially supplied by a hostile user.

## Implementing Comparable

It’s straightforward to implement `equals()` and `hashCode()` correctly for a data class, if a bit verbose:

```java
public final class SearchKey {
    private final String site;
    private final long userId;
    private final String query;

    public SearchKey(String site, long userId, String query) {
        this.site = Objects.requireNonNull(site);
        this.userId = userId;
        this.query = Objects.requireNonNull(query);
    }

    // getters ...

    @Override
    public int hashCode() {
        return (site.hashCode() * 31 + Long.hashCode(userId)) * 31 + query.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof SearchKey)) {
            return false;
        }
        SearchKey other = (SearchKey) obj;
        return userId == other.userId && site.equals(other.site) && query.equals(other.query);
    }
}
```

(I use 31 as the multiplier in the hash code because it’s prime, and `x * 31` can be optimised to `(x << 5) - x` to be much faster on some platforms.)

As above, the same hash code can be generated for different values, like `new SearchKey("fg", 12345, "fg")`, `new SearchKey("fg", 12345, "gH")` and `new SearchKey("gH", 12345, "fg")`, which all hash to 3,523,625. If we used these as keys in a map-based cache, an attacker could mount a denial-of-service attack by making many queries to our service that use the same hash.

The `compareTo` method can be implemented by tediously comparing fields one by one:

```java
public final class SearchKey implements Comparable<SearchKey> {
    // ...

    @Override
    public int compareTo(SearchKey o) {
        int c = site.compareTo(o.site);
        if (c != 0) {
            return c;
        }
        c = Long.compare(userId, o.userId);
        if (c != 0) {
            return c;
        }
        return query.compareTo(o.query);
    }
}
```

But from Java 8, it can be implemented more concisely:

```java
public final class SearchKey implements Comparable<SearchKey> {
    private static final Comparator<SearchKey> COMPARATOR =
        Comparator.comparing(SearchKey::getSite)
            .thenComparingLong(SearchKey::getUserId)
            .thenComparing(SearchKey::getQuery);

    // ...

    @Override
    public int compareTo(SearchKey o) {
        return COMPARATOR.compare(this, o);
    }
```