serverIndex = hash(key) % N (N은 서버의 개수)

import hashlib

class ConsistentHashing:
    def __init__(self, replicas=3):
        self.replicas = replicas  # Number of replicas per server
        self.server_ring = {}
        self.sorted_keys = []

    def _get_hashed_key(self, key):
        hash_object = hashlib.sha1(key.encode())
        hash_key = int(hash_object.hexdigest(), 16)
        return hash_key

    def add_server(self, server):
        for i in range(self.replicas):
            replica_key = self._get_hashed_key(f"{server}-{i}")
            self.server_ring[replica_key] = server
            self.sorted_keys.append(replica_key)
        self.sorted_keys.sort()

    def remove_server(self, server):
        keys_to_remove = []
        for key, value in self.server_ring.items():
            if value == server:
                keys_to_remove.append(key)
    
        for key in keys_to_remove:
            self.sorted_keys.remove(key)
            del self.server_ring[key]

    def get_server(self, key):
        if not self.server_ring:
            return None

        hashed_key = self._get_hashed_key(key)
        for server_key in self.sorted_keys:
            if hashed_key <= server_key:
                return self.server_ring[server_key]
        return self.server_ring[self.sorted_keys[0]]

# Example usage
ch = ConsistentHashing(replicas=3)

servers = ['Server1', 'Server2', 'Server3']
for server in servers:
    ch.add_server(server)

keys = ['Key1', 'Key2', 'Key3', 'Key4', 'Key5']
for key in keys:
    server = ch.get_server(key)
    print(f"Key {key} is directed to {server}")

ch.add_server('Server4')
added_server = 'Server4'
print(f"Server {added_server} has been added.")

key = 'Key6'
server = ch.get_server(key)
print(f"Key {key} is directed to {server} after server addition.")

keys = ['Key1', 'Key2', 'Key3', 'Key4', 'Key5']
for key in keys:
    server = ch.get_server(key)
    print(f"Key {key} is directed to {server}")
    
ch.remove_server('Server2')
removed_server = 'Server2'
print(f"Server {removed_server} has been removed.")

key = 'Key7'
server = ch.get_server(key)
print(f"Key {key} is directed to {server} after server removal.")

keys = ['Key1', 'Key2', 'Key3', 'Key4', 'Key5', 'Key6']
for key in keys:
    server = ch.get_server(key)
    print(f"Key {key} is directed to {server}")

Key Key1 is directed to Server3
Key Key2 is directed to Server1
Key Key3 is directed to Server2
Key Key4 is directed to Server2
Key Key5 is directed to Server2
Server Server4 has been added.
Key Key6 is directed to Server4 after server addition.
Key Key1 is directed to Server4
Key Key2 is directed to Server1
Key Key3 is directed to Server2
Key Key4 is directed to Server2
Key Key5 is directed to Server2
Server Server2 has been removed.
Key Key7 is directed to Server4 after server removal.
Key Key1 is directed to Server4
Key Key2 is directed to Server1
Key Key3 is directed to Server4
Key Key4 is directed to Server4
Key Key5 is directed to Server4
Key Key6 is directed to Server4