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

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



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

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

有什么缺点？

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

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

我有以下部分答案:

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

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

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

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

最佳答案

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

如果元素的分布足够均匀，则查找的平均成本仅取决于每个列表的平均元素数(负载因子)。因此每个列表的平均元素数为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)查询时间。

关于data-structures - 图表-如果我用哈希表替换邻接列表中的每个链表，会有什么缺点？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9667571/