架构师训练营第五周作业 一致性哈希

import java.util.Collection;
public class StandardDivision {
    public double calculate(Collection<Integer> nums, int average) {
        if(nums == null || nums.isEmpty()) throw new IllegalArgumentException();
        int n = nums.size();
        double variance = 0;
        for(int num : nums) {
            variance += (num - average) * (num - average);
        }
        variance /= n;
        return Math.sqrt(variance);
    }
}

import java.util.*;
public class ConsistentHash {
    private final Random random = new Random();
    private final Map<Integer, Integer> virtualPhysicalMapping = new HashMap<>();//key is virtual node, value is physical node id
    private final List<Integer> virtualNodes = new ArrayList<>(); //keep all virtualNodes
    private final int machineNumbers;
    private final int virtualNodesNumbersForOneMachine;
    // key is index of physical machine, value is number of data in this physical machine
    Map<Integer, Integer> physicalMachineCountMap = new HashMap<>();
    public ConsistentHash(int machineNumbers, int virtualNodesNumbersForOneMachine) {
        if(machineNumbers <= 0) throw new IllegalArgumentException("machineNumbers needs to be positive");
        if(virtualNodesNumbersForOneMachine <= 0) throw new IllegalArgumentException("virtualNodesNumbersForOneMachine needs to be positive");
        this.machineNumbers = machineNumbers;
        this.virtualNodesNumbersForOneMachine = virtualNodesNumbersForOneMachine;
        generateVirtualNodes();
    }
    public void assignValueToVirtualNode(int value) {
        int index = Collections.binarySearch(virtualNodes, value);
        if(index < 0) index = -index - 1; //if index < 0, get the correct insert position
        if(index == virtualNodes.size()) index = 0; //reach the end of the hash cycle, use the first virtual node
        int physicalMachineId = virtualPhysicalMapping.get(virtualNodes.get(index));
        int count = physicalMachineCountMap.getOrDefault(physicalMachineId, 0);
        physicalMachineCountMap.put(physicalMachineId, count + 1);
    }
    public Map<Integer, Integer> getPhysicalMachineCountMap() {
        return physicalMachineCountMap;
    }
    private void generateVirtualNodes() {
        for(int i=0; i<machineNumbers; i++) {
            List<Integer> virtualNodesForOneMachine = generateVirtualNodesForOneMachine();
            for(Integer virtual : virtualNodesForOneMachine) {
                virtualPhysicalMapping.put(virtual, i);
            }
            virtualNodes.addAll(virtualNodesForOneMachine);
        }
        virtualNodes.sort(Comparator.comparingInt(x -> x));
    }
    private List<Integer> generateVirtualNodesForOneMachine() {
        List<Integer> virtualNodesForOneMachine = new ArrayList<>();
        for(int i=0; i<virtualNodesNumbersForOneMachine; i++) {
            virtualNodesForOneMachine.add(random.nextInt());
        }
        return virtualNodesForOneMachine;
    }
}

    public static void main(String[] args) {
        int numberOfTestData = 1000000;
        int numberOfMachine = 10;
        int numberOfVirtualNodes = 200;
        ConsistentHash consistentHash = new ConsistentHash(numberOfMachine, numberOfVirtualNodes);
        Random r = new Random();
        for(int i=0; i<numberOfTestData; i++) {
            int value = r.nextInt();
            consistentHash.assignValueToVirtualNode(value);
        }
        Map<Integer, Integer> physicalMachineCountMap = consistentHash.getPhysicalMachineCountMap();
        StandardDivision standardDivision = new StandardDivision();
        double standDivision = standardDivision.calculate(physicalMachineCountMap.values(), numberOfTestData/numberOfMachine);
        System.out.println("Standard Division is: " + standDivision);
    }