Хеш-таблицы в теории графов

Question

Я читаю статью о хэш-таблицах. Вот фрагмент текста.

Хеш-таблица полезна для любой задачи теории графов, где узлы иметь реальные имена вместо цифр. Здесь, когда ввод читается, вершинам присваиваются целые числа от 1 года в порядке появления. Опять же, ввод, вероятно, будет иметь большие группы в алфавитном порядке записей. Например, вершины могут быть компьютерами. Тогда если один В конкретной установке его компьютеры перечислены как ibm1, ibm2, ibm3,. , , , может быть драматический эффект на эффективность, если дерево поиска б.

Мои квесты по тексту выше

1. Что означает автор: «поскольку входные данные считываются, вершинам присваиваются целые числа от 1 года», разве мы не рассчитываем хеш-ключ для входного чтения?

2. Что автор имеет в виду, что "при использовании дерева поиска может произойти существенное влияние на эффективность"??

3. Как хеш-таблицы полезны в задачах теории графов по сравнению с деревом поиска?

Спасибо!

Answer 1

(1) автор может ссылаться на методы представления графов в матричной форме, как в этом примере

(2) не уверен насчет "деревьев поиска", хотя, если вы можете представить хеш-таблицы в виде графа, есть несколько способов их оптимизации, как в этом примере .

Answer 2

(1) Это карта, а не набор, они, конечно, вычисляют хеш-значение, но узел отображается в целое число, и это цель карты.
(2) Дерево поиска - это поиск O (logn), использование карты на основе дерева поиска увеличит временную сложность всех операций * O (logn).[например, BFS будет принимать O(logV*[V+E)) вместо O(V+E) из-за времени поиска.
(3) Хеш-таблица имеет значение O (1), поэтому сложность времени будет лучше для хеш-таблиц в среднем случае.