面试题：JavaScript稀疏数组内存优化的方法探讨

Question

当处理大型稀疏数组时，内存管理成为关键问题。请阐述至少两种优化JavaScript稀疏数组内存使用的策略，并分析每种策略的优缺点。

Answer 1

策略一：使用对象模拟稀疏数组

• 实现方式：用对象的键值对来模拟数组结构，键表示数组索引，值为对应位置的元素。例如：

let sparseObject = {};
sparseObject[10] = 'value';

• 优点：
  • 内存高效，仅存储实际存在的元素，对于稀疏数组能显著节省内存。
  • 灵活，可随时添加或删除元素，不受固定数组长度限制。
• 缺点：
  • 索引操作性能相对较差，因为对象查找不是基于连续内存，需要遍历哈希表，时间复杂度平均为O(1)，但在极端情况下可能退化到O(n)。
  • 丢失了数组的一些原生特性，如长度属性不能直观反映实际元素数量，也无法直接使用数组的某些方法（如 map、reduce 等，需额外处理）。

策略二：使用 TypedArray 结合位运算优化

• 实现方式：利用 TypedArray（如 Uint8Array、Uint16Array 等）存储数据，结合位运算来表示稀疏性。例如，使用一个 Uint8Array 来存储数据，同时用另一个 Uint8Array 来标记哪些位置有数据。

let dataArray = new Uint8Array(1000);
let flagArray = new Uint8Array(1000);
function setValue(index, value) {
    dataArray[index] = value;
    flagArray[index >> 3] |= 1 << (index & 7);
}
function getValue(index) {
    if (flagArray[index >> 3] & (1 << (index & 7))) {
        return dataArray[index];
    }
    return undefined;
}

• 优点：
  • 内存使用效率高，TypedArray 存储更紧凑，并且通过位运算标记稀疏位置进一步优化。
  • 对于数值类型数据有较好的性能，TypedArray 操作在现代JavaScript引擎中经过优化，执行速度快。
• 缺点：
  • 实现复杂，需要额外的数组和位运算逻辑，增加了代码的复杂性和维护成本。
  • 不适合存储非数值类型数据，对于字符串、对象等类型需要额外的处理方式。