# Вводим размер будущей хеш-таблицы
print("Enter the hash table size(enter an integer):")
N = int(input())
size = N
# Задаем хеш-таблицу как список
h = []
# Счетчик заполняемости хеш-таблицы
count = 0
# Создаем хеш-таблицу
for i in range(N):
    sl = ['', '', '']
    h.append(sl)
print("Empty hash table", h)
# Запускаем цикл работы с хеш-таблицей
while True:
    # Вводим команду
    print('')
    print("Enter the command(add, find, delete, exit:")
    command = str(input())
    # Команда добавления ключа
    if command == 'add':
        # Проверяем заполнена ли хеш-таблица
        if count == size:
            print("The hash table is full")
        # Если таблица не заполнена полностью вводим ключ
        else:
            print("Enter the key:")
            key = input()
            # Вводим значение
            print("Enter the value:")
            value = input()
            # Вычисляем хеш для ключа
            hf = (sum(ord(ch) for ch in key)) * size
            s = str(hf)
            # Из хеша вычисляем индекс вставки ключа
            ind = int(s[0] + s[-1])
            # Проверяем, чтобы индекс был не больше существующих
            while ind >= size:
                ind = int(ind * 2 / 3)
            # Запускаем цикл вставки ключа
            for i in range(size):
                # Проверяем занята ли позиция
                if h[ind][0] != '':
                    # Если позиция занята ключом с тем же хешем вставляем подсписок нового ключа
                    if hf == h[ind][0]:
                        # Определяем как список новые ключ и значение
                        n = [key, value]
                        # Вставляем подсписок
                        h[ind].append(n)
                        break
                    # Если позиция занята ключом с другим хешем пересчитываем индекс позиции
                    elif hf != h[ind][0]:
                        ind = int(ind / 2)
                        continue
                # Если позоция свободна записываем в неё ключ, значение и хеш
                else:
                    # Увеличиваем счетчик заполненности хеш-таблицы
                    count = count + 1
                    h[ind][0] = hf
                    h[ind][1] = key
                    h[ind][2] = value
                    # Вписанные значения определяем как подсписок
                    t = [h[ind][1], h[ind][2]]
                    h[ind] = [h[ind][0]] + [t]
                break
            # Выводим индекс вставленного ключа
            print("Insert in the index:", ind)
            # Выводим хеш-таблицу
            print(h)

    # Команда поиска по ключу
    if command == 'find':
        # Вводим ключ
        print("Enter the key")
        key = str(input())
        # Считаем хеш введенного ключа
        hf = (sum(ord(ch) for ch in key)) * size
        # Запускаем цикл поиска
        for i in range(len(h)):
            # Если хеш не найден выводим сообщение
            if i == len(h) - 1 and hf != h[i][0]:
                print("No found")
            # Если хеш есть в хеш-таблице выполняем поиск
            if hf == h[i][0]:
                # Проверяем в i-ом элементе с найденным хешем больше одного ключа или нет
                if len(h[i]) > 2:
                    # Если в i-ом элементе ключ не один запускаем цикл поиска по ключам
                    for j in range(1, len(h[i])):
                        # При равенстве искомого ключа с уже имеющимся выводим значение ключа
                        if key == h[i][j][0]:
                            print("Value:", h[i][j][1])
                # Если в i-ом элементе находится один ключ выводим его значение
                else:
                    print("Value:", h[i][1][1])
                    break

    # Команда удаления по ключу
    if command == 'delete':
        # Проверяем пуста ли хеш-таблица
        if count == 0:
            print("The hash table is empty")
        # Если таблица не пуста вводим ключ
        else:
            print("Enter the key")
            dk = str(input())
            # Рассчитываем хеш ключа на удаление
            hf = (sum(ord(ch) for ch in dk)) * size
            # Запускаем поиск ключа по хешу
            for i in range(len(h)):
                # Если ключ с рассчитанным хешем не найден выводим сообщение
                if i == len(h) - 1 and hf != h[i][0]:
                    print("No found")
                # Проверка равенства найденного хеша с уже имеющимися
                if hf == h[i][0]:
                    # При равенстве хешей проверяем количество ключей в i-ом элементе
                    if len(h[i]) > 2:
                        # При условии, что ключей больше одного запускаем цикл поиска  по ключам в i-ом элементе
                        for j in range(1, len(h[i])):
                            # Если введенный ключ равен имеющемуся удаляем ключ и соответствующее ему значение
                            if dk == h[i][j][0]:
                                h[i].pop(j)
                                # Выводим из какой позиции произведено удаление и хеш-таблицу
                                print("Deleting from the index", i)
                                print(h)
                                break
                    # Если в i-ом элементе находится один ключ, удаляем его, хеш и значение
                    else:
                        h[i] = ['', '', '']
                        # Уменьшаем счетчик заполненности хеш-таблицы
                        count = count - 1
                        # Выводим позицию из которой было произведено удаление и хеш-таблицу
                        print("Deleting from the index", i)
                        print(h)
                        break

    # Команда выхода из программы
    if command == 'exit':
        exit()
