在JavaScript中用哈希表替代二维数组实现网格：O(1)查找及复杂度疑问

1. 哈希结构能否替代二维数组实现网格？ #

完全可以。传统二维数组若需遍历查找元素，时间复杂度为O(n*m)，而哈希结构可让坐标定位的读写、查找操作均达到O(1)，更适合频繁按坐标访问的场景。

2. 如何创建支持O(1)查找的哈希网格？ #

你给出的gridObj = [{}, {}, ...]框架是可行的：用外层数组存储行，每行对应一个对象，对象的键为列索引（或自定义列标识），值为对应单元格的数据。通过行索引+列键可直接定位单元格，实现O(1)读写。

示例实现： #

// 初始化5行的哈希网格
let gridObj = Array.from({ length: 5 }, () => ({}));

// 设置指定坐标的值（行、列索引从0开始）
gridObj[1][2] = 10;

// 获取指定坐标的值（O(1)操作）
console.log(gridObj[1][2]); // 输出 10

// 遍历所有非空单元格（仅遍历有数据的项，比二维数组全遍历高效）
for (let rowIdx = 0; rowIdx < gridObj.length; rowIdx++) {
  const row = gridObj[rowIdx];
  for (const colKey in row) {
    console.log(`(${rowIdx}, ${colKey}): ${row[colKey]}`);
  }
}

若需要更灵活的结构，也可使用单个对象存储所有坐标，将行-列拼接为唯一键：

let gridMap = {};

// 设置值
gridMap["2-3"] = 20; // 表示第2行第3列

// 获取值
console.log(gridMap["2-3"]); // 输出 20

3. 能否创建同时具备O(1)时间复杂度和O(1)空间复杂度的网格？ #

无法实现通用的全量网格同时满足O(1)时间与O(1)空间：

• O(1)空间意味着内存占用不随网格规模（行、列数）变化，但全量网格需存储每个单元格的数据，空间复杂度至少为O(n*m)，与网格大小正相关。
• 若为稀疏网格（多数单元格为默认值，仅存储非默认值项），空间复杂度可优化为O(k)（k为非默认值单元格数量），读写仍保持O(1)，但这并非严格的O(1)空间。
• 特殊场景下，比如网格所有单元格的值可通过公式动态计算（如所有值为0，或值等于行号+列号），此时无需存储任何数据，直接通过公式返回结果，可做到O(1)时间（计算）+O(1)空间（无存储），但这属于逻辑网格，而非实际存储数据的网格。

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