Мое понимание в HashMap заключается в том, что порядок непредсказуем, поэтому время поиска также непредсказуемо. Но мне задали этот вопрос в недавнем интервью "Есть ли ситуация, когда у HashMap есть определенное время поиска?"
HashMap - это вероятностная структура данных со средней сложностью времени поиска O (1). Однако поиск может занять до O (n) в худшем случае.
Существует множество "особых" случаев, когда хэш гарантированно выполняет поиск в O (1) раз.
Например:
Если все ключи известны заранее, можно создать "идеальную" хеширующую функцию, которая гарантирует случай №3. Это используется на практике для создания таблиц поиска символов, где заранее известен набор символов (строк).
Видеть:
hashMap
имеет переменное время поиска.. !!
hashMap
находит местоположение с помощью хэш-функции. Но для хэш-функции требуется некоторое время. Его в основном алгоритм, поэтому выполнение этого алгоритма требует некоторого времени. !!
Следующее - это то, что даже если хеш-функция завершается, она создает одно и то же место для нескольких записей (в некоторых случаях). Поэтому в этом случае он хочет выглядеть глубже. Это тоже занимает больше времени. !!
Единственный случай, когда
hashMap
указывает на записи, которые имеют общее время поиска, состоит в том, что данные всегда должны создавать уникальныйhashKey
. То есть, время всегда будет равным выполнению алгоритма хеширования.
Но в случае массива Время поиска всегда одно и то же, поскольку он обеспечивает прямой доступ к местоположению массива, время всегда равно O (1).
java.util.HashMap
).