Самый эффективный способ хранения тысячи телефонных номеров

Это вопрос из интервью Google:

Необходимо сохранить около тысячи телефонных номеров, каждый из которых состоит из 10 цифр. Вы можете предположить, что первые 5 цифр каждой из тысяч чисел одинаковы. Вам необходимо выполнить следующие операции: a. Выполните поиск, если заданный номер существует. б. Выведите все числа

Каков наиболее эффективный способ сэкономить место?

Я ответил на хеш-таблицу, а затем на кодирование Хаффмана, но мой интервьюер сказал, что я иду не в правильном направлении. Пожалуйста, помогите мне здесь.

Может ли помочь использование дерева с суффиксом?

В идеале для сохранения 1000 чисел требуется 4 байта на число, поэтому в целом для хранения 1000 чисел потребуется 4000 байтов. Количественно я хочу уменьшить объем хранилища до <4000 байт, как мне объяснил мой интервьюер.