Как улучшить производительность хеш-таблицы с 1 миллионом элементов и 997 корзинами?

Это вопрос интервью.

Предположим, что в таблице 1 миллион элементов и 997 корзин неупорядоченных списков. Далее предположим, что хеш-функция распределяет ключи с равной вероятностью (т.е. каждая корзина имеет 1000 элементов).

Какое время является наихудшим, чтобы найти элемент, которого нет в таблице? Чтобы найти тот, который есть в таблице? Как вы можете это улучшить?

Мое решение: В худшем случае время нахождения элемента не в таблице и в таблице все равно O (1000). 1000 - длина несортированного списка.

Улучшение: (0) просто, увеличьте количество сегментов> 1 миллиона. (1) каждая корзина содержит вторую хеш-таблицу, которая использует другую хеш-функцию для вычисления хеш-значения для второй таблицы. это будет O (1) (2) каждая корзина содержит двоичное дерево поиска. Это будет O (lg n).

возможно ли сделать компромисс между пространством и временем. Держите их оба в разумном диапазоне.

Есть идеи получше? Благодарность !