Ну да, если выбрать достаточно компактную вселенную, можно сопоставить каждый ключ с уникальным слотом, используя всего log₂(n) бит на ключ, но все равно нужно место для хранения этой сопоставления. Можно построить идеальную хеш-функцию без коллизий, но это обычно требует дополнительных затрат памяти или времени. Короче говоря, можно приблизиться к нескольким битам на ключ, но общий объем данных всегда будет компромиссом.