为什么在实现邻接表时，基于散列 table 的数据结构不是默认的？
Why are hash table based data structures not the default when implementing adjacency lists?
我在网上查看了邻接表的一些现有实现，如果不是全部的话，大多数实现都是使用动态数组实现的。但是基于哈希表的数据结构不是更合适吗？ （集和图）
在非常有限的情况下，我们会通过索引访问图节点。即使是这样，如果图中缺少某些指标，也会浪费space。如果节点没有按顺序插入，查找是 O(n).
但是，如果我们使用基于哈希表的数据结构，无论节点是否被索引，查找都将是 O(1)。
那么为什么映射和集合不是实现邻接表时使用的默认数据结构？
选择合适的容器并不容易。
我会考虑一些最常见的：
- 一个列表（包含对下一个 and/or 上一个的引用的元素）
- 一个数组（连续存储）
- 关联数组
- 一个散列table.
它们各有优缺点。
关于列表，插入和删除可能非常快（如果插入点/删除元素已知，则最坏情况为 O(1)）但查找的最坏情况时间复杂度为 O(N)。
如果索引已知，在最坏的情况下，数组中的查找复杂度为 O(1)（但如果必须保持顺序，插入和删除可能会很慢）。
哈希 table 在最好的情况下查找 O(1)，但最坏的情况可能是 O(N)（即使如果哈希 table 并不是完全糟糕的实施）。
关联数组在最坏情况下的时间复杂度为 O(lg N)。
因此，选择始终取决于预期的用例，以找到最佳折衷方案，让优势得到最大回报，而劣势不会造成太大伤害。
对于图中节点和边列表的管理，OP观察到数组似乎很常见。
我最近查看了 Boost Graph Library（出于好奇和灵感）。关于数据结构，提到：
The adjacency_list class is the general purpose “swiss army knife” of graph classes. It is highly parameterized so that it can be optimized for different situations: the graph is directed or undirected, allow or disallow parallel edges, efficient access to just the out-edges or also to the in-edges, fast vertex insertion and removal at the cost of extra space overhead, etc.
配置（根据具体用例），多花了一页BGL – adjacency_list。
但是，顶点（节点）列表和边列表的默认值实际上是向量（又名动态数组）。假设平均用例是一个非 mutable 图（加载一次且从未修改过），由算法探索以回答某些用户问题，在数组中查找的 O(1) 的最坏情况是很难被击败，很可能会得到回报。
为了组织这个，必须枚举节点和边。如果输入数据不提供此信息，则很容易将其作为一种内部 ID 添加到图形的内存表示中。
在这种情况下，“public”节点引用必须映射到内部 ID，答案必须映射回来。对于 public 节点引用的映射，应该使用最合适的容器。这实际上可能是关联的数组或散列 table.
考虑到像这样的请求找到从 A 到 B 的最短路径必须将 A 和 B 一次映射到相应的内部 ID，但可能需要多次查找节点和边来计算答案，选择用于存储节点和边的数组非常有意义.
There are very limited scenarios where we would access graph nodes by index.
这是真的，而且正是您应该考虑的问题：您想要一种数据结构，它可以高效地执行您实际想要使用它执行的任何操作。那么问题来了，你希望哪些操作是高效的？
假设您正在实施某种使用邻接表的标准算法，例如Dijkstra算法，A*搜索，深度优先搜索，广度优先搜索，拓扑排序等等。对于几乎所有像这样的算法，您会发现唯一需要使用邻接表的操作是：对于给定节点，遍历其邻居。
该操作对于动态数组比哈希表更有效，因为哈希表必须足够稀疏以防止太多冲突。除此之外，出于同样的原因，动态数组将使用比哈希表更少的内存；并且动态数组首先构建效率更高，因为您不必计算任何哈希值。
现在，如果您有不同的算法，需要能够在 O(1) 时间内测试边的存在，那么使用哈希表实现的邻接表可能是一个不错的选择；但是你也要考虑是不是邻接矩阵更合适
我在网上查看了邻接表的一些现有实现，如果不是全部的话，大多数实现都是使用动态数组实现的。但是基于哈希表的数据结构不是更合适吗？ （集和图）
在非常有限的情况下，我们会通过索引访问图节点。即使是这样，如果图中缺少某些指标，也会浪费space。如果节点没有按顺序插入，查找是 O(n).
但是，如果我们使用基于哈希表的数据结构，无论节点是否被索引，查找都将是 O(1)。
那么为什么映射和集合不是实现邻接表时使用的默认数据结构？
选择合适的容器并不容易。
我会考虑一些最常见的：
- 一个列表（包含对下一个 and/or 上一个的引用的元素）
- 一个数组（连续存储）
- 关联数组
- 一个散列table.
它们各有优缺点。
关于列表，插入和删除可能非常快（如果插入点/删除元素已知，则最坏情况为 O(1)）但查找的最坏情况时间复杂度为 O(N)。
如果索引已知，在最坏的情况下，数组中的查找复杂度为 O(1)（但如果必须保持顺序，插入和删除可能会很慢）。
哈希 table 在最好的情况下查找 O(1)，但最坏的情况可能是 O(N)（即使如果哈希 table 并不是完全糟糕的实施）。
关联数组在最坏情况下的时间复杂度为 O(lg N)。
因此，选择始终取决于预期的用例，以找到最佳折衷方案，让优势得到最大回报，而劣势不会造成太大伤害。
对于图中节点和边列表的管理，OP观察到数组似乎很常见。
我最近查看了 Boost Graph Library（出于好奇和灵感）。关于数据结构，提到：
The
adjacency_listclass is the general purpose “swiss army knife” of graph classes. It is highly parameterized so that it can be optimized for different situations: the graph is directed or undirected, allow or disallow parallel edges, efficient access to just the out-edges or also to the in-edges, fast vertex insertion and removal at the cost of extra space overhead, etc.
配置（根据具体用例），多花了一页BGL – adjacency_list。
但是，顶点（节点）列表和边列表的默认值实际上是向量（又名动态数组）。假设平均用例是一个非 mutable 图（加载一次且从未修改过），由算法探索以回答某些用户问题，在数组中查找的 O(1) 的最坏情况是很难被击败，很可能会得到回报。
为了组织这个，必须枚举节点和边。如果输入数据不提供此信息，则很容易将其作为一种内部 ID 添加到图形的内存表示中。
在这种情况下，“public”节点引用必须映射到内部 ID，答案必须映射回来。对于 public 节点引用的映射，应该使用最合适的容器。这实际上可能是关联的数组或散列 table.
考虑到像这样的请求找到从 A 到 B 的最短路径必须将 A 和 B 一次映射到相应的内部 ID，但可能需要多次查找节点和边来计算答案，选择用于存储节点和边的数组非常有意义.
There are very limited scenarios where we would access graph nodes by index.
这是真的，而且正是您应该考虑的问题：您想要一种数据结构，它可以高效地执行您实际想要使用它执行的任何操作。那么问题来了，你希望哪些操作是高效的？
假设您正在实施某种使用邻接表的标准算法，例如Dijkstra算法，A*搜索，深度优先搜索，广度优先搜索，拓扑排序等等。对于几乎所有像这样的算法，您会发现唯一需要使用邻接表的操作是：对于给定节点，遍历其邻居。
该操作对于动态数组比哈希表更有效，因为哈希表必须足够稀疏以防止太多冲突。除此之外，出于同样的原因，动态数组将使用比哈希表更少的内存；并且动态数组首先构建效率更高，因为您不必计算任何哈希值。
现在，如果您有不同的算法，需要能够在 O(1) 时间内测试边的存在，那么使用哈希表实现的邻接表可能是一个不错的选择；但是你也要考虑是不是邻接矩阵更合适