Consistent Hashing--一致性哈希代码实现Java

一致性哈希的介绍

public class Solution {
    public int n, k;public Set<Integer> ids = null;public Map<Integer, List<Integer>> machines = null;// @param n a 环的大小// @param k a 一台机器对应1000个Virtual nodes// @return a Solution object//n 和 k在真实的 NoSQL 数据库中一般是 2^64 和 1000。public static Solution create(int n, int k) {
    Solution solution = new Solution();solution.n = n;solution.k = k;solution.ids = new TreeSet<Integer>();solution.machines = new HashMap<Integer, List<Integer>>();return solution;}// @param machine_id an integer// @return a list of shard idspublic List<Integer> addMachine(int machine_id) {
    // Write your code hereRandom ra = new Random();List<Integer> random_nums = new ArrayList<Integer>();for (int i = 0; i < k; ++i) {
    int index = ra.nextInt(n);while (ids.contains(index))index = ra.nextInt(n);ids.add(index);random_nums.add(index);}Collections.sort(random_nums);machines.put(machine_id, random_nums);return random_nums;}// @param hashcode an integer// @return a machine idpublic int getMachineIdByHashCode(int hashcode) {
    int distance = n + 1;int machine_id = 0;for (Map.Entry<Integer, List<Integer>> entry : machines.entrySet()) {
    int key = entry.getKey();List<Integer> random_nums = entry.getValue();for (Integer num : random_nums) {
    int d = num - hashcode;if (d < 0)d += n;if (d < distance) {
    distance = d;machine_id = key;}}}return machine_id;}
}