Каковы недостатки, если я заменю каждый связанный список в списке смежности с хэш-таблицей?

Question

В CLRS акциз 22.1-8 (я учусь самостоятельно, не в каких университетах)

Предположим, что вместо связанного списка каждая запись массива Adj [u] представляет собой хеш-таблица, содержащая вершины v, для которых (u, v) ∈ E. Если все поиски по краям одинаково вероятны, каково ожидаемое время определить, есть ли ребро в графе? Какие недостатки делает эта схема есть? Предложить альтернативную структуру данных для каждого ребра список, который решает эти проблемы. Есть ли у вашей альтернативы недостатки по сравнению с хеш-таблицей?

Итак, если я заменю каждый связанный список хеш-таблицей, возникнут следующие вопросы:

1. Каково ожидаемое время, чтобы определить, есть ли ребро на графике?
2. Какие недостатки?
3. Предложить альтернативную структуру данных для каждого списка ребер, которая решает эти проблемы
4. Есть ли у вашей альтернативы недостатки по сравнению с хеш-таблицей?

У меня есть следующие частичные ответы:

1. Я думаю, ожидаемое время O (1), потому что я просто перехожу к Hashtable t = Adj [u], а затем возвращаю t.get (v);
2. Я думаю, что недостатком является то, что Hashtable будет занимать больше пробелов, чем связанный список.

Что касается двух других вопросов, я не могу понять.

Кто-нибудь может дать мне подсказку?

Answer 1

Ответ на вопрос 3 может быть бинарным деревом поиска.

В матрице смежности за каждой вершиной следует массив из V элементов.Эта стоимость O (V) -пространства приводит к быстрому (O (1) -время) поиска ребер.

В списке смежности за каждой вершиной следует список, который содержит только n смежных вершин.Этот неэффективный способ приводит к медленному поиску (O (n)).

Хеш-таблица является компромиссом между массивом и списком.Он использует меньше места, чем V, но требует обработки коллизий при поиске.

Бинарное дерево поиска - это еще один компромисс: стоимость пространства минимальна, как у списков, а средняя стоимость времени при поиске равна O(LG N).

Answer 2

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

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

1. Ожидаемое время определения того, находится ли ребро на графике, равно O (н / м)
2. больше места, чем связанный список, и больше времени запроса, чем в матрице смежности. Если наша хеш-таблица поддерживает динамическое изменение размера, то нам потребуется дополнительное время для перемещения элементов между старой и новой хеш-таблицами, а если нет, нам потребуется пространство O (n) для каждой хеш-таблицы, чтобы иметь время запроса O (1), которое приводит к O (n ^ 2) пространство. также мы только что проверили ожидаемое время запроса, и в худшем случае у нас может быть время запроса точно так же, как связанный список (O (степень (u))), поэтому, кажется, лучше использовать матрицу смежности, чтобы иметь детерминированное время запроса O (1) и O (n ^ 2) пробел.
3. читать выше
4. да, например, если мы знаем, что каждая вершина нашего графа имеет не более d смежных вершин и d меньше n, то для использования хэш-таблицы потребуется O (nd) пространство вместо O (n ^ 2) и будет ожидаемое время запроса O (1).

Answer 3

Вопросы 3 и 4 очень открыты.Помимо мыслей из двух других, одна проблема с хэш-таблицей заключается в том, что это неэффективная структура данных для сканирования элементов от начала до конца.В реальном мире иногда довольно часто перечислять всех соседей для данной вершины (например, BFS, DFS), и это каким-то образом ставит под угрозу использование прямой хеш-таблицы.

Одним из возможных решений для этого являетсяобъединить существующие сегменты в хеш-таблицу так, чтобы они образовали двусвязный список.Каждый раз, когда добавляется новый элемент, подключайте его к концу списка;Всякий раз, когда элемент удаляется, удаляйте его из списка и исправьте отношение ссылки соответствующим образом.Если вы хотите выполнить общее сканирование, просто просмотрите этот список.

Недостатком этой стратегии, конечно, является больше места.Существует два указателя на каждый элемент.Кроме того, добавление / удаление элемента занимает больше времени для создания / исправления отношения ссылки.

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