CountDegree

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        long time = 0;
        for (long s = 1 ; s <= 10 ; s++) {
            int[] g = gen(s);
            time += takeIHM(g);
        }
        System.out.println("done:" + time / 10 / 1000);
    }

    public static int[] gen(long seed) {
        Random rand = new Random(seed);
        int size = 2_000_000;
        int[] ret = new int[size];
        for (int i = 0 ; i < size ; i++) {
            ret[i] = rand.nextInt(1_000_000_000);
        }
        return ret;
    }

    public static long takeHM(int[] a) {
        long time = System.nanoTime();
        Map<Integer,Integer> degree = new HashMap<>();
        for (int i = 0 ; i < a.length ; i++) {
            degree.put(a[i], degree.getOrDefault(a[i], 0)+1);
        }
        return System.nanoTime()-time;
    }

    public static long takeSHM(int[] a) {
        long time = System.nanoTime();
        Map<Integer,Integer> degree = new HashMap<>(a.length*2);
        for (int i = 0 ; i < a.length ; i++) {
            degree.put(a[i], degree.getOrDefault(a[i], 0)+1);
        }
        return System.nanoTime()-time;
    }

    public static long takeSort(int[] a) {
        long time = System.nanoTime();
        Arrays.sort(a);
        for (int i = 0 ; i < a.length ; ) {
            int j = i;
            while (j < a.length && a[i] == a[j]) {
                j++;
            }
            i = j;
        }
        return System.nanoTime() - time;
    }

    public static long takeIHM(int[] a) {
        long time = System.nanoTime();
        int n = a.length;
        int M = (1<<22);
        IntHashMap degree = new IntHashMap(M, 0);
        for (int i = 0 ; i < n ; i++) {
            if (degree.containsKey(a[i])) {
                degree.put(a[i], degree.get(a[i])+1);
            } else {
                degree.put(a[i], 1);
            }
        }
        return System.nanoTime() - time;
    }

    public static class IntHashMap {
        int defaultValue;
        int M;
        int[] next;
        int[] entryKey;
        int[] entryValue;
        int nextIndex;

        public IntHashMap(int capacity, int defaultValue) {
            int c = Math.max(32, Integer.highestOneBit(capacity-1)<<1);

            this.defaultValue = defaultValue;
            this.next = new int[c];
            this.entryKey = new int[c];
            this.entryValue = new int[c];
            this.M = c / 2;
            this.nextIndex = M;

            Arrays.fill(next, -1);
            Arrays.fill(entryValue, defaultValue);
        }

        public boolean containsKey(int key) {
            return detectEntry(key) >= 0;
        }

        public int get(int key) {
            int pos = detectEntry(key);
            if (pos < 0) {
                return defaultValue;
            }
            return entryValue[pos];
        }

        public void put(int key, int value) {
            int pos = detectEntry(key);
            if (pos < 0) {
                addEntry(-pos-1, key, value);
            } else {
                entryValue[pos] = value;
            }
        }

        private int detectEntry(int key) {
            int pos = hashPosition(key);
            while (true) {
                if (entryKey[pos] == key) {
                    return pos;
                }
                if (next[pos] == -1) {
                    break;
                }
                pos = next[pos];
            }
            return -(pos+1);
        }

        private void addEntry(int pos, int key, int value) {
            assert(next[pos] == -1);
            next[pos] = nextIndex++;
            int newpos = next[pos];
            entryKey[newpos] = key;
            entryValue[newpos] = value;
        }

        private int hashPosition(int key) {
            return hash(key) & (M-1);
        }

        private static int hash(int h) {
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    }
}