import uuid


class My_dict:
    def __init__(self, M):
        self.M = M
        self.table = [self.Linked_list() for i in range(M)]

    def put(self, key, value):
        self.table[self.hashcode(key)].add(key, value)

    def hashcode(self, key):
        return hash(key) % self.M

    def stat(self):
        max_size = 0
        for l in self.table:
            if l.N > max_length:
                max_length = l.N
        print("max bucket size is: %s" % max_size)

    class Linked_list:
        def __init__(self):
            self.first = None
            self.N = 0

        def add(self, key, value):
            cur = self.first
            while cur is not None:
                if cur.key == key:
                    cur.value = value
                    return
                cur = cur.next
            self.first = self.Node(key, value, self.first)
            self.N += 1

        class Node:
            def __init__(self, key, value, next_node):
                self.key = key
                self.value = value
                self.next = next_node


for i in range(4, 20):
    m = 1 << i
    my_map = My_dict(m)
    for j in range(int(0.75 * m)):
        # u = uuid.uuid1()
        # print(hash(u))
        u = "".join(random.sample('zyxwvutsrqponmlkjihgfedcba0123456789/*-+!@#$%^&*', 5))
        my_map.put(u, 0)
    my_map.stat()