Skip to content
Tags

,

Java 6,7,8 HashMap collisions

June 3, 2013

In an earlier post, I wrote about how Java 6 hashing for Strings in HashMaps could easily be attacked by reasoning about the source code. In this post, I provide some code examples, and performance numbers.

First, we need to be able to generate a list of Java Strings that compute the same String.hashCode(). Simply run the code below and pipe the output to a file. e.g. java StringHashCollisionGenerator 1000000 > collisions.txt

Now your collisions.txt file will contain exactly the number of strings you requested with the same hash code. Now to test how HashMap performs in each JVM use the following code. Run the code below as follows: java HashMapVictim < collisions.txt

Below are 4 different test results all using 65,536 Strings. 1) JDK 6_45 2) JDK7_21 3) JDK7_21 w/JVM property jdk.map.althashing.threshold=1 and 4) JDK 8b92

As you can see from the results below, Java 6 is definitely susceptible to this attack. Java 7 is also susceptible by default, however it can be saved by enabling “alternate hashing” with jdk.map.althashing.threshold=1. And finally, Java 8 has this behavior as the only option.

The primary distinction here is that hash codes are permitted to change for the same string between JVM invocations, but in Java 6 and default Java 7 they simply don’t.

> time /System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/bin/java HashMapVictim < collisions.txt
real 2m7.792s
user 2m4.845s
sys 0m0.451s

> time /Library/Java/JavaVirtualMachines/jdk1.7.0_21.jdk/Contents/Home/bin/java HashMapVictim < collisions.txt
real 2m48.456s
user 2m47.581s
sys 0m0.467s

> time /Library/Java/JavaVirtualMachines/jdk1.7.0_21.jdk/Contents/Home/bin/java -Djdk.map.althashing.threshold=1 HashMapVictim < collisions.txt
real 0m0.794s
user 0m1.175s
sys 0m0.088s

> time /Library/Java/JavaVirtualMachines/jdk1.8.0.jdk/Contents/Home/bin/java HashMapVictim < collisions.txt
real 0m0.805s
user 0m1.163s
sys 0m0.087s
Advertisements

From → Java

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: