Будет ли идеальный хеш иметь удаление вставки и поиск за 0 (1) раз?
Да, поскольку вы получите только одноэлементные сегменты. Таким образом, вы получаете столько ведер, сколько есть элементов.
Если так, то почему ученые-компьютерщики не используют идеальное хеширование все время, если нет, какова будет временная сложность?
Одна из причин теоретическая .
Идеальная хеш-функция является инъективной, и определение такой функции может быть трудным, если не невозможным.
Рассмотрим следующую тривиальную структуру:
{
int x;
int y;
}
Как правило, вы хотите, чтобы ваша функция hash() давала уникальные результаты для всех возможных значений x и y, это может быть невозможно. В основном для тривиальных, таких как x + y, x * y, x ^ y, вы всегда можете создать другой вход, который дал бы тот же результат.
С другой стороны, это возможно (как |N^2| = |N| = aleph-null) - см. Функция сопряжения Кантора .
Другая причина - практическая - ваша функция возврата должна иметь тип возврата. Возвращаемый тип должен быть способен хранить все возможные результаты внедрения - поэтому для хэша двух 32-битных значений потребуется 64 бита, для трех 3 * 32 и т. Д. (Сравните, что вышеупомянутая функция сопряжения эффективно умножает аргументы)