Почему бы не использовать хэширующие/хеш-таблицы для всего?

Ответ 1

Хэш-таблицы, в среднем, имеют отличную временную сложность для вставки, извлечения и удаления. НО:

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

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

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

Все это в стороне, у вас do все еще есть хорошая точка. Hashtables имеют чрезвычайно широкий диапазон подходящих вариантов использования. Вот почему они являются основной встроенной структурой данных на некоторых языках сценариев, таких как Lua.

Ответ 2

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

Ответ 3

• HashTable не является ответом для всех. Если ваша хеш-функция не распределяет ваш ключ, а hashMap может превратиться в linkedList в худшем случае, для которого вставка, удаление, поиск займет O(N) в худшем случае.

• hashMap имеет значительный объем памяти, поэтому есть некоторые варианты использования, когда ваша память слишком ценна, чем временная сложность, тогда вы hashMap, возможно, не лучший выбор.

• hashMap не является ответом на запросы диапазона или префиксные запросы. Поэтому большинство поставщиков базы данных реализуют индексирование с помощью Btree, а не только путем хэширования для запросов диапазона или префикса.

• HashTable в целом демонстрируют плохую локальность ссылки, то есть данные, к которым нужно получить доступ, распределены, по-видимому, случайным образом в памяти.

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

Ответ 4

• Таблицы Hash не сортируются (карта)
• Таблицы Hash не подходят для вставки head/tail (список ссылок /deque )
• В таблицах Hash есть служебные данные для поддержки поиска (вектор/массив)

Ответ 5

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