Consistent Hashing

Consistent Hashing是用来解决分布式数据库数据迁移问题的一个实用算法，第一题实现的是一个朴素的consistent hashing，数据分区比较暴力

class Solution:
    # @param {int} n a positive integer
    # @return {int[][]} n x 3 matrix
    def consistentHashing(self, n):
        # Write your code here
        result = [[0, 359, 1]]

        for i in xrange(1, n):
            tmp, index = 0, 0
            for j in xrange(i):
                if result[j][1] - result[j][0] > tmp:
                    tmp = result[j][1] - result[j][0]
                    index = j

            newInterval = [(result[index][1] + result[index][0]) / 2 + 1, result[index][1], i + 1]
            result[index][1] = (result[index][1] + result[index][0]) / 2
            result.append(newInterval)

        return result

Consistent Hashing II

主要就是实现真正的一致性哈希，不过这里其实只要求实现了撒点和利用hashCode来找对应服务器的算法，对于数据点和服务器virtual node的冲突处理没有实现

import random

class Solution:

    hashBase = None
    shardingCount = None
    hashingCircle = None
    checker = None

    # @param {int} n a positive integer
    # @param {int} k a positive integer
    # @return {Solution} a Solution object
    @classmethod
    def create(cls, n, k):
        # Write your code here
        result = cls()
        result.hashBase = n
        result.shardingCount = k
        result.hashingCircle = [0] * n
        result.checker = set(range(n))
        return result

    # @param {int} machine_id an integer
    # @return {int[]} a list of shard ids
    def addMachine(self, machine_id):
        # write your code here
        result = []
        while len(result) < self.shardingCount:
            tmpIndex = random.randint(0, self.hashBase - 1)
            if tmpIndex not in self.checker:
                continue
            result.append(tmpIndex)
            self.checker.remove(tmpIndex)
            self.hashingCircle[tmpIndex] = machine_id
        return result

    # @param {int} hashcode an integer
    # @return {int} a machine id
    def getMachineIdByHashCode(self, hashcode):
        # write your code here
        cur = hashcode
        while self.hashingCircle[cur] == 0:
            cur += 1
            cur %= self.hashBase
        return self.hashingCircle[cur]