在我的算法课上，我被告知图表示的邻接列表的一个缺点是迭代对应于每个节点的相邻节点数组的O（n）查找时间。我通过使用HashMap来实现我的邻接列表，该HashMap将节点映射到它们相邻节点的HashSet，这难道不只需要O（1）查找时间吗？我错过了什么吗？
如您所知，在HashMap中使用key查找value是O（1）。然而，在邻接列表中，HashMap的值也是其相邻节点的列表。邻接列表的主要目的是迭代相邻节点。例如：图遍历算法，如DFS和BFS。在您的情况下，HashSet。假设HashSet中的元素数量为n。那么即使在HashSet中迭代所有元素也是O（n）。
So, total complexity would be O(1)+O(n).
Where O(1)= look up in HashMap
O(n)= iterate all the elements
通常，邻接列表对于稀疏图更可取，因为它是只有几条边的图。这意味着每个节点（HashMap的键）中相邻元素的数量较少。因此查找元素不会花费更多。
我通过使用将节点映射到其相邻节点的HashSet的HashMap来实现我的邻接列表，那不只需要O（1）查找时间吗？[强调我的]
没错——但是“邻接列表”通常意味着表示为数组或链表，而不是HashSet：换句话说，邻接列表被优化为遍历顶点的邻居，而不是查询两个顶点是否是邻居。
与邻接列表相比，生成更具时间效率的图表示是可能的，特别是对于顶点顶点通常有许多边的图。
使用顶点映射，其中每个顶点都包含相邻顶点和/或边缘对象的映射，我们可以通过索引顶点id，然后索引邻居来查看节点是否在O（1）时间内连接。这可能比邻接列表节省了很大的成本，在邻接列表中，我们可能必须遍历许多边才能找到特定的邻居。此外，地图的数据结构可以允许我们在边缘对象中存储任意数据。这对于加权图和动作/边的特征很有用
