图 - 如果我使用哈希表替换邻接列表中的每个链接列表有什么缺点？ [英] graph - What are the disadvantages if I replace each linked list in adjacency-list with hash table?

问题描述

在CLRS消费税22.1-8（我是自学，不在任何大学）

In CLRS excise 22.1-8 (I am self learning, not in any universities)

假设，而不是链表，每个数组条目Adj [u]是一个
哈希表，其中包含（u，v）∈E的顶点v。如果所有
边缘查找同样可能，那么预期的时间是
确定边是否在图中？这个计划有哪些不利条件？为每个边缘建议一个替代数据结构
列表来解决这些问题。您的替代方案与哈希表相比有
的缺点吗？

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?

所以，如果我用哈希表替换每个链表，有以下问题：

So, if I replace each linked list with hash table, there are following questions:

1. 确定边缘是否在图形中的预期时间是多少？


2. 有什么缺点？


3. 为解决这些问题的每个边缘列表建议一个替代数据结构


4. 您的替代方案与哈希表？

1. what is the expected time to determine whether an edge is in the graph?
2. What are the disadvantages?
3. Suggest an alternate data structure for each edge list that solves these problems
4. Does your alternative have disadvantages compared to the hash table?

我有以下部分答案：

1. 我认为预期的时间是O（1），因为我刚刚去Hashtable t = Adj [u]，然后返回t.get（v）;


2. 我认为缺点是Hashtable将占用更多的空间，然后链接列表。

对于其他两个问题，我无法得到一个线索。

For the other two questions, I can't get a clue.

任何人都可以给我一个线索？

Anyone can give me a clue?

推荐答案

这取决于哈希表以及它如何处理冲突，例如假设在我们的散列表中，每个条目都指向具有相同键的元素列表。

It depends on the hash table and how it handles collisions, for example assume that in our hash table each entry points to a list of elements having the same key.

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

If the distribution of elements is sufficiently uniform, the average cost of a lookup depends only on the average number of elements per each list(load factor). so the average number of elements per each list is n/m where m is the size of our hash table.

1. 预计的时间来确定图中边缘是否比链接列表更多的空间超过邻接矩阵。（n / m）


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）查询时间。

1. The expected time to determine whether an edge is in the graph is O(n/m)
2. more space than linked list and more query time than adjacency matrix. If our hash table supports dynamic resizing then we would need extra time to move the elements between the old and new hash tables and if not we would need O(n) space for each hash table in order to have O(1) query time which results in O(n^2) space. also we have just checked expected query time, and In worst case we may have query time just like linked list(O(degree(u))) so it seems better to use adjacency matrix in order to have deterministic O(1) query time and O(n^2) space.
3. read above
4. yes, for example if we know that every vertices of our graph has at most d adjacent vertices and d less than n, then using hash table would need O(nd) space instead of O(n^2) and would have expected O(1) query time.

这篇关于图 - 如果我使用哈希表替换邻接列表中的每个链接列表有什么缺点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！