Finding hash collisions in Java Strings

In ##java, a question came up about generating unique identifiers based on Strings, with someone suggesting that hashCode() would generate generally usable numbers, without any guarantee of uniqueness. However, duplicate hash codes can be generated from very small strings, with ordinary character sets – see this stackoverflow answer – and therefore I thought it’d be interesting to find other short strings with the same hash values.
It was discussed how prone to collisions the Strings hashCode() method is, especially when using small strings. You would naturally assume a hashCode with an int as result – and thus 2 billion possible values – will be unique for small and simple strings.
Here’s a simple class to demonstrate this:

package org.javachannel.collisions;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
* Simple example class to show amount of hashCode collisions in Strings.
* TODO: Make the number of characters and the character set to be more
* configurable
* @author Michael Stummvoll
public class HashCodeCollision {
  public static void main(String[] args) {
    Map<Integer, List<String>> hashMap = new HashMap<>();
    String str = "abcdefghijklmnopqrstuvwxyz";
    str += str.toUpperCase();
    for (char c1 : str.toCharArray()) {
      for (char c2 : str.toCharArray()) {
        // for (char c3 : str.toCharArray()) {
        String s = c1 + "" + c2; // + "" + c3;
        int code = s.hashCode();
        if (!hashMap.containsKey(code)) {
          hashMap.put(code, new ArrayList<String>());
      // }
  int collisions = 0;
  int max = 0;
  List<String> maxList = null;
  for (Entry<Integer, List<String>> e : hashMap.entrySet()) {
    List<String> l = e.getValue();
    if (l.size() > max) {
      max = l.size();
      maxList = l;
    if (l.size() > 1) {
      System.out.println("Collision: " + l);
  System.out.println("collisions found: " + collisions);
  System.out.println("biggest collision: " + maxList);

This reveals that in all permutations of 2 letter strings consisting of letters we already have 1250 collisions (with two strings for each given hash code). When using 3 letter strings, we’d see that we have 37,500 collisions with up to four strings per hash code.
When reviewing the implementation of String‘s hashCode() method, you can conclude that it’s very easy to provoke collisions both ways, both intentionally and accidentally. So you shouldn’t rely on hash codes being unique for your Strings.

First steps: Structure of your first source file

This is what a class file ought to look like when you take your first steps writing java programs:

public class YourAppNameHere {
  public static void main(String[] args) {
    new YourAppNameHere().go();
  private String iAmAField;
  void go() {
    System.out.println("Your code goes here!");
  void someOtherMethod() {
    // You can call this method from 'go' with: someOtherMethod()
    iAmAField = "Hello, World!";

In particular, copy/paste the main() method verbatim and don’t touch it. If you need access to the command line arguments, pass the args parameter directly to your go method, and update the go method to take String[] args as parameter.

Editor’s note: Another way of handling arguments is to use JCommander, which itself encourages the kind of object design in this post.

Why should you do it this way? The short answer is: Because main() has to be static, but the idea of static is advanced java. You will and should learn about it in time, but trying to explain it to you (so that you don’t make mistakes because you don’t understand what that means) as you take your first steps is a bit like teaching you about the fuel gauge during your first drive. It’s just not that interesting, and you don’t need to know about it to start taking your first steps. It’ll become much more obvious once you’ve done some exercises. This main() method will get you out of static immediately so that you can ignore its existence until the time comes to learn about what it’s for.

Guava's Equivalence: strategy for equals()/hashCode()


Given a class C, if you want to implement ordering, you have two choices:

  1. Have your class implement Comparable<c> (or Comparable<x>, where X is a superclass of C).
  2. Define a Comparator<c> to use with this class (or a Comparator<x>, where X is a superclass of C).

In fact, many classes in the JDK will have you supply a Comparator if your class does not implement Comparable; examples include Collections.sort() and Arrays.sort().
It can be said that for a given class C, a Comparator defines a strategy for ordering, and that you need to supply a Comparator if the class itself does not define this strategy (that is, does not implement Comparable).
And while the JDK offers a means to provide different strategies for ordering, it does not do so for a more fundamental contract of Object: equals() and hashCode().
And this is where Guava comes in.

Equivalence: a strategy for Object’s `equals()` and `hashCode()`

Guava’s Equivalence intends to fill this gap. In the same vein as a Comparator, using an Equivalence allows you to either define a different equals()/hashCode() strategy than the one already defined by your target class, or to define one for a target class which “has none at all” (meaning, in this case, that the class uses Object‘s equals()/hashCode() implementations).

Usage part 1: implementing an Equivalence

Equivalence is a parameterized class; for a class C, you will need to implement two methods:

  • doEquivalent(C a, C b): given two instances a and b of class C, are those two classes considered equivalent? This is really like writing an implementation of equals() for class C, except that you don’t have to handle nulls (it is guaranteed that both parameters are non-null) nor casts (it is guaranteed that both arguments are “at least” of type C).
  • doHash(C t): given an instance t of class C, compute a hash value. Of course, an implementation must mirror Object‘s hashCode()/equals() contract: if doEquivalent(a, b) is true, then doHash(a) == doHash(b).

Note that it is guaranteed that arguments to these methods will never be null.

Usage part 2: “out of Collections” usage

There is really only one method you will need here: .equivalent(). Provided you want to test equivalence between two instances of a given class C, you will do:

final C a = ...;
final C b = ...;
final Equivalence<C> eq = ...;
// Test equivalence of a and b against equivalence stragey eq
if (eq.equivalent(a, b)) {
    // Yup, they are

Usage part 3: Collection usage

Unlike the Comparable/Comparator relationship, equivalence between objects has to be “engraved” into collections. This unfortunately means that the syntax to initiate a collection is somewhat on the verbose side. Namely, if you want to initiate a Set of elements of class C wrapped into an Equivalence, you will have to initialize it as such:

// Java 7 and better...
Set<Equivalence.Wrapper<C>> set = new HashSet<>();
// Java 5 or 6; and since we use Guava...
Set<Equivalence.Wrapper<C>> set = Sets.newHashSet();

You will also need to rely on an Equivalence implementation in order to interact with this collection (of course, you also need to ensure that you use the same implementation all along!):

// Your Equivalence...
Equivalence<C> eq = ...;
// Inserting an element c into a Set<Equivalence.Wrapper<C>> set
// Removing, testing...
// Retrieve the original element
C element;
for (final Equivalence.Wrapper<C> wrapped: set) {
    // get the original element
    element = wrapped.get();
    // do something with element


Admittedly, having to redefine an equivalence strategy is far less common than having to redefine an ordering strategy. It is, however, a welcome tool to use when you have to deal with a “foreign” class which doesn’t meet your equals()/hashCode() expectations, either because there is no implementation at all for this class, or because the existing implementations don’t suit your needs.
Happy coding!

PriorityQueue and mutable item behavior

From today, in Java: a user asked if changing the value of an item in a PriorityQueue would still result in the queue being correctly ordered. (He explained that he was doing this to prioritize based on counters, which makes sense. It’s worth noting that this blog entry is not about solving his problem, but about the behavior of PriorityQueue.)
Getting items out of a PriorityQueue requires peek() and/or poll(). Let’s take a look at some simple usage; first, let’s look at an object that represents something with a priority:

class Container implements Comparable {
  int x;
  public Container(int x) { this.x = x; }
  public int getX() { return x; }
  public void setX(int x) { this.x = x; }
  public String toString() { return "Container{" + "x=" + x + '}'; }
  public int compareTo(Container o) {
    return, o.getX());

Let’s use this from another class. First, a utility method that builds a Queue, returning one element from the Queue for us to mutate later:

private static Container buildQueue(Queue q) {
  q.add(new Container(4));
  q.add(new Container(2));
  q.add(new Container(6));
  Container c = new Container(5);
  return c;

As stated, we need to use peek() or poll() to get results out in correct order. If we use normal iteration, our order starts off correctly, but fails immediately. Here’s the code:

for(Container c1:q) {

And the output is:


The first element is in the right place – we expect 2 as the highest priority – but the others are in insertion order, not actual priority order.
If, however, we use poll(), we get different results. The code:

while((c=q.poll())!=null) {

And the output:


What poll() does is simple: it removes the head of the Queue – the item with priority – and then it sifts the queue, with the result that the Queue‘s order is adjusted. Depending on the nature of the queue, this may put it in proper order all the way through the queue, but this is not required — the actual result is that the Queue is more ordered, with the new head of the Queue (the result of the next poll() or peek()) being set properly.

If you want to see the actual code for this process, grepcode has it: see PriorityQueue.poll(). Internally, “sift” is the actual term used.

Mutating the Elements in the Queue

What happens if we mutate the priority, then?
As it turns out, the behavior of the Queue doesn’t change much – except that the results of the last sifting of the Queue are maintained. This is actually a big deal. poll() doesn’t sift the Queue before returning the head of the queue. Therefore, if this is our code:

Container container = buildQueue(q);
System.out.println("1: "+q);
System.out.println("2: "+q);
while((c=q.poll())!=null) {
1: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=5}]
2: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=3}]

Note what happens: we modify the last element in the Queue to be 3, and the Queue maintains its order, but pulling the results out via poll() gives us the results as we expect. But if we change the priority of the last element such that it should be first… let’s see what that looks like.

container = buildQueue(q);
System.out.println("1: "+q);
System.out.println("2: "+q);
while((c=q.poll())!=null) {

Our output is:

1: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=5}]
2: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=1}]


As stated, PriorityQueue sifts its values after pulling the top element from the Queue. It’d be unwise to expect a Queue to work properly with mutable items in any case – much as using mutable keys in a Map would be unwise – but as you can see, mutating the priorities can work but can also fail if you happen to modify the priorities such that the element at the head of the list should change.

Catching (and implementing) exceptions


In a previous article on Using exceptions correctly, exception propagation was explained: use runtime exceptions for situations in which the code is incorrect, and use checked exceptions for situations for which there is a valid recovery path internal to the application.
This article deals with two other things you will have to do with exceptions: catching them and implementing them. And in order to do both, you have to know about exception classes themselves…

Java’s Exception Classes

At the core of all exceptions is a class called Throwable. It is the superclass for both Exception and Error. (OutOfMemoryError is an example of an Error.)
The truth of the matter is you should probably never encounter code which directly handles (or throws!) a Throwable which is not also an Exception, but you should know that it exists. You never know: some inexperienced programmer might add it to his or her exception handling, and then you’d have to clean up their code.
The Exception class itself is the base class for all checked exceptions. When you want to create custom exceptions, you will probably want to extend this one (or a more specialized version: IOException, for instance).
The RuntimeException class Is the base class for all unchecked exceptions. If you browse the JDK javadoc, you will notice that all such niceties as the infamous NullPointerException (NPE for short), but also IllegalArgumentException, IndexOutOfBoundsException, etc., are all subclasses of RuntimeException.
But there’s a catch (pun intended): RuntimeException is also a subclass of Exception. This has an often overlooked consequence on catch statements, see below.

Catching, and the importance of exception inheritance

Since exceptions are Java classes like any other, exception classes which you can catch may inherit from other exception classes. This has an influence on how you catch them. For starters…

Catch more specific exceptions first

Let us take an example of a method doing filesystem operations using the java.nio.file API. Such operations can fail at two levels:

  • Filesystem-level errors; the exception defined by the JDK for such errors is FileSystemException.
  • I/O errors; in this case you will probably get an IOException instead.

From the javadoc links above, you may have noticed that FileSystemException inherits IOException. Provided you want to treat both exceptions differently, you must catch FileSystemException first:

try {
} catch (FileSystemException e) {
    // deal with filesystem level errors
} catch (IOException e) {
    // deal with I/O errors

As an added benefit, you get to access all methods defined in FileSystemException (getFile(), etc) which IOException does not define, allowing you to (for instance) construct much more detailed error messages.
If, instead, your code was:

try {
} catch (IOException e) {
    // deal with it
} catch (FileSystemException e) {

As explained, you will never get to deal with FileSystemExceptions separately – the more general IOException will match and its exception-handling block called, instead.

Catching Exception is dangerous…

Remember what was said earlier? RuntimeException inherits Exception. As such, if you simply catch Exception, you also get to catch all unchecked exceptions!
You don’t want to do that, of course… But just in case, if you want to (or, preferrably, need to) have a “one size fits all” catch block, here is an idiom you can use which will “correctly” propagate all unchecked exceptions (reminder: since they are unchecked, you needn’t declare that your method throws them):

try {
    // some exception-heavy code throwing many exceptions
} catch (RuntimeException oops) {
    // Unchecked exception: rethrow!
    throw oops;
// deal with specific exceptions if possible...
// then:
catch (Exception e) {
    // One size fits all

Well, that’s one idiom; a better way to deal with exception-heavy code is to simply reduce the amount of code in your try blocks so that the amount of exceptions you have to deal with is limited.
Alternatively, you can use multicatch.

“Multicatch” (since Java 7)

Editor’s Note: if you’re not on Java 7 by now, you should attempt to upgrade. Java 6 has been end-of-lifed, and it has a support lifecycle that’s not likely to be available for most users. Java 7’s been out for years, people. It’s time.

Again, in the situation where you have to deal with “exception-heavy” try blocks, you have another tool since Java 7 allowing you to treat a given set of exceptions with the same code. So, instead of, for instance, writing:

try {
    // something
} catch (E1 e) {
    // do x with e
} catch (E2 e) {
    // do x with e
// etc

You can instead write:

try {
    // something
} catch (E1 | E2 e) { // | E3 | ...
    // do x with e

Implementing your own exceptions: some rules

Exceptions are regular Java classes. This means that there is more to exception classes than .getMessage(), as we saw with FileSystemException.
Therefore, if you feel the need to, do not hesitate to add methods to your custom exception classes.
However, try to avoid extending Exception directly. The JDK defines plenty of exception classes which can serve as a useful basis for your own exception classes; for instance, if you want to relay an I/O error of your own, you will probably want to extend IOException instead.
Double check whether the exception class you extend inherits RuntimeException… If it does, you have just created an unchecked exception class. Is this what you want?

Side note: implementing “throwing methods”…

When implementing a method which is declared to throw an exception class, the implementation can choose to throw a subclass of this exception. So, for instance, if you have an abstract method to implement declared as:

// Reminder: all declared methods in an interface are "public abstract" by default
void foo() throws SomeException;

… and you have a custom exception MyException which extends SomeException, then you can implement it as such:

// Note the declared exception...
void foo() throws MyException { /* whatever */ }

This is demonstrated by the JDK with AutoCloseable and Closeable: Closeable extends AutoCloseable. The close() method of AutoCloseable is declared to simply throw Exception, whereas its override in Closeable is declared to throw IOException.

Final words…

Hopefully, this article and the quoted article in the introduction should have provided you with enough tools, knowledge and recipes so that you are confident when it comes to dealing with exceptions in Java — whether that be in your own code, or when using other people’s code.
Happy (and fruitful) coding…

Use exceptions correctly

In this article we are going to address the common misuse of exceptions, more specifically those times when programmers fail to correctly propagate exceptions. Along the way, and most of this article, we will talk about the differences between runtime and checked exceptions and the ways in which it is appropriate to use them.

Runtime exceptions

There are two main differences between checked, or “normal,” exceptions, and runtime exceptions:

  • Runtime exceptions don’t have to be mentioned in a method’s signature, and the compiler doesn’t warn about them.
  • The compiler doesn’t require that runtime exceptions are caught.

This means that when a runtime exception is thrown it has the potential to propagate to the JVM without any prior warning, thus crashing the application. This makes runtime exceptions bad for managing errors that are recoverable, and great for failing the application for errors that are irrecoverable such as defective code.

Checked exceptions

Checked exceptions are different from runtime exceptions in that:

  • Checked exceptions have to be mentioned in a method’s signature.
  • Checked exceptions have to be caught, or the code will not compile. (Exception handling is forced by the specification and compiler.)

This means that checked exceptions never propagate up to the JVM and cannot crash your application unless you have deliberately allowed it by including them in your main method’s signature. This makes checked exceptions great for managing errors that are recoverable, and bad for errors that are irrecoverable. Who would want to keep catching exceptions that they can do absolutely nothing about? (Answer: nobody.)

The meaning of “recovery” from errors

“Recovery” means different things to different people (and situations, and applications).
Imagine that we are trying to connect to a server and the server is not responding. It’s possible to recover from the resulting exception by connecting to a different server, given that it has the same capabilities of the server to which we originally tried to connect.
This will achieve the original goal, thus we have recovered from the error.
This is not exactly what recovery means in this context — if it’s possible to make such recovery as was mentioned in the illustration, then by all means you should do it.
However, recovery could also be displaying an alert dialog to the user that describes the incident, or perhaps sending an email to an administrator, or even simply logging the error to a log file. All of these options qualify as ‘recovery’ – taking a valid and known course of action in the event of an exception.

Using the correct exception type

With this information about the nature of exceptions and a workable definition of “recovery” in mind, the de facto standards in industry regarding exception handling make sense, and have evidently been practiced in the JVM and the Java runtime library itself:

  • If the cause of the error is because the code is incorrect, throw a runtime exception.
  • If the cause of the error is because of state while the code is correct, throw a checked exception.

The reason for this is that if the code is correct, the matter is very likely to be recoverable.
Examples include situations where you try to connect to a server without an internet connection — there is no need to crash the app. A gentle way to deal with the error is to display an error dialog that explains what happened, allowing the user to fix their connection, given a clear enough message.
If the error is in the code, and the program itself is defective, then writing a recovery path is irrelevant — how can you recover from a problem that you don’t even know exists yet? Or if you do know what the problem is, then why write a recovery path at all instead of fixing the problem?
Runtime exception examples
The following is an error for which a runtime exception is appropriate:

float nan = 1 / 0;

This will throw a division by zero exception. It is appropriate because the only means of fixing this issue is to modify the code, it is not dependent on any external state.
Here’s another example, a portion of HashMap‘s constructor:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    // more irrelevant code

In the case presented above it is also appropriate to throw runtime exceptions, because it is not logically sound to construct a hash map with negative capacity, or a load factor that is not a positive number. This error is not due to something that was transmitted over the network, the state of a file or the disk, user input, or any other external state — it’s because a calculation is wrong, or the flow is inappropriate in that it permitted these values. Either way — it’s the code that has to be fixed.
Checked exception example
The following is a rather common example of “exception handling,” often written by programmers who think that they’re following Spring‘s example:

public Data dataAccessCode(){
    try {
        // ..some code that throws SQLException
    } catch(SQLException ex) {
        throw new RuntimeException(ex);

Honestly, the frustration of a person who would take part in such an abomination is understandable. What can they possibly do in that method to deal with an SQL exception? It’s an exception in the database, there are no means of “recovery,” and this scope is probably incapable of accessing the UI to display an error dialog. Some more sophisticated evil-doers solve this by doing something of this sort:

public Data dataAccessCode() {
    try {
        // ..some code that throws SQLException
    } catch(SQLException ex) {
        // TODO: add internationalization?
          "We don't know what you're trying to do, but uhh, can't access data. Sorry.", ex);

This does perform a certain effort at recovery, however it may not always be the correct recovery that is appropriate for the grander scheme, nor is it necessary evil. The correct way to solve this is to simply not handle the exception in this scope, and propagate the exception:

public Data dataAccessCode() throws SQLException {
    // ..some code that throws SQLException

This way, the code is not even “uglified” and it allows for the possibility of recovery by the caller, which is more aware of the grander scheme of things:

public void loadDataAndShowUiBecauseUserClickedThatButton() {
    try {
        Data data = dataAccessCode();
    } catch (SQLException e) {
        // This method’s scope can do UI, so we don't need sorcery to show an error dialog.
        // messages is an internationalized ResourceBundle.

Ending notes

Exceptions are a wonderful feature; it is worthwhile to use them. Don’t invent your own ways to handle and propagate errors; you’ll have less trouble and better results if you stick to the idiom instead of fighting with the platform that you are using.

Code Complexity

This morning, a user asked a question about determining the equality of three values on ##java. The code he offered as a test was as follows, roughly:

boolean a=false, b=false, c=false;
System.out.println(a == b == c);

Rather than determining if the three values are equivalent, this code checks to see if a is the same as b – with the result of true – and then checks to see if this result is the same as c – so it tries to see if a == b is false. It’s not, so the result of the expression is false. The disassembled code shows it, too:

       0: iconst_0
       1: istore_1
       2: iconst_0
       3: istore_2
       4: iconst_0
       5: istore_3
       6: getstatic     #2    // Field java/lang/System.out:Ljava/io/PrintStream;
       9: iload_1
      10: iload_2
      11: if_icmpne     18
      14: iconst_1
      15: goto          19
      18: iconst_0
      19: iload_3
      20: if_icmpne     27
      23: iconst_1
      24: goto          28
      27: iconst_0
      28: invokevirtual #3    // Method java/io/PrintStream.println:(Z)V
      31: return

This is all well and good, and the original poster was shown code that would work: (a==b && b==c). However… there were other solutions offered. They include:

  • (a == b) == c
  • (a ^ b) == c
  • a ^ b ^ c
  • isSame(a,b,c)

All together now: ugh.
But why? Which ones of those work? Which ones don’t work? (You should probably try to give this some thought before continuing. Be honest with yourself about your answers: nobody else is watching.)
It doesn’t matter.
The reason comes down to code complexity. The simplest solution (a==b && b==c) lacks a certain elegance, I suppose: it’s very straightforward and very, very simple. The other solutions appeal to a certain mentality, the one that says that you have to know something to use this code; you have to think about them some.
You might not have to think much – but only one has the chance of being right, the isSame() method, and that assumes it works properly.
Smart coders will code simply; gauge code by the reward it should give. isSame(), if it accepts multiple types of sequences and has variable arity, might be okay if you can reuse it in multiple scenarios (and it’s needed quite a bit in your code, I guess) — but the others are too complex to really pass a good code review.

Tags on

Articles on are going to start using Odersky’s “Scala Levels” as tags for new content (with old content being rated as they get maintained over time, possibly).
The levels are in two groups: A1, A2, A3, and L1, L2, and L3. The “A” stands for “application;” the “L” stands for “library.” Put simply, the features that tend to be found in applications and libraries are different; an application can prefer concrete types, whereas a library tends not to (if able); the skills and knowledge for writing applications or libraries are different.
An A1 programmer is a beginner at Java; an L3 programmer is expected to really know the language and its features well.
The skills are grouped like: A1, A2/L1, A3/L2, L3. The idea being expressed here is that before you should design a library, you need to be moderately skilled at Java – a beginner shouldn’t bother worrying about expressing ideas in a library.
Odersky actually grouped concepts for Scala in each level (for which he’s gotten some scathing criticism from Tony Morris, for example); eventually, I’d like to have the same kind of groupings for Java, if only to establish a baseline (which is what Odersky was doing, and what Morris apparently missed, in his quest for overreaction. Tony’s a brilliant guy, but like so many other brilliant people in this field, he’s desperate to find points of contention, and then wring them dry. Astute readers might note that Tony’s critique has no way through which to offer commentary…)
So: What you’ll start seeing is tips on being grouped by these levels by tags; the higher the level, the more complex the content is.