Задача не имеет решения в заявленых ограничениях. Если чьи-то решения прокатывают - значит редакция мухлюет с тестовыми данными. Вот демка на этот счет. Можешь допилить её, выбросив лишнее и заменив
randrange на
hash(input()), и попробовать пропихнуть как решение.
from numpy import zeros, uint32
from random import randrange
from sys import getsizeof
N = 10 ** 6
hashes = zeros(N, uint32)
print(f'hashes занимает {getsizeof(hashes)} байт')
control = set() # здесь считаем по-честному
for i in range(N):
# вместо строк я использую большие случайные числа
r = randrange(0x4000000000000000)
control.add(r)
# сохраняем последние 4 байта r - больше не лезет
hashes[i] = r & 0xffffffff
hashes.sort()
a, cnt = hashes[0], 1
for b in hashes:
if a != b:
a = b
cnt += 1
print(f'control - целых {getsizeof(control)} байт (для строк длиной до 1к было бы больше)')
print(f'{cnt:8} разных хэшей\n{len(control):8} разных чисел')
Слишком короткий хэш (32 бита) на 10^6 строк порождает слишком много коллизий (смотри
парадокс дней рождения). Нельзя впихнуть невпихуемое.
UPDATE
Roman Kitaev предложил использовать фильтр Блума, вот решение на этой идее. Оно несёт в себе недостатки фильтра Блума: работает медленно и ошибается; так же возможно, что мои упрощения убили фильтр, но авось прокатит.
bitmap, cnt = bytearray(0x400000), 0
for _ in range(int(input())):
h, f = hash(input()), 0
for _ in range(16):
m = b'\x01\x02\x04\x08\x10\x20\x40\x80'[h & 7]
h = ((h >> 4) ^ i) | ((h & 15) << 60)
if not bitmap[h & 0x3fffff] & m:
bitmap[h & 0x3fffff] |= m
f = 1
cnt += f
print(cnt)
