карта — Хеш-таблица в переполнении стека
Является ли время вставки / удаления / поиска C ++ std::map O(log n)? Можно ли реализовать O(1) хеш-таблица?
Решение
Является ли время вставки / удаления / поиска карты C ++ O (log n)?
Да.
Можно ли реализовать хеш-таблицу O (1)?
Определенно. Стандартная библиотека также предоставляет std::unordered_map.
Другие решения
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).