В тех случаях, когда у меня есть ключ для каждого элемента, и я не знаю индекс элемента в массиве, hashtables работают лучше, чем массивы (O (1) vs O (n)).
Почему? Я имею в виду: у меня есть ключ, я его хэш... У меня есть хэш. Не должен ли алгоритм сравнивать этот хэш против каждого элемента хэша? Я думаю, что есть какой-то трюк за память, не так ли?
В тех случаях, когда у меня есть ключ для каждого элемента, и я не знаю, индекс элемента в массив, hashtables работают лучше, чем массивы (O (1) vs O (n)).
Поиск хэш-таблицы выполняет O (1) в среднем случае. В худшем случае поиск в хэш-таблице выполняет O (n): когда у вас есть коллизии, а хэш-функция всегда возвращает тот же слот. Можно подумать, что "это удаленная ситуация", но хороший анализ должен ее рассмотреть. В этом случае вы должны перебирать все элементы, как в массиве или связанных списках (O (n)).
Почему? Я имею в виду: у меня есть ключ, я хэш... У меня есть хэш.. не должен алгоритм сравнивать этот хэш против каждого элемента хэш? Я думаю, там какой-то трюк за памятью, не это?
У вас есть ключ, вы хэш его.. у вас есть хеш: индекс хеш-таблицы, где присутствует элемент (если он был ранее). На этом этапе вы можете получить доступ к записи хэш-таблицы в O (1). Если коэффициент нагрузки мал, вряд ли он увидит более одного элемента. Итак, первый элемент, который вы видите, должен быть тем элементом, который вы ищете. В противном случае, если у вас есть несколько элементов, вы должны сравнить элементы, которые вы найдете в позиции, с элементом, который вы ищете. В этом случае у вас есть O (1) + O (number_of_elements).
В среднем случае сложность поиска хеш-таблицы - это O (1) + O (load_factor) = O (1 + load_factor).
Помните, load_factor = n в худшем случае. Таким образом, сложность поиска - это O (n) в худшем случае.
Я не знаю, что вы имеете в виду под "трюком за диспозицией памяти". В некоторых точках зрения хэш-таблица (с ее структурой и разрешением столкновений путем цепочки) может считаться "умным трюком".
Конечно, результаты анализа хеш-таблицы могут быть доказаны математикой.
Хэш-таблицы немного сложнее. Они клали элементы в разные ведра, исходя из их хеша%. В идеальной ситуации в каждом ковше содержится очень мало предметов, и не так много пустых ведер.
Как только вы знаете ключ, вы вычисляете хэш. Основываясь на хеше, вы знаете, какое ведро искать. И, как указано выше, количество элементов в каждом ковше должно быть относительно небольшим.
Таблицы хэшей делают много магии внутри, чтобы убедиться, что ведра настолько малы, насколько это возможно, не потребляя слишком много памяти для пустых ведер. Кроме того, многое зависит от качества ключа → хэш-функции.
Wikipedia предоставляет очень подробное описание хеш-таблицы.
С массивами: если вы знаете значение, вам нужно найти в среднем половину значений (если не отсортировано), чтобы найти его местоположение.
С хешей: местоположение создается на основе значения. Таким образом, учитывая это значение снова, вы можете вычислить тот же хеш, который вы вычислили при вставке. Иногда более одного значения приводит к одному и тому же хешу, поэтому на практике каждое "местоположение" само по себе является массивом (или связанным списком) всех значений хеша в этом месте. В этом случае нужно искать только этот гораздо меньший (если только он плохой хэш) массив.
Таблица хэша не должна сравнивать каждый элемент в хеш. Он будет вычислять хэш-код в соответствии с ключом. Например, если ключ равен 4, то hashcode может быть - 4 * x * y. Теперь указатель точно знает, какой элемент выбрать.
Если он был массивом, ему придется пройти через весь массив для поиска этого элемента.
Думаю, ты ответил на свой вопрос. "не следует, чтобы алгоритм сравнивал этот хэш с каждым хешем элемента". Это то, что он делает, когда он не знает местоположение индекса того, что вы ищете. Он сравнивает каждый элемент, чтобы найти тот, который вы ищете:
например. Скажем, вы ищете элемент под названием "Автомобиль" внутри массива строк. Вам нужно пройти через каждый элемент и проверить элемент. Hash() == "Автомобиль".Hash(), чтобы узнать, что это предмет, который вы ищете. Очевидно, что он не использует хэш при поиске всегда, но пример стоит. Затем у вас есть хеш-таблица. То, что делает хэш-таблица, это создание разреженного массива или иногда массив ведер, как упомянутый выше парень. Затем он использует "Car".Hash(), чтобы вывести, где в разреженном массиве ваш "автомобиль" на самом деле. Это означает, что вам не нужно искать весь массив, чтобы найти ваш элемент.