架构师 0 期 05 周作业

package com.afangsha.hash;
/**
 * @author thanheart
 *
 */
public class HashNode {
    private Integer trueNode;
    private Integer hashCode;
    private Long count = 0L;
    public HashNode(final Integer trueNode, final Integer hashCode) {
        this.trueNode = trueNode;
        this.hashCode = hashCode;
    }
    public Integer getTrueNode() {
        return trueNode;
    }
    public void setTrueNode(final Integer trueNode) {
        this.trueNode = trueNode;
    }
    public Integer getHashCode() {
        return hashCode;
    }
    public void setHashCode(final Integer hashCode) {
        this.hashCode = hashCode;
    }
    public Long getCount() {
        return count;
    }
    public void setCount(final Long count) {
        this.count = count;
    }
}

package com.afangsha.hash;
import java.lang.invoke.SerializedLambda;
import java.util.Arrays;
import java.util.Random;
/**
 * @author thanheart
 *
 */
public class Main {
    private static final Integer SERVICE_COUNT = 10;
    private static final Integer[] SERVICE_NUMBER = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    private static final Integer FICTITIOUS_COUNT = 200;
    private static final Integer HASH_NUMBER_COUNT = (int) Math.pow(2, 32) - 1;
    private static final Integer HASH_COUNT = 1000000;
    private static final double AVERAGE = HASH_COUNT / (SERVICE_COUNT * FICTITIOUS_COUNT);
    public static void main(String[] args) {
        Random random = new Random();
        final HashNode[] hashNodes = new HashNode[SERVICE_COUNT * FICTITIOUS_COUNT];
        for (int i = 0; i < SERVICE_COUNT; ++i) {
            for (int j = 0; j < FICTITIOUS_COUNT; ++j) {
                hashNodes[FICTITIOUS_COUNT * i + j] = new HashNode(SERVICE_NUMBER[i],
                        random.nextInt(HASH_NUMBER_COUNT));
            }
        }
        Arrays.sort(hashNodes, (a, b) -> a.getHashCode() - b.getHashCode());
        for (int i = 0; i < HASH_COUNT; ++i) {
            int hashCode = random.nextInt(HASH_NUMBER_COUNT);
            HashNode hashNode = getNextHashNode(hashCode, hashNodes);
            hashNode.setCount(hashNode.getCount() + 1);
        }
        double variance = 0;
        for (int i = 0; i < hashNodes.length; ++i) {
            variance += Math.pow((hashNodes[i].getCount() - AVERAGE), 2);
        }
        double standard = Math.sqrt(variance);
        System.out.println("所有虚拟节点标准差为：" + standard);
        long[] trueNodeHashCount = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        for (int i = 0; i < hashNodes.length; ++i) {
            HashNode hashNode = hashNodes[i];
            trueNodeHashCount[hashNode.getTrueNode()] += hashNode.getCount();
        }
        double average = HASH_COUNT / SERVICE_COUNT;
        double trueVariance = 0;
        for (int i = 0; i < trueNodeHashCount.length; ++i) {
            trueVariance += Math.pow((trueNodeHashCount[i] - average), 2);
        }
        double trueStandard = Math.sqrt(trueVariance);
        System.out.println("真实标准差为：" + trueStandard);
    }
    public static HashNode getNextHashNode(final Integer hashCode, HashNode[] hashNodes) {
        int firstIndex = 0;
        int lastIndex = hashNodes.length - 1;
        int middle = (firstIndex + lastIndex);
        while (firstIndex < middle) {
            if (hashNodes[middle].getHashCode().equals(hashCode)) {
                return hashNodes[middle];
            }
            if (hashNodes[middle].getHashCode() > hashCode) {
                lastIndex = middle;
            } else {
                firstIndex = middle;
            }
            middle = (firstIndex + lastIndex) / 2;
        }
        return hashNodes[firstIndex];
    }
}