邻接表最佳实现：Array存储链表和Map存储链表该如何选择？

首先明确结论：确实存在大量优先选择数组实现邻接表的场景，你认为哈希表性能更优是存在前提的，只有在顶点标识非连续/非数值的场景下才成立，以下是优先选数组实现的典型场景：

• 顶点ID为连续整数的场景
  大部分教学案例、算法题中的图顶点都是从0/1开始的连续整数，这种场景下数组的随机访问是无额外开销的纯O(1)操作：直接用下标就能定位到对应顶点的邻接链表，不需要做哈希计算、不需要处理哈希冲突，比哈希表的均摊O(1)实际性能高得多。同时遍历所有顶点时直接循环数组即可，不需要额外拉取哈希表的键列表，遍历效率也更高。
• 大规模稠密图的性能优化场景
  数组是连续内存存储，CPU的缓存预读机制可以充分发挥作用，访问邻接表时的缓存命中率远高于哈希表的随机内存访问。同时哈希表本身存在大量额外存储开销：要存键值对、哈希值、处理冲突的冗余空间，当顶点规模达到十万、百万级别时，数组实现的内存占用比哈希表低30%以上，性能优势会被进一步放大。
• 快速开发/算法竞赛场景
  数组实现的邻接表代码量远低于哈希表实现，以JS为例，只需要一行代码就能完成初始化：const adj = Array.from({length: n}, () => [])，不需要额外封装链表、哈希表的逻辑，也不需要处理键不存在的边界情况，开发效率更高、出错概率更低。

你提供的基于哈希表的邻接表实现逻辑是正确的，这类实现更适合顶点标识为非连续整数、字符串等无法直接作为数组下标的场景，比如存储以用户UUID为顶点的社交关系图，这种场景下用数组会浪费大量空白存储空间，哈希表才是更优选择。

内容的提问来源于stack exchange，提问作者Espresso