Почему поиск hashmap - это O (1), то есть постоянное время?

Ответ 1

Исходя из соответствующих предположений об используемой хэш-функции, мы можем сказать, что поиск в хэш-таблице занимает ожидаемое время O (1) (при условии, что вы используете стандартную схему хеширования, такую как линейное зондирование или цепное хеширование). Это означает, что в среднем объем работы, выполняемой хеш-таблицей для поиска, не более чем постоянный.

Интуитивно понятно, что если у вас есть "хорошая" хеш-функция, вы ожидаете, что элементы будут распределены более или менее равномерно по всей хеш-таблице, а это означает, что количество элементов в каждом сегменте будет близко к числу элементов, деленному на число. ведер. Если реализация хеш-таблицы поддерживает это число на низком уровне (скажем, путем добавления большего количества сегментов каждый раз, когда отношение элементов к сегментам превышает некоторую константу), то ожидаемый объем работы, который выполняется, в конечном итоге составляет некоторый базовый объем работы, чтобы выбрать, какой сегмент следует сканировать, а затем выполнять "не слишком много" работы, просматривая элементы там, потому что в ожидании в этом сегменте будет только постоянное количество элементов.

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

Для получения дополнительной информации вы можете прочитать учебник по алгоритмам, чтобы увидеть формальный вывод, почему хеш-таблицы поддерживают поиск так эффективно. Обычно это входит в состав типичного университетского курса по алгоритмам и структурам данных, и в Интернете есть много хороших ресурсов.

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

Надеюсь это поможет!

Ответ 2

Ключ находится в этом документе в документах:

Если многие экземпляры должны храниться в экземпляре HashMap, создание его с достаточной большой емкостью позволит сохранять снимки более эффективно, чем позволить ему автоматически выполнять перезагрузку по мере необходимости для роста таблицы.

и

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

http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html

Внутренняя структура ковша будет фактически перестроена, если коэффициент нагрузки будет превышен, учитывая, что амортизированная стоимость get и put будет равна O (1).

Обратите внимание, что если внутренняя структура перестраивается, это вводит штраф за производительность, который может быть O (N), поэтому довольно много запросов на получение и размещение могут потребоваться до того, как амортизационная стоимость снова приблизится к O (1). По этой причине планируйте начальную мощность и коэффициент загрузки соответствующим образом, чтобы вы не теряли площадь и не вызывали предотвратимую перестройку внутренней структуры.

Ответ 3

Чтобы следить за комментариями templatetypedef:

Реализация хэш-таблицы с постоянным временем может быть хэш-маской, с помощью которой вы можете реализовать список логических массивов, который указывает, существует ли конкретный элемент в ведре. Однако, если вы используете связанный список для своей хэш-карты, худший случай потребует, чтобы вы проходили через каждое ведро и проходили по концам списков.