data-structures - 图表-如果我用哈希表替换邻接列表中的每个链表，会有什么缺点？

Question

在CLRS消费税22.1-8中(我是自学成才，不在任何大学中)

Suppose that instead of a linked list, each array entry Adj[u] is a hash table containing the vertices v for which (u,v) ∈ E. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in the graph? What disadvantages does this scheme have? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table?

因此，如果我用哈希表替换每个链表，则存在以下问题:

，确定图表中是否存在边的预计时间是多少？

有什么缺点？

为每个边缘列表建议替代数据结构，以解决这些问题

与哈希表相比，您的替代方法是否有缺点？

我有以下部分答案:

我认为预期时间是O(1)，因为我只是去哈希表t = Adj [u]，然后返回t.get(v);

我认为缺点是哈希表将比链接列表占用更多空间。

对于其他两个问题，我一无所知。

有人可以给我一个提示吗？

Answer 1

它取决于哈希表及其处理冲突的方式，例如，假设哈希表中的每个条目都指向具有相同键的元素列表。

如果元素的分布足够均匀，则查找的平均成本仅取决于每个列表的平均元素数(负载因子)。因此每个列表的平均元素数为n / m，其中m是哈希表的大小。

判断图中是否存在边的预期时间为O(n / m)

比链接列表更多的空间，比邻接矩阵更多的查询时间。如果我们的哈希表支持动态调整大小，那么我们将需要额外的时间在旧哈希表和新哈希表之间移动元素，否则，每个哈希表将需要O(n)空间，以便获得O(1)查询时间导致O(n ^ 2)空间。我们也刚刚检查了预期的查询时间，在最坏的情况下，查询时间可能像链表(O(degree(u)))一样，因此最好使用邻接矩阵来确定O(1)查询时间和O(n ^ 2)空间。

阅读以上

是，例如，如果我们知道图的每个顶点最多具有d个相邻顶点且d小于n，则使用哈希表将需要O(nd)空间而不是O(n ^ 2)，并且期望O (1)查询时间。