карта — Хеш-таблица в переполнении стека

C ++ имеет unordered_map тип. STL также содержит hash_map типа, хотя это не входит в стандартную библиотеку C ++.

Теперь немного о алгоритмической теории. Можно реализовать хеш-таблицу O (1) в идеальных условиях, и технически хеш-таблицы представляют собой вставку и поиск O (1). Идеальные условия в этом случае состоят в том, что хеш-функция должна быть идеальной (то есть свободной от столкновений), и у вас есть бесконечная память.

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

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

Реализация std::map это дерево. Это прямо не указано в стандарте, но, как говорят некоторые хорошие книги: "It is difficult to imagine that it can be anything else", Это означает, что время вставки / удаления / поиска для карты O (log n).

Классические хеш-таблицы имеют время поиска О (п / num_slots). Как только ожидаемое количество предметов в таблице сравнимо с количеством слотов, у вас будет saturated O (1).