Использование хэш-таблицы и карты

Question

Хэш-таблица и карта хэш-таблица реализована как функция хэша, но карта реализована как дерево.

Вопрос в том, в какой ситуации хэш-таблицу нельзя использовать, но карта обязательна?

Answer 1

Одной из мотиваций выбора карты по хеш-таблице является ограничение, которое каждый из них указывает на тип ключа, используемый в создании шаблона. Как описано в the documentation for hash_map in the SGI implementation of STL, конкретизация hash_map требует предоставления функтора, который Хэш К. СТЛ включает в себя функтор, std::hash, который делает это, но он реализован только для ограниченного набора типов Т.

конкретизации станда: : карта с другой стороны требует только функтора, который сравнивает объекты типа K для генерации слабого упорядочения. Стандартный функтор std::less будет работать для любого T, который определяет оператор <.

Это означает, что для многих пользовательских типов добавление поддержки, необходимой для использования этого типа в качестве ключа в std :: map, намного меньше, чем требуется для использования в std :: hash_map.

Помимо вопроса о накладных,

1. Только станд :: Карта, не StD :: hash_map, гарантии того, что ключи будут упорядоченными, так что если это требование, используйте зЬй :: Карты
2. hash_map не является частью стандарта, поэтому, хотя некоторые реализации STL включают его, это не относится ко всем реализациям. Поэтому использование hash_map потенциально влияет на переносимость вашей программы.

Answer 2

Когда вы зависите от того, что ключи отсортированы.

Answer 3

Я собираюсь ответить в отношении std :: unordered_map (хеш-таблица) и std :: map (дерево). Обратите внимание, что ни один из них на самом деле не указывает механизмы реализации. В принципе, вы используете карту, когда вам нужно получить доступ к ключам в отсортированном порядке и в противном случае unordered_map.

Answer 4

Существует ряд потенциальных причин.

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

Answer 5

В время выполнения характеристики различны:

древовидная карты всегда имеет время (в худшем случае, средний случай) в порядке O (LOG п), т.е. высота (сбалансированного) двоичного дерева поиска.

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

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

Answer 6

Если вам нужно найти «следующий» элемент в структуре данных, хеш-таблица не может использоваться, поскольку она не сохраняет элементы в прохождении по порядку.