Я знаю только, что разница между хэшмапом и картой заключается в том, что hashmap реализован с помощью функции хэша, но карта реализована с помощью дерева. Может ли любое тело добавить что-нибудь еще?Есть ли какие-либо вещи hashmap, но карта не может?
Исходя из этого, есть ли какие-либо вещи hashmap, но карта не может?
Hashmaps имеют средний коэффициент улучшения производительности для доступа (O (1)), но хуже худшего исполнения (O (n)). Карты всегда O (lg (n)).
Карты упорядочены по их ключу, hashmaps - нет.
Hashmaps обычно используют больше памяти, чем карты.
Карты обычно позволяют ускорить итерацию.
Хорошие функции хеша сложнее писать, чем хорошие функции упорядочения (и сложнее анализировать).
Я не верю, что есть что-то, что может сделать хэш-карта, что карта не может.
Hashmaps обычно используют больше памяти. – GManNickG
Имо О (1) претензия на хэш-таблицы - это немного обман. Существует фиксированная привязка к числу ключей, распознаваемых как отличные без обработки конфликтов, и как только вы получаете столкновения, производительность ухудшается по сравнению с количеством операций обработки конфликтов (часто O (n)). Хорошо, хэш традиционно поддерживает столько уникальных ключей, сколько вы можете хранить в памяти в любом случае, но мне интересно, сколько людей пренебрегли обновлением пользовательских хеш-вычислений от 32 бит до 64 бит и получат деградацию производительности с очень большими хеш-таблицами. Таблица хэша размера не решит этого, если сам хэш слишком узкий. – Steve314
@Steve - Я упомянул, что O (1) был средним случаем, а O (n) был наихудшим случаем. @GMan - Спасибо, добавлю. –
Карта требует, чтобы ключ имел строгий слабый порядок, который, возможно, не может существовать. Для хэш-функции нужна только хэш-функция. Таким образом, хэш-карта может использоваться с ключами, которые не имеют строгого слабого порядка.
Если честно, деревья и хэшмапы имеют равные проблемы. Это проблема, с которой мне недавно приходилось обращаться с использованием конечных автоматов в качестве ключей. Вы не можете просто сделать хэш (или сравнение) представления в памяти, поскольку эквивалентные автоматы могут иметь разные представления. Решение состоит в том, чтобы получить каноническую форму. После того, как у вас есть каноническая форма, вы можете работать одинаково хорошо из представлений в памяти, независимо от того, сравниваете ли вы или хешируете - и это относится только к любым данным. Если вы можете хэш, вы можете так же легко определить произвольный, но последовательный порядок. – Steve314
Одно преимущество, которое имеет hashmaps над деревьями, состоит в том, что в многопотоковой среде вам не нужно блокировать весь контейнер, чтобы добавить или удалить один ключ - блокировка единственной соответствующей записи в хэш-таблице (почти) достаточно.
Почти потому, что для обновления могут быть метаданные (количество элементов в хэш-таблице, например). Разумеется, вам, вероятно, нужно будет запереть всю таблицу, чтобы расти или сокращать ее.
Тип подобного, возможно, не обман: http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of -ривиальные ключи/ – GManNickG
Будьте осторожны с терминологией. В некоторых кругах «карта» относится только к объекту, который хранит ключ и значение и ищет, а «хэш-карта» - это одна реализация карты. (Где карта деревьев может быть другой.). IOW, «карта» - это интерфейс, а «хэш-карта» - это конкретная реализация. (Я отмечаю это, потому что ваш вопрос не помечен как или не относится к какой-либо конкретной библиотеке.) –
@Ben: В C++ «карта» почти однозначно относится к дереву «std :: map». – GManNickG