week5

package pkg;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;

public class ConsistentHashing {
    private Map<Integer, String> hash = new HashMap<Integer, String>();
    private List<Integer> keys = new ArrayList<Integer>();

    public ConsistentHashing(List<String> servers) {
        build(servers);
    }

    private static int computeHashKey(String k) {
        MessageDigest md = null;
        try {
            md = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            System.exit(1);
        }
        md.update(k.getBytes());
        byte[] bytes = md.digest();
        return (bytes[0] & 0xff) << 24 | (bytes[1] & 0xff) << 16 | (bytes[2] & 0xff) << 8 | (bytes[3] & 0xff);
    }

    private void build(List<String> servers) {
        MessageDigest md = null;
        try {
            md = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            System.exit(1);
        }
        for (String server : servers) {
            for (int i = 0; i < 40; i++) {
                String tmp = server + i;
                md.update(tmp.getBytes());
                byte[] bytes = md.digest();
                int k = 0;
                for (int j = 0; j < bytes.length; j += 4) {
                    k <<= 8;
                    k |= bytes[j] & 0xff;
                    k <<= 8;
                    k |= bytes[j + 1] & 0xff;
                    k <<= 8;
                    k |= bytes[j + 2] & 0xff;
                    k <<= 8;
                    k |= bytes[j + 3] & 0xff;
                    keys.add(k);
                    hash.put(k, server);
                }
            }
        }
        keys.sort(Comparator.<Integer>naturalOrder());
    }

    public String getServer(String inputKey) {
        int hashValue = computeHashKey(inputKey);
        int ret = Collections.binarySearch(keys, hashValue);
        if (ret < 0) {
            ret = -ret - 1;
        }
        if (ret == keys.size()) {
            ret = 0;
        }
        return hash.get(ret);
    }

    public static void main(String[] args) {
        List<String> servers = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            servers.add("server" + i);
        }
        ConsistentHashing consistentHashing = new ConsistentHashing(servers);

        Map<String, Integer> count = new HashMap<>();
        for (int i = 0; i < 1_000_000; i++) {
            String s = consistentHashing.getServer("k" + i);
            count.merge(s, 0, Integer::sum);
        }

        double mean = 1_000_000 * 1.0 / count.size();
        double d = 0;
        for (String server : servers) {
            int cnt = count.getOrDefault(server, 0);
            d += Math.pow(cnt - mean, 2);
        }
        d /= count.size();
        double result = Math.sqrt(d / mean);

        System.out.println(result);
    }
}