动态规划备忘录：HashMap<(usize,i32),i32>与HashMap数组哪个更高效？

当所有索引i都会被用到时，改用[HashMap<i32, i32>]数组确实比单个HashMap<(usize, i32), i32>更高效，核心原因如下：

• 哈希查找开销更低：
  原结构需要对元组(usize, i32)整体计算哈希值、处理碰撞；而数组结构先通过索引i做O(1)的直接定位，再仅对n值做哈希查找，整体查找路径更短，哈希计算的成本也更小。

• 内存局部性更优：
  数组的内存是连续分配的，访问不同i对应的HashMap时，CPU缓存命中率更高；而单个大HashMap的键值对是散列存储的，内存地址分散，缓存友好性远不如数组结构。

针对你提到的状态转移f(i, n) = f(i + 1, 0 to n)、所有i都会被用到的场景，数组结构的优势会被进一步放大：
每个i对应的状态集合（n的取值）被隔离在独立的HashMap中，哈希表的负载因子更低，插入、查找的冲突概率更小，操作效率更高。

额外注意：初始化数组时要提前分配好对应长度（等于i的最大可能值+1），避免动态扩容的开销；而单个大HashMap的全局扩容，当数据量较大时成本会显著高于数组的预分配。

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