Каковы недостатки хэш-карт?

Question

Какой бы язык я ни использовал, я всегда стремлюсь использовать эквивалент хэш-карты. Тем не менее, я проходил некоторые вопросы практического собеседования, и меня спрашивали, каково это ограничение?

Единственная причина, по которой я могу придумать, - это ограниченная основная память, но тогда это не будет ограничиваться только хэш-картами, а также списками ArrayLists и т. Д.

Answer 1

1. В то время как хеш-таблицы имеют постоянную вставку по времени, хеш-таблице иногда требуется увеличивать свою внутреннюю структуру и перегруппировать свои записи. Это операция, стоимость которой пропорциональна текущему размеру хэш-таблицы. Результатом этого является то, что время вставки не всегда согласовано, то есть вставка будет постоянной, O(1), но иногда вы заметите линейную задержку, O(n) по мере роста таблицы. (Эта характеристика поведения привела к тому, что некоторые предложили отдать предпочтение дереву над хеш-таблицей в стандартном / наивном случае.)
2. Вы должны убедиться, что алгоритм хэширования добавляемого вами элемента является правильным. Что это означает, что для произвольного набора элементов результирующие хеш-коды хорошо распределены по диапазону типа хеш-кода (в Java и C # это int). Если у вас есть несколько элементов с одинаковым значением (ноль кого-либо?), Тогда ваша хеш-таблица превратится в сложный связанный список, и производительность значительно снизится.
3. Вы должны убедиться, что хеш-код ваших элементов не изменяется со временем и что метод равенства (Java equals() или .NET Equals()) реализован для сравнения того же набора полей, который использовался для хеша. -код. (В идеале это означает, что объекты, которые вы добавляете в таблицу, являются неизменяемыми, но в качестве альтернативы вы можете вместо этого убедиться, что любые изменяемые поля не имеют отношения к вычислению хеш-кода и используют метод равных: рискованная стратегия. При изменении хеш-кодов таблица Вы не сможете найти записи, которые вы уже добавили в него, когда позже придете, чтобы получить их.
4. Хеш-таблицы, как правило, не сохраняют порядок - будь то естественный порядок или порядок вставки. (Те, которые обычно используют параллельную структуру для поддержания порядка или выполняют относительно дорогую сортировку во время итерации.)

Смотри также:

• http://web.archive.org/web/20090430172748/http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/
• http://en.wikipedia.org/wiki/Hash_table#Drawbacks

Answer 2

Используйте правильную структуру данных для правильной работы.Если вам не нужен доступ по ключу, не используйте Map.

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

Answer 3

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

из Википедия - Хеш-таблицы

Answer 4

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

Answer 5

Одним (очень важным) ограничением является то, что вы не должны использовать их с типами, которые имеют нестабильные (изменяемые) хэш-коды. Вот Эрик Липперт на эту тему .

Answer 6

Использование хэш-карты является ситуативным.

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

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

Answer 7

Недостатком хэш-карты на Java является то, что она не синхронизируется.Если несколько потоков обращаются к хэш-карте одновременно, и хотя бы один из потоков структурно изменяет карту, она должна быть синхронизирована извне.Вы должны обернуть это в Collections.synchronizedMap

Answer 8

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

Answer 9

Они означают, что порядок элементов не сохраняется в HashMap.Следующий вопрос «как решить эту проблему».И ответ таков: используйте LinkedHashMap, чтобы иметь возможность получать элементы в том же порядке, в котором они были вставлены, и TreeMap с соответствующим компаратором для управления порядком по любым критериям, которые вы хотите.

Answer 10

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