package jdk.test;

/*

Original JDK9 HashMap:

Benchmark                                (initialSize)  Mode  Samples     Score     Error  Units
j.t.HashMapCollision.badDistFalseComp               16    ss       20  4221.438 ± 250.774     ms
j.t.HashMapCollision.badDistNoComp                  16    ss       20  2868.605 ±  40.754     ms
j.t.HashMapCollision.badDistWithComp                16    ss       20  3030.780 ± 111.315     ms

Patched:

Benchmark                                (initialSize)  Mode  Samples     Score     Error  Units
j.t.HashMapCollision.badDistFalseComp               16    ss       20  3237.953 ± 143.608     ms
j.t.HashMapCollision.badDistNoComp                  16    ss       20  2643.024 ± 137.067     ms
j.t.HashMapCollision.badDistWithComp                16    ss       20  3087.902 ± 122.041     ms

*/

import org.openjdk.jmh.annotations.*;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

@State(Scope.Thread)
@Warmup(iterations = 5)
@Measurement(iterations = 10)
@Fork(2)
@BenchmarkMode(Mode.SingleShotTime)
@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;

    @Param({"16"})
    int initialSize;

    @Benchmark
    public Map<NodeNoComp, NodeNoComp> badDistNoComp() {
        Map<NodeNoComp, NodeNoComp> map = new HashMap<NodeNoComp, NodeNoComp>(initialSize);
        ThreadLocalRandom random = ThreadLocalRandom.current();
        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);
        ThreadLocalRandom random = ThreadLocalRandom.current();
        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<NodeFalseComp, NodeFalseComp> badDistFalseComp() {
        Map<NodeFalseComp, NodeFalseComp> map = new HashMap<NodeFalseComp, NodeFalseComp>(initialSize);
        ThreadLocalRandom random = ThreadLocalRandom.current();
        for (int i = 0; i < 10000000; i++) {
            NodeFalseComp key = new NodeFalseComp(random.nextInt(max_k1), random.nextInt(max_k2), BAD_HASH);
            NodeFalseComp 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);
        ThreadLocalRandom random = ThreadLocalRandom.current();
        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);
        ThreadLocalRandom random = ThreadLocalRandom.current();
        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;
    }

    @Benchmark
    public Map<NodeFalseComp, NodeFalseComp> goodDistFalseComp() {
        Map<NodeFalseComp, NodeFalseComp> map = new HashMap<NodeFalseComp, NodeFalseComp>(initialSize);
        ThreadLocalRandom random = ThreadLocalRandom.current();
        for (int i = 0; i < 10000000; i++) {
            NodeFalseComp key = new NodeFalseComp(random.nextInt(max_k1), random.nextInt(max_k2), GOOD_HASH);
            NodeFalseComp 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;
        }
    }

    private static class NodeFalseComp implements Comparable<Void> {

        private final int k1;
        private final int k2;
        private final int hashFactor;

        public NodeFalseComp(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 NodeFalseComp))
                return false;

            NodeFalseComp other = (NodeFalseComp) obj;

            return k1 == other.k1 && k2 == other.k2;
        }

        @Override
        public int compareTo(Void o) {
            return 0;
        }
    }
}