数组是JS中唯一的0(1)数据结构吗？如果是这样的话，为什么上面的答案会说不一样呢？

Question

假设您正在使用JavaScript中的大型关系数据结构，并且经常需要快速访问这些信息。在JS公开的幕后使用的散列表应该可以以O(1)效率访问大型数据结构。但下面的代码示例将说明，对于普通对象，它不是几乎0(1)。然而，对此的最高回答在讨论数组(因此也是对象)的效率时声称，数组应该执行“就像常规对象值”，利用哈希表：

与大多数实现数组的语言不同，在Javascript数组中，数组是对象，值存储在哈希表中，就像普通的对象值一样。因此：

• 出入- O(1)
• 附加-摊销的O(1) (有时需要调整散列表的大小；通常只需要插入)
• 通过unshift预置- O(n)，因为它需要重新分配所有索引
• 插入-如果值不存在，则摊销O(1)。O(n)如果您想转移现有的值(例如，使用splice)。
• 删除-摊销O(1)以删除一个值，如果希望通过splice重新分配索引，则删除O(n)。
• 交换- O(1)

一些简单的测试表明，在使用JavaScript的V8中，对象和映射只提供O(n)或更糟糕的性能，有时弱映射(但并不总是提供O(1))：

​

​

每次运行时，图表看起来都会有很大的不同，但保持一致的一点是，数组是保持O(1)访问效率的四种数据结构中唯一的JavaScript数据结构。即使是弱地图也不能始终提供0(1)。

​

let count;
let start;
let end;
let access;
let counts = [];

//object speed test

let objData = [];
let obj = {}
count = 0;
// don't raise this above i < 5, the loops will hang
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
  if (i === 1) j -= 100;
  for (let k = 0; k < j; k++) {
    count++;
    obj['s' + count] = true;
  }
  start = performance.now()
  for (let n = 0; n < 1000; n++) {
    // if you access the object iteratively, V8 seems to actually optimize performance massively
    // via prediction, but typically with relational data we have non-iterative use cases.
    // replace the access line with the following to see that performance optimization
    // access = obj['s' + count];
    access = obj['s' + Math.floor(Math.random() * count)];
  }
  end = performance.now()
  objData.push(end - start);
  counts.push(count);
}

//array speed test

let arrData = [];
let arr = []
count = 0;
// don't raise this above i < 5, the loops will hang
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
  if (i === 1) j -= 100;
  for (let k = 0; k < j; k++) {
    count++;
    arr[count] = true;
  }
  start = performance.now()
  for (let n = 0; n < 1000; n++) {
    // if you access the object iteratively, V8 seems to actually optimize performance massively
    // via prediction, but typically with relational data we have non-iterative use cases.
    // replace the access line with the following to see that performance optimization
    // access = obj['s' + count];
    access = arr[Math.floor(Math.random() * count)];
  }
  end = performance.now()
  arrData.push(end - start);
}

// map speed test

let mapData = [];
let map = new Map();
count = 0;
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
  if (i === 1) j -= 100;
  for (let k = 0; k < j; k++) {
    count++;
    map.set('s' + count, true)
  }
  start = performance.now()
  for (let n = 0; n < 1000; n++) {
    access = map.get('s' + Math.floor(Math.random() * count));
  }
  end = performance.now()
  mapData.push(end - start);
}

// weak map speed test

let weakMapData = [];
let weakMap = new WeakMap();
let objs = [];
for (let i = 0; i < 1000000; i++) {
  objs.push({
    data: Math.random()
  });
}
let objsLen = objs.length - 1;
count = 0;
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
  if (i === 1) j -= 100;
  for (let k = 0; k < j; k++) {
    count++;
    weakMap.set(objs[Math.floor(Math.random() * objsLen)], objs[Math.floor(Math.random() * objsLen)]);
  }
  start = performance.now()
  for (let n = 0; n < 1000; n++) {
    access = weakMap.get(objs[Math.floor(Math.random() * objs.length)]);
  }
  end = performance.now()
  weakMapData.push(end - start);
}

let colorSchemes = ['rgb(255, 99, 132)', 'rgb(242, 101, 36)', 'rgb(113, 38, 242)', 'rgb(48, 221, 86)']
var ctx = document.getElementById('myChart').getContext('2d');
var myLineChart = new Chart(ctx, {
  type: 'line',
  data: {
    labels: counts,
    datasets: [{
        label: 'Objects',
        data: objData,
        pointBackgroundColor: colorSchemes[0],
        backgroundColor: 'rgba(0,0,0,0)',
        borderColor: colorSchemes[0],
        borderWidth: 2
      },
      {
        label: 'Maps',
        data: mapData,
        pointBackgroundColor: colorSchemes[1],
        backgroundColor: 'rgba(0,0,0,0)',
        borderColor: colorSchemes[1],
        borderWidth: 2,
      },
      {
        label: 'WeakMaps',
        data: weakMapData,
        pointBackgroundColor: colorSchemes[2],
        backgroundColor: 'rgba(0,0,0,0)',
        borderColor: colorSchemes[2],
        borderWidth: 2,
      },
      {
        label: 'Arrays',
        data: arrData,
        pointBackgroundColor: colorSchemes[3],
        backgroundColor: 'rgba(0,0,0,0)',
        borderColor: colorSchemes[3],
        borderWidth: 2,
      }
    ]
  }
});

<script src="https://cdn.jsdelivr.net/npm/chart.js@2.9.3/dist/Chart.min.js"></script>

<canvas id="myChart" width="400" height="400"></canvas>

​

这个说法正确吗?我的测试是错的吗？还是说声明不准确，对象不能提供与数组相同的访问效率？弱地图不也应该提供0(1)访问吗？

不只是这个答案。MDN弱地图文档在弱映射上的性能优于0(n)，指出替代的一个不便是0(n)效率。

Answer 1

担保

不能保证对数组和对象的查找时间。它可能是O(1)，可能更糟，取决于实现。平均而言，地图查找时间是有保证比O(n)更好：

必须使用哈希表或其他机制来实现Map对象，这些机制平均提供的访问时间与集合中元素的数量呈次线性关系。

现实

到目前为止，V8对对象使用各种不同的表示形式，对于映射使用哈希表，对于数组使用哈希表或数组列表。虽然数组列表和映射都有O(1)查找时间的最佳情况，但Map查找时间可能更糟(如果散列的分布不好)，而对象查找时间可以是从哈希表上的O(1)到对象属性中的O(n)搜索。

观察

比较数字查找时间和字符串查找时间是没有意义的。