week05- 作业

import java.util.*;
public class Sample {
    public static void main(String[] args) {
        List<Host> hosts = new ArrayList<>();
        hosts.add(Host.newInstance("192.168.1.1", 20));
        hosts.add(Host.newInstance("192.168.1.2", 20));
        hosts.add(Host.newInstance("192.168.1.3", 20));
        hosts.add(Host.newInstance("192.168.1.4", 20));
        hosts.add(Host.newInstance("192.168.1.5", 20));
        hosts.add(Host.newInstance("192.168.1.6", 20));
        hosts.add(Host.newInstance("192.168.1.7", 20));
        hosts.add(Host.newInstance("192.168.1.8", 20));
        hosts.add(Host.newInstance("192.168.1.9", 20));
        hosts.add(Host.newInstance("192.168.1.10", 20));
        Map<Integer, Integer> statistics = new HashMap<>(200);
        int[] vhosts = new int[200];
        int index = 0;
        for (Host host : hosts) {
            for (VirtualHost virtualHost : host.virtualHosts) {
                vhosts[index] = virtualHost.hash;
                statistics.put(virtualHost.hash, 0);
                index++;
            }
        }
        quickSort(vhosts, 0, vhosts.length - 1);
        int min = vhosts[0];
        int max = vhosts[vhosts.length - 1];
        Random random = new Random();
        int times = 1;
        for (int i = 0; i < 1000000; i++) {
            String string = String.valueOf(random.nextInt()) + "v" + i;
            int hashCode = string.hashCode();
            if (hashCode < min || hashCode > max) {
                Integer count = statistics.get(min);
                count++;
                statistics.put(min, count);
            } else {
                Integer key = binarySearch(vhosts, hashCode, min);
                Integer count = statistics.get(key);
                count++;
                statistics.put(key, count);
            }
        }
        double sum = 0;
        for (Map.Entry<Integer, Integer> integerIntegerEntry : statistics.entrySet()) {
            sum += integerIntegerEntry.getValue();
        }
        double avg = sum / statistics.size();
        double dVar = 0;
        for (Map.Entry<Integer, Integer> integerIntegerEntry : statistics.entrySet()) {
            dVar += (integerIntegerEntry.getValue() - avg) * (integerIntegerEntry.getValue() - avg);
        }
        double result = Math.sqrt(dVar / statistics.size());
        System.out.println(result);
    }
    private static void quickSort(int[] arr, int left, int right) {
        if (arr == null || left >= right || arr.length <= 1) {
            return;
        }
        int mid = partition(arr, left, right);
        quickSort(arr, left, mid);
        quickSort(arr, mid + 1, right);
    }
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (right > left) {
            while (pivot <= arr[right] && left < right) {
                --right;
            }
            if (left < right) {
                arr[left] = arr[right];
                ++left;
            }
            while (pivot >= arr[left] && left < right) {
                ++left;
            }
            if (left < right) {
                arr[right] = arr[left];
                --right;
            }
        }
        arr[left] = pivot;
        return left;
    }
    public static int binarySearch(int[] ary, int hash, int defaultValue) {
        int len = ary.length;
        int high = len - 1;
        int low = 0;
        while (low <= high) {
            int mid = (high + low) >> 1;
            if (ary[mid] == hash) {
                return ary[mid];
            } else if (hash >= ary[mid] && hash < ary[high]) {
                return ary[mid];
            } else if (ary[mid] < hash) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return defaultValue;
    }
    private static class Host {
        private String ip;
        private VirtualHost[] virtualHosts;
        private Host(String ip) {
            this.ip = ip;
        }
        public static final Host newInstance(String ip, int vCnt) {
            Host host = new Host(ip);
            Random random = new Random();
            VirtualHost[] virtualHosts = new VirtualHost[vCnt];
            for (int i = 0; i < vCnt; i++) {
                virtualHosts[i] = new VirtualHost((ip + "@" + i + "-" + random.nextInt()).hashCode());
            }
            host.virtualHosts = virtualHosts;
            return host;
        }
    }
    private static class VirtualHost {
        private int hash;
        public VirtualHost(int hash) {
            this.hash = hash;
        }
    }
}