假设一开始所有的数据都在一台机器上，请问加到第 n 台机器的时候，区间的分布情况和对应的机器编号分别是多少？
Example
for n = 1, return
[
[0,359,1]
]
represent 0~359 belongs to machine 1.
for n = 2, return
[
[0,179,1],
[180,359,2]
]
for n = 3, return
[
[0,89,1]
[90,179,3],
[180,359,2]
]
for n = 4, return
[
[0,89,1],
[90,179,3],
[180,269,2],
[270,359,4]
]
for n = 5, return
[
[0,44,1],
[45,89,5],
[90,179,3],
[180,269,2],
[270,359,4]
]
Clarification
If the maximal interval is [x, y], and it belongs to machine id z, when you add a new machine with id n, you should divide [x, y, z] into two intervals:
[x, (x + y) / 2, z]and[(x + y) / 2 + 1, y, n]
Notice
你可以假设 n <= 360. 同时我们约定，当最大区间出现多个时，我们拆分编号较小的那台机器。
比如0~119， 120~239区间的大小都是120，但是前一台机器的编号是1，后一台机器的编号是2, 所以我们拆分0~119这个区间。
Solution
public class Solution {
/*
* @param n: a positive integer
* @return: n x 3 matrix
*/
public List<List<Integer>> consistentHashing(int n) {
List<List<Integer>> results = new ArrayList<List<Integer>>();
List<Integer> machine = new ArrayList<Integer>();
machine.add(0);
machine.add(359);
machine.add(1);
results.add(machine);
for (int i = 1; i < n; i++) {
List<Integer> newMachine = new ArrayList<Integer>();
int maxIntervalIndex = 0;
for (int j = 0; j < i; j++) {
if (results.get(j).get(1) - results.get(j).get(0) > results.get(maxIntervalIndex).get(1) - results.get(maxIntervalIndex).get(0)) {
maxIntervalIndex = j;
}
}
int x = results.get(maxIntervalIndex).get(0);
int y = results.get(maxIntervalIndex).get(1);
results.get(maxIntervalIndex).set(1, (x + y) / 2);
newMachine.add((x + y) / 2 + 1);
newMachine.add(y);
newMachine.add(i + 1);
results.add(newMachine);
}
return results;
}
}
Consistent Hashing - II
Description
在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法，这个简单的版本有两个缺陷：
addMachine(int machine_id) // add a new machine, return a list of shard ids.
getMachineIdByHashCode(int hashcode) // return machine id
当 n 为 2^64 时，在这个区间内随机基本不会出现重复。
但是为了方便测试您程序的正确性，n 在数据中可能会比较小，所以你必须保证你生成的 k 个随机数不会出现重复。
LintCode并不会判断你addMachine的返回结果的正确性（因为是随机数），只会根据您返回的addMachine的结果判断你getMachineIdByHashCode结果的正确性。
Using HashMap (machine_id as key, random numbers as value)
public class Solution {
public int n, k;
public Set<Integer> ids = null;
public Map<Integer, List<Integer>> machines = null;
// @param n a positive integer
// @param k a positive integer
// @return a Solution object
public static Solution create(int n, int k) {
// Write your code here
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 ids
public List<Integer> addMachine(int machine_id) {
// Write your code here
Random 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 id
public int getMachineIdByHashCode(int hashcode) {
// Write your code here
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;
}
}
Using TreeMap (random numbers as key, machine_id as value in the treemap)
public class Solution {
private TreeMap<Integer, Integer> tm = new TreeMap<>();
private int[] nums;
private int size = 0;
private int k;
public Solution(int n, int k) {
this.nums = new int[n];
for(int i = 0; i < n; i++) this.nums[i] = i;
Random random = new Random();
for(int i = 0; i < n; i++) {
int j = random.nextInt(i + 1);
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
this.k = k;
}
// @param n a positive integer
// @param k a positive integer
// @return a Solution object
public static Solution create(int n, int k) {
// Write your code here
return new Solution(n, k);
}
// @param machine_id an integer
// @return a list of shard ids
public List<Integer> addMachine(int machine_id) {
// Write your code here
List<Integer> ids = new ArrayList<>();
for(int i = 0; i < this.k; i++) {
int id = this.nums[size++ % this.nums.length];
ids.add(id);
this.tm.put(id, machine_id);
}
return ids;
}
// @param hashcode an integer
// @return a machine id
public int getMachineIdByHashCode(int hashcode) {
// Write your code here
if (tm.isEmpty()) return 0;
Integer ceiling = tm.ceilingKey(hashcode);
if (ceiling != null) return tm.get(ceiling);
return tm.get(tm.firstKey());
}
}
---------------------
作者：jmspan
来源：CSDN
原文：https://blog.csdn.net/jmspan/article/details/51749521
版权声明：本文为博主原创文章，转载请附上博文链接！