BST - это дерево двоичного поиска. Используется для словаря. BST не имеет ограничений по структуре, и поэтому поиск / вставка / удаление является O (n) худшим случаем.
Карта [на stl] также является словарем и фактически является красно-черным деревом [на stl]. это особый тип BST, который имеет ограничения на структуры, поэтому поиск / вставка / удаление в худшем случае - O (logn).
хэширование хеш-таблица - это другой тип словаря, преимущество хеш-таблицы [с хорошими хеш-функциями] составляет O (1) среднее время поиска / удаления / вставки. однако наихудший случай - O (n), который происходит, если сталкивается слишком много элементов и / или когда требуется перефразировка [когда баланс нагрузки слишком высок, мы выделяем больший массив и перефразируем все элементы в is].
Попытки специально для строк. все операции O (S), где S - длина строки. у других [при работе со строками] преимущество заключается в том, что вам все равно нужно читать строку, поэтому сложность, например, если Map при работе со строками, фактически равна O (S * n * logn).
когда использовать?
a Map [или любое другое сбалансированное дерево] почти всегда должно быть лучшим выбором, чем обычный BST.
hash table - хороший выбор, если вы хотите получить среднее короткое время, но не обращайте внимания на то, что в некоторых случаях вы будете терять производительность из-за перефразирования, а в некоторых случаях могут возникать коллизии.
Trie обычно хороший словарь для строк.