У меня вопрос с hash_map и map в С++. Я понимаю, что map находится в STL, но hash_map не является стандартом. Какая разница между двумя?
Map vs. hash_map в С++
Ответ 1
Они реализованы по-разному.
hash_map (unordered_map в TR1 и Boost; используйте их вместо этого) используйте хеш-таблицу, где ключ хэшируется в слот в таблице, и значение сохраняется в списке, привязанным к этому ключу.
map реализуется как сбалансированное двоичное дерево поиска (обычно это дерево красного/черного).
An unordered_map должен давать немного лучшую производительность для доступа к известным элементам коллекции, но map будет иметь дополнительные полезные характеристики (например, он хранится в отсортированном порядке, что позволяет обход от начала до конца). unordered_map будет быстрее при вставке и удалении, чем a map.
Ответ 2
hash_map - общее расширение, предоставляемое многими реализациями библиотек. Именно поэтому он был переименован в unordered_map, когда он был добавлен в стандарт С++ как часть TR1. карта обычно реализуется со сбалансированным двоичным деревом, подобным красно-черному дереву (реализации, конечно, различны). hash_map и unordered_map обычно реализуются с помощью хеш-таблиц. Таким образом, порядок не поддерживается. unordered_map insert/delete/query будет O (1) (постоянное время), где map будет O (log n), где n - количество элементов в структуре данных. Таким образом, unordered_map работает быстрее, и если вам не нужно, чтобы порядок элементов был предпочтительнее map. Иногда вы хотите сохранить порядок (упорядоченный по ключу), и для этого map будет выбор.
Ответ 3
Некоторые из ключевых различий в требованиях сложности.
Для отображения требуется O (log (N)) время для вставок и находок.
Unordered_map требует "среднего" времени O (1) для вставок и находок, но ему разрешено иметь наихудшее время O (N).
Итак, как правило, unordered_map будет быстрее, но в зависимости от ключей и хэш-функции, которую вы храните, может стать намного хуже.
Ответ 4
Спецификация С++ не говорит точно, какой алгоритм вы должны использовать для контейнеров STL. Однако он создает определенные ограничения на их производительность, что исключает использование хеш-таблиц для map и других ассоциативных контейнеров. (Они чаще всего реализуются с красными/черными деревьями.) Эти ограничения требуют лучшей производительности в худшем случае для этих контейнеров, чем могут предоставлять таблицы хешей.
unordered_map и такие к более поздним версиям стандарта С++. Ответ 5
Я не знаю, что дает, но hash_map занимает более 20 секунд, чтобы очистить() 150K беззнаковых целочисленных ключей и значений float. Я просто бегу и читаю код другого.
Вот как он включает hash_map.
#include "StdAfx.h"
#include <hash_map>
Я читал это здесь https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap
говоря, что clear() - порядок O (N). Это мне очень странно, но, что так оно и есть.