Наилучший возможный способ - поддерживать низкий коэффициент загрузки хеш-таблицы за счет более высокого риска коллизии ha sh. В качестве альтернативы, если вы знаете, какие записи с большей вероятностью будут иметь какое-либо значение, ведите небольшой индекс этих записей. В противном случае это невозможно улучшить.
Ниже приведено интуитивное доказательство того, что это невозможно.
Сначала давайте рассмотрим структуру HashSet. HashSet основан на хеш-таблице с ключом ha sh. Следующее использует эту хеш-таблицу, взятую из Википедии в качестве примера:
Предположим, существует эффективный алгоритм для получения произвольной записи из хеш-таблицы.
Рассмотрим случай где мы вставили три записи в примере, затем вызовем remove("John Smith") и remove("Lisa Smith"). Теперь мы запускаем этот мнимый алгоритм и получаем 521-9655. Как это сделать? Поскольку предполагается, что значения ha sh распределены равномерно, попытка исследовать записи 00, 01, ... должна работать так же эффективно, как и любой другой алгоритм, предполагая, что никакой другой информации не известно. Затем мы видим наихудший случай, когда нам нужно исследовать O (n) записей (в этом примере 15 проб), чтобы найти произвольную запись. Обратите внимание, что n - это число записей хеш-таблицы, которое линейно коррелирует с размером HashSet по коэффициенту загрузки хеш-таблицы (или максимальному размеру за все время, в зависимости от того, как реализация сокращает и перестраивает хеш-таблицу, когда слишком много элементы удаляются).
Таким образом, чтобы получить более быстрый алгоритм, мы должны хранить другую информацию о хеш-таблице, а не только исходную реализацию. Рассмотрим случай, когда мы индексируем указатели f (n), в которые могут быть вставлены записи. Как поддерживается этот индекс? Возможно, мы выполняем некоторые операции с insert() или remove(). Обновление индекса может быть тривиальным, когда записи вставляются, но если последовательно удаляются записи f (n) (
В заключение, предполагая, что мы не знаем, что с большей вероятностью будет вставлено / удалено, а ключи ha sh распределены равномерно, производительность просмотра произвольного значения должна быть либо O (n), либо иным образом влиять на производительность insert () / remove () по величине.
(Этот вывод может быть полезен. Простое предложение - ленивый рассчитать результат, предполагая, что вызовы remove () выполняются значительно реже по сравнению с поиском произвольных значений)