Какая разница между картой и хэшмапом в STL

Ответ 1

map использует красно-черное дерево в качестве структуры данных, поэтому элементы, которые вы там помещаете, сортируются, а insert/delete - O (log (n)). Элементы должны реализовывать не менее operator<.

hashmap использует хэш, поэтому элементы не сортируются, insert/delete - O (1). Элементы должны реализовывать не менее operator==, и вам нужна хеш-функция.

Ответ 2

hash_map использует хэш-таблицу. Это "постоянное" время в теории. В большинстве реализаций используется хэш-таблица "столкновение". Что на самом деле происходит:

• Он создает большую таблицу
• У вас есть функция "хеш" для вашего объекта, которая генерирует вам случайное место в таблице (случайный вид, но хеш-функция всегда возвращает одно и то же значение для вашего объекта), и обычно это мода фактического 32-битное (или 64-битное) хеш-значение с размером таблицы.
• В таблице показано, доступно ли пространство. Если это так, он помещает элемент в таблицу. Если он не проверяет, есть ли элемент, который вы пытаетесь вставить. Если это так, это дубликат, поэтому нет вставки. Если нет, это называется "столкновением", и он использует некоторую формулу для поиска другой ячейки, и это продолжается до тех пор, пока не найдет дубликат или пустую ячейку.
• Когда таблица заполняется слишком сильно, она изменяется. Эффективная (по времени) реализация сохранит все исходные значения хэша вместе с элементами, поэтому при необходимости он не будет пересчитывать хэши. Кроме того, сравнение хэшей обычно быстрее, чем сравнение элементов, поэтому он может это сделать, в то время как поиск устраняет большинство столкновений как предварительный шаг.
• Если вы никогда ничего не удаляете, это просто. Однако удаление элементов добавляет дополнительную сложность. Ячейка, у которой есть элемент в ней, который был удален, находится в другом состоянии от того, который был всего лишь пустым, поскольку вы, возможно, столкнулись с конфликтами, и если вы просто его очистите, эти элементы не будут найдены. Так что обычно есть "знак". Конечно, теперь, когда мы хотим повторно использовать ячейку, нам все равно придется откладывать ее, если есть дубликат ниже (в этом случае мы не можем вставить эту ячейку), а затем не забудьте повторно использовать удаленную ячейку.
• Обычное ограничение заключается в том, что ваши объекты должны быть реализованы для проверки равенства, но Dinkumware (или был SGI) реализовал их с помощью оператора < который может быть медленнее, но имеет преимущество развязки ваших элементов и типа связанного контейнера, в котором они могут быть сохранены, хотя вам все еще нужна хеш-функция для хранения в хеше.

Теория состоит в том, что если у вас есть достаточно большая таблица, то это постоянное время, то есть оно не зависит от количества фактических элементов, которые у вас есть. На практике, конечно, чем больше элементов, тем больше столкновений происходит.

std:: map использует двоичное дерево. Нет необходимости определять хеш-функцию для объекта, просто строго упорядоченное сравнение. При вставке он рекурсирует вниз по дереву, чтобы найти точку вставки (и есть ли какие-либо дубликаты), и добавляет node, и, возможно, потребуется перебалансировать дерево, чтобы глубина листьев не превышала 1 раз. Время ребалансировки относительно глубины дерева тоже, поэтому все эти операции равны O (log N), где N - количество элементов.

Преимущества хэша - сложность Преимуществами дерева являются:

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

Еще одна проблема с std::map заключается в том, что она использует единственную строго упорядоченную функцию сравнения, в то время как функция "сравнения", которая возвращала -1, 0 или 1, была бы намного более эффективной, особенно с наиболее часто используемым типом ключа, std::string, который уже реализовал эту функцию (это char_traits::compare). (Эта неэффективность основана на предпосылке, что для проверки x==y вы проверяете x<y и y<x, чтобы вы делали два сравнения. Вы сделали бы это только один раз для поиска).

Ответ 3

map - это красно-черное дерево, O(log(n)) время доступа. hash_map (что не является стандартным, однако unordered_map станет стандартным) использует (концептуально) хэш ключа как индекс в массиве связанных списков и, следовательно, имеет наилучшее время доступа O(1) и наихудший случай O(n).

См. http://en.wikipedia.org/wiki/Red-black_tree

Ответ 4

Основное различие - время поиска.

для нескольких данных лучше карта

для большого количества данных лучше hashmap

В любом случае, правильные технические ответы верны.