假设一开始所有的数据都在一台机器上,请问加到第 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
publicclassSolution {/* * @param n: a positive integer * @return: n x 3 matrix */publicList<List<Integer>> consistentHashing(int n) {List<List<Integer>> results =newArrayList<List<Integer>>();List<Integer> machine =newArrayList<Integer>();machine.add(0);machine.add(359);machine.add(1);results.add(machine);for (int i =1; i < n; i++) {List<Integer> newMachine =newArrayList<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结果的正确性。