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

Question

在 CLRS 练习 22.1-8 中（我是自学而非在任何大学学习），假设每个数组入口 Adj[u] 是一个哈希表，其中包含 (u, v) ∈ E 的顶点 v。如果所有边查找的可能性相等，那么确定边是否在图中的预期时间是多少？这种方案有什么缺点？为每个边列表建议一种替代数据结构来解决这些问题。与哈希表相比，你的替代方法有什么缺点吗？

因此，如果我用哈希表替换每个链表，则会有以下问题：

1. 确定边是否在图中的预期时间是多少？ 2. 有哪些缺点？ 3. 为每个边列表建议一种替代数据结构来解决这些问题。 4. 与哈希表相比，你的替代方法有什么缺点吗？

我的部分回答如下：

1. 我认为预期时间是 O(1)，因为只需执行 Hashtable t = Adj[u]，然后返回 t.get(v)。 2. 我认为缺点是哈希表将占用更多空间。 3. 对于另外两个问题，我还没有头绪。

请问有人能给我一些提示吗？

- Jackson Tale

Answer 1

问题3的答案可能是二叉搜索树。

在邻接矩阵中，每个顶点后面跟着一个包含V个元素的数组。这种O(V)空间成本导致了快速（O(1)-时间）搜索边缘。

在邻接表中，每个顶点后面跟着一个列表，其中只包含n个相邻的顶点。这种节省空间的方式会导致搜索变慢（O(n)）。

哈希表是数组和列表之间的折衷方案。它使用的空间比V少，但需要处理搜索中的冲突。

二叉搜索树是另一种妥协--空间成本与列表相同，而平均搜索时间成本为O(lg n)。

- cxwangyi

---

我喜欢你的回答。我也在考虑同样的做法，即用红黑/自平衡树替换列表。 - Chenna V

或者列表可以保持排序顺序。 - Evgeni Sergeev

Answer 2

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

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

1. 确定边是否在图中的预期时间为O(n/m)
2. 空间比链接列表更大，查询时间比邻接矩阵更长。如果我们的哈希表支持动态调整大小，则需要额外的时间将元素移动到旧哈希表和新哈希表之间，否则我们需要为每个哈希表使用O(n)空间，以实现O(1)查询时间，这会导致O(n^2)空间。我们刚刚检查了预期查询时间，在最坏情况下，我们可能会像链接列表一样具有查询时间（O(degree(u))），因此似乎最好使用邻接矩阵，以获得确定性的O(1)查询时间和O(n^2)空间。
3. 见上文
4. 是的，例如，如果我们知道图的每个顶点最多有d个相邻顶点且d小于n，则使用哈希表需要O(nd)空间而不是O(n^2)，并且预期查询时间为O(1)。

- Ehsan Shoja

Answer 3

问题3和问题4都非常开放式。除了另外两个问题的想法之外，哈希表的一个问题是它不是一种有效的数据结构来扫描从开始到结束的元素。在现实世界中，有时枚举给定顶点的所有邻居（例如BFS，DFS）相当普遍，这从某种程度上妥协了直接哈希表的使用。

解决这个问题的一个可能方案是将哈希表中的现有桶链接在一起，以形成双向链表。每次添加新元素时，将其连接到列表末尾;每当删除元素时，从列表中删除它并相应地修复链接关系。当您想要进行全面扫描时，只需通过此列表即可。

当然，这种策略的缺点是更多的空间。每个元素都有两个指针开销。此外，添加/删除元素需要更多时间来构建/修复链接关系。

我不太担心碰撞。顶点的哈希表存储其邻居，其中每个邻居都是唯一的。如果它的键是唯一的，就没有发生冲突的机会。

- Eric Z

---

如果它的键是唯一的，就不会发生冲突。碰撞的整个意义在于两个不同的键散列到相同的值，而不是这两个键相同。 - xdavidliu

Answer 4

我想在其他答案中没有提到的情况下添加另一个选项。如果图是静态的，即一旦创建了图形，顶点和边不会改变，则可以为每个顶点使用具有完美哈希的哈希表，而不是邻接列表。这将使您能够在最坏情况下以O（1）时间查找顶点之间是否存在边缘，并且仅使用O（V + E）内存，因此渐近地与普通邻接列表相同的内存使用。优点是检查顶点之间是否存在边缘的O（1）搜索时间是最坏情况而不是平均情况。

- tail_recursion