Итерация через HashSet против связанного Hashset

Question

Я думаю о способах представления графа в памяти?

Я думал использовать карты ha sh для карт ha sh, чтобы он вел себя подобно матрице смежности, но мы можем использовать сопоставимые метки ребер вместо целых чисел.

В алгоритмах поиска в ширину и алгоритма Дейкстры мы должны выполнить итерации по спискам смежности и добавить узлы в очередь. Это приводит к моему вопросу:

Является ли итерация через связанный набор ha sh более эффективной, чем итерация через обычный HashSet в Java?

Кажется, что это произошло бы потому, что между каждым узлом есть ссылки в том порядке, в котором они были добавлены, поэтому нам не нужно перебирать пустые корзины, если они существуют (в зависимости от коэффициента повторного хэширования HashMap, это может быть больше или меньше). Это позволило бы нам объединить поведение произвольного доступа матрицы смежности с эффективностью алгоритма поиска списка смежности.

Answer 1

Да, вы правы.

Java HashMap / Set имеет низкую производительность в разреженном графике, потому что он должен повторяться из пустых корзин. Когда большинство узлов подключено только один другой узел. HashMap / Set может занять 8 итераций, чтобы получить точный результат. Соответствующий анализ можно найти в Codeforces: производительность ha sh набор итераторов на разных языках программирования .

Для представления графа механизм Java generi c может позволить Вы создаете тип объекта для примитивного типа, например, Integer. Они снизят производительность при преобразовании в примитивный тип и построении графа. В лучшем случае вам нужно использовать Trove или другую библиотеку. Возможно, реализовать самостоятельно.