Skip to content

Instantly share code, notes, and snippets.

@ecki

ecki/HashMapCollision.java

Last active August 29, 2015 14:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ecki/9f69773eb29428a36077 to your computer and use it in GitHub Desktop.
Save ecki/9f69773eb29428a36077 to your computer and use it in GitHub Desktop.
Download ZIP
JMH Hash test
Raw
HashMapCollision.java
package net.eckenfels.jmhtest.hash;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
// java source level 1.6
@State(Scope.Thread)
@Warmup(iterations=2,time=10,timeUnit=TimeUnit.SECONDS)
@Measurement(iterations=4,time=20,timeUnit=TimeUnit.SECONDS)
@Fork(1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class HashMapCollision {
final static int max_k1 = 500;
final static int max_k2 = 500;
final static int GOOD_HASH = 507;
final static int BAD_HASH = 37;
Random random = new Random(0);
@Param({"16", "1000", "100000"})
int initialSize;
@Benchmark
public Map<NodeNoComp, NodeNoComp> badDistNoComp() {
Map<NodeNoComp, NodeNoComp> map = new HashMap<NodeNoComp, NodeNoComp>(initialSize);
for (int i = 0; i < 10000000; i++) {
NodeNoComp key = new NodeNoComp(random.nextInt(max_k1), random.nextInt(max_k2), BAD_HASH);
NodeNoComp val = map.get(key);
if (val == null)
map.put(key, key);
}
return map;
}
@Benchmark
public Map<NodeComp, NodeComp> badDistWithComp() {
Map<NodeComp, NodeComp> map = new HashMap<NodeComp, NodeComp>(initialSize);
for (int i = 0; i < 10000000; i++) {
NodeComp key = new NodeComp(random.nextInt(max_k1), random.nextInt(max_k2), BAD_HASH);
NodeComp val = map.get(key);
if (val == null)
map.put(key, key);
}
return map;
}
@Benchmark
public Map<NodeNoComp, NodeNoComp> goodDistNoComp() {
Map<NodeNoComp, NodeNoComp> map = new HashMap<NodeNoComp, NodeNoComp>(initialSize);
for (int i = 0; i < 10000000; i++) {
NodeNoComp key = new NodeNoComp(random.nextInt(max_k1), random.nextInt(max_k2), GOOD_HASH);
NodeNoComp val = map.get(key);
if (val == null)
map.put(key, key);
}
return map;
}
@Benchmark
public Map<NodeComp, NodeComp> goodDistWithComp() {
Map<NodeComp, NodeComp> map = new HashMap<NodeComp, NodeComp>(initialSize);
for (int i = 0; i < 10000000; i++) {
NodeComp key = new NodeComp(random.nextInt(max_k1), random.nextInt(max_k2), GOOD_HASH);
NodeComp val = map.get(key);
if (val == null)
map.put(key, key);
}
return map;
}
private static class NodeNoComp {
private final int k1;
private final int k2;
private final int hashFactor;
public NodeNoComp(int k1, int k2, int factor) {
this.k1 = k1;
this.k2 = k2;
this.hashFactor = factor;
}
@Override
public int hashCode() {
int result = 17;
result = hashFactor * result + k1;
result = hashFactor * result + k2;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!(obj instanceof NodeNoComp))
return false;
NodeNoComp other = (NodeNoComp) obj;
return k1 == other.k1 && k2 == other.k2;
}
}
private static class NodeComp implements Comparable<NodeComp> {
private final int k1;
private final int k2;
private final int hashFactor;
public NodeComp(int k1, int k2, int factor) {
this.k1 = k1;
this.k2 = k2;
this.hashFactor = factor;
}
@Override
public int hashCode() {
int result = 17;
result = hashFactor * result + k1;
result = hashFactor * result + k2;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!(obj instanceof NodeComp))
return false;
NodeComp other = (NodeComp) obj;
return k1 == other.k1 && k2 == other.k2;
}
@Override
public int compareTo(NodeComp o)
{
if (k1 < o.k1)
return -1;
else if (k1 > o.k1)
return +1;
else if (k2 < o.k2)
return -1;
else if (k2 > o.k2)
return +1;
return 0;
}
}
}
Raw
result.txt
Windows 7 x64 on Core i7 Q720 1,6GHz:
java version "1.7.0_72"
Java(TM) SE Runtime Environment (build 1.7.0_72-b14)
Java HotSpot(TM) 64-Bit Server VM (build 24.72-b04, mixed mode)
Benchmark (initialSize) Mode Samples Score Error Units
n.e.j.h.HashMapCollision.badDistNoComp 16 avgt 4 10847,318 ± 5596,690 ms/op
n.e.j.h.HashMapCollision.badDistNoComp 1000 avgt 4 10854,908 ± 5607,831 ms/op
n.e.j.h.HashMapCollision.badDistNoComp 100000 avgt 4 10850,451 ± 4702,399 ms/op
n.e.j.h.HashMapCollision.badDistWithComp 16 avgt 4 10761,430 ± 5376,975 ms/op
n.e.j.h.HashMapCollision.badDistWithComp 1000 avgt 4 10796,408 ± 4736,724 ms/op
n.e.j.h.HashMapCollision.badDistWithComp 100000 avgt 4 10828,842 ± 5299,540 ms/op
n.e.j.h.HashMapCollision.goodDistNoComp 16 avgt 4 3613,923 ± 254,823 ms/op
n.e.j.h.HashMapCollision.goodDistNoComp 1000 avgt 4 3666,860 ± 524,511 ms/op
n.e.j.h.HashMapCollision.goodDistNoComp 100000 avgt 4 3531,277 ± 312,273 ms/op
n.e.j.h.HashMapCollision.goodDistWithComp 16 avgt 4 3656,229 ± 274,350 ms/op
n.e.j.h.HashMapCollision.goodDistWithComp 1000 avgt 4 3597,400 ± 236,908 ms/op
n.e.j.h.HashMapCollision.goodDistWithComp 100000 avgt 4 3553,777 ± 411,838 ms/op
java version "1.8.0_25"
Java(TM) SE Runtime Environment (build 1.8.0_25-b18)
Java HotSpot(TM) 64-Bit Server VM (build 25.25-b02, mixed mode)
Benchmark (initialSize) Mode Samples Score Error Units
n.e.j.h.HashMapCollision.badDistNoComp 16 avgt 4 14309,880 ± 1811,709 ms/op
n.e.j.h.HashMapCollision.badDistNoComp 1000 avgt 4 14307,280 ± 1734,091 ms/op
n.e.j.h.HashMapCollision.badDistNoComp 100000 avgt 4 14178,139 ± 2873,303 ms/op
n.e.j.h.HashMapCollision.badDistWithComp 16 avgt 4 8232,037 ± 5974,530 ms/op
n.e.j.h.HashMapCollision.badDistWithComp 1000 avgt 4 8240,359 ± 7272,672 ms/op
n.e.j.h.HashMapCollision.badDistWithComp 100000 avgt 4 8079,922 ± 6270,460 ms/op
n.e.j.h.HashMapCollision.goodDistNoComp 16 avgt 4 3304,698 ± 116,866 ms/op
n.e.j.h.HashMapCollision.goodDistNoComp 1000 avgt 4 3429,393 ± 232,625 ms/op
n.e.j.h.HashMapCollision.goodDistNoComp 100000 avgt 4 3432,545 ± 497,607 ms/op
n.e.j.h.HashMapCollision.goodDistWithComp 16 avgt 4 3425,762 ± 107,659 ms/op
n.e.j.h.HashMapCollision.goodDistWithComp 1000 avgt 4 3389,997 ± 99,614 ms/op
n.e.j.h.HashMapCollision.goodDistWithComp 100000 avgt 4 3525,149 ± 549,090 ms/op
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment