# coding: UTF-8
import bisect
import zlib
class HashServer:
    def __init__(self):
        self.hash_node = [] # hash节点
        self.node_name = [] # 节点名称
    def hash(self, v):
        return zlib.crc32(v)%(2**32-1)
    def add_server(self, server):
        for i in range(0, 4):#vnode
            name = server + ":*" + str(i)
            node = self.hash(name)
            pos = bisect.bisect_right(self.hash_node, node)
            self.hash_node.insert(pos, node)
            self.node_name.insert(pos, name)
    def remove_server(self, server):
        i = 0
        while i < len(self.node_name):
            if self.node_name[i][:-3]==server:
                self.node_name.pop(i)
                
                self.hash_node.pop(i)
            else:
                i = i + 1
    def find_server(self, v):
        node = self.hash(v)
        pos = bisect.bisect_right(self.hash_node, node) # 二分查找
        if pos == len(self.hash_node):
            pos = 0
        return self.node_name[pos]
a = HashServer()
a.add_server("node1")
a.add_server("node2")
a.add_server("node3")
print "----"
for i in range(0, 20):
    print a.find_server(str(i))[:-3]
a.add_server("node4")
print "----"
for i in range(0, 20):
    print a.find_server(str(i))[:-3]
a.remove_server("node4")
print "----"
for i in range(0, 20):
    print a.find_server(str(i))[:-3]

----
node3
node3
node2
node3
node3
node3
node2
node3
node3
node3
node1
node1
node2
node1
node1
node1
node2
node1
node2
node1
----
node4
node4
node2
node3
node4
node4
node2
node3
node4
node4
node1
node1
node2
node1
node1
node1
node2
node1
node2
node1
----
node3
node3
node2
node3
node3
node3
node2
node3
node3
node3
node1
node1
node2
node1
node1
node1
node2
node1
node2
node1