图单数组邻接存储与常规邻接表10倍性能差异原因求解

两种实现的性能差距主要来自内存布局、装箱开销、分配开销三个层面的叠加，具体如下：

• 缓存友好性差距
  Graph1的所有邻接节点都存储在单个连续的原生int数组edgeEndpoints中，内存地址完全连续，CPU的缓存预取机制可以大幅提升访问命中率，即使写入阶段有随机访问，所有操作也都落在同一块连续内存区域，缓存行利用率极高。
  而Graph2的邻接表是ArrayList<Integer>[]结构，每个ArrayList是独立的堆对象，其内部存储数据的数组也分散在堆内存的不同位置，访问不同节点的邻接表时需要跳转不同的内存地址，缓存miss率远高于连续数组实现，在百万级节点的场景下差距会被放大。
• 原生类型与装箱的开销差距
  Graph1全程使用int原生类型存储节点编号，无任何装箱拆箱操作。
  而ArrayList只能存储对象类型，每次add整数、访问整数时都需要做int和Integer的自动装箱拆箱，单条操作开销虽然小，但800万次（400万条无向边对应两次add）的累计开销非常可观。
• 内存分配与扩容开销差距
  Graph1仅需要一次性分配3个固定大小的原生数组：edgeEndpoints（长度2*M）、l和r（各长度N），分配次数极少，无额外内存开销。
  而Graph2需要创建N个ArrayList对象，每个ArrayList默认初始容量为10，如果节点度数超过10就会触发扩容：扩容需要重新分配更大的数组、复制原有数据，大量扩容操作会带来极高的额外开销。同时100万个ArrayList对象本身的对象头、元数据也会带来额外的内存占用和访问开销。

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