Check if a HashMap key is Comparable

Context: Java Map keys should always be Comparable - DEV Community

HashMap key types should be Comparable.

In short: Non-comparable key types of a HashMap are vulnerable to DoS attacks, see VU#903934 - Hash table implementations vulnerable to algorithmic complexity attacks

Since java 8 and JEP180 this issue can be solved by implementing the Comparable interface on classes that are used as a key of a HashMap.

Hello @MahatmaFatalError,

While it is correct that implementing Comparable helps in case of higher collision rate of hashCode, it might be unnecessary for types used as keys that are properly implemented.

We would need to raise an issue when a given type T:

  • Is used as a key in a Map
  • Has a custom hashCode implementation
  • Does not implement Comparable

What do you think?

If I got it correctly, even the default impl of hashCode is vulnerable. So I would discard your second point.

Actually, I would add a condition that checks that the content of the key can be set from the outside (i.e. vulnerability is exposed and attackable), however, I doubt that this can be verified appropriately.

Indeed, removing the constraint on custom hashCode implementation would make sense.

As for checking for possible modifications from the outside, that is a bit too broad a scope for the rules we typically implement.

A ticket has been created for the new rule.

1 Like