[хеш-таблицы имеют] O (1) вставка и поиск
Я думаю, что это неправильно.
Прежде всего, если вы ограничите пространство клавиш до конечного, вы можете сохранить элементы в массиве и выполнить O (1) линейное сканирование. Или вы можете перемешать массив и затем выполнить линейное сканирование за O (1) ожидаемое время. Когда вещи конечны, вещи легко O (1).
Допустим, ваша хеш-таблица будет хранить любую произвольную строку битов; это не имеет большого значения, пока существует бесконечный набор ключей, каждый из которых конечен. Затем вы должны прочитать все биты любого запроса и ввода, иначе я вставлю y0 в пустой хеш и запрос на y1, где y0 и y1 отличаются в одной позиции бита, на которую вы не смотрите.
Но скажем, длина ключа не является параметром. Если ваша вставка и поиск занимают O (1), в частности хеширование занимает O (1) время, что означает, что вы смотрите только конечное количество выходных данных из хеш-функции (из которых вероятно, что будет предоставляется только конечный вывод).
Это означает, что с конечным числом сегментов должен существовать бесконечный набор строк, которые имеют одинаковое значение хеш-функции. Предположим, я вставил много, т. Е. (1) из них, и начал запрашивать. Это означает, что ваша хеш-таблица должна использовать другой механизм вставки / поиска O (1), чтобы отвечать на мои запросы. Какой, и почему бы просто не использовать это напрямую?