数组(Array)

数据结构和算法，和语言是无关的

• 数组

  • 数组是一种线性结构，可以在数组的任意位置插入和删除数据
  • 但是有时候为了实现某些机能，需要对这种任意性加以限制
  • 而栈和队列就是比较常见的受限的线性结构

• 底层数组特点

  1. 数组中必须存放相同类型数据

2. 申请数组的内存空间时，必须指定数组大小

• 影响数组性能的要素

  1. 数组扩容
  2. 元素位移

• 数组扩容

  1. numA:16 ➡ 18
  2. 此时底层会申请一个新的，长度扩大1倍的数组 numB:32 []
  3. 将numA中的数据一个个拷贝到numB, 再依次添加17,18
  4. 将numA的内存释放(free)掉
  5. java中ArrayList默认长度是10, 超出10之后继续add的话，数组扩容到15(10 + 10 >> 1
  6. 参考自ArrayList源码private void grow(int minCapacity)

• 元素位移

  1. 在数组最前面插入元素时，元素一个个向后移动
  2. 在中间或者前面插入或者删除元素性能非常低

• 既然有以上的缺点，为什么还要用数组

  1. 因为在日常开发中, 数组存放到数组后，常用的是查找
  2. 由于有下标, 查找的速度非常快(O(1)的性能)

• JavaScript数组底层实现

  1. 实际并不是数组，而是类似于hashMap

  2. 不同时期采用不同实现, 正靠近C的数组实现

  3. Diving deep into JavaScript array