какая разница между map и hashmap в STL [дубликат]

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

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

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

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

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

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

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

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

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

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

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

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

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