知识反刍--数组

发表于   |   更新于 | | 阅读数
字数统计 1.8k 字 | 阅读时长 6 分钟

知识反刍–数组

学而不思则惘

起因：

  1. 学习这种事最怕一知半解而不自知，验证自己是否一知半解甚至错误理解的方式，就是看能否通过简单易懂的方式将概念表达出来；如果在尝试阐述的过程中遇到了停顿和迷茫，那说明需要回到知识源头重新学习
  2. 也是为了检验自己是否真的学进去了，而不是用战术上的勤奋掩盖战略上的懒惰

数组：

  1. 什么是数组？：

    1. 一种线性的数据结构，线性指的是其中数据的存储方式是像一条线一样连接在一起的
    2. 它使用的是一块连续的内存空间，这里的连续是指物理上的连续，也就是一整块的内存空间
    3. 存储着相同类型的数据
    4. 数组就像是一排规格一致的储物柜，柜子按照编号排列，每个柜子的大小都是相同的；想从哪个柜子里存取东西的时候，根据柜子的编号用钥匙去打开就行

  2. 数组为什么可以做到随机访问？

    1. 数组占据了一整块连续的内存空间，而且存储着相同类型的数据，意味着每一个数据之间的空间间隔是一致的
    2. 假设长度为10的整型数组，内存中的起始位置是1000，32位的int类型占据4个字节，则整个数组的内存地址为1000 ~ 1039 ，每个数据的间隔为 4 个字节，依次为 ： 10001003，10041007，10081011…10361039，转换成公式表示：数组的起始内存地址为 bas_address =1000 ，存储的数据类型单位长度为 4字节，则第n个数据的内存地址范围可以表示为 ： base_address + 4n ~ base_address + 4n -1；因此能够根据偏移量做到随机访问
    3. 就像你要打开第5个柜子，你站在柜子前面，一眼就能看到编号为5的柜子哪里

  3. 数组为什么不适合删除和插入？

    1. 根据前面的随机访问特性实现我们可以知道：数组只有维护连续的内存空间才能支持根据偏移量的随机访问，如果内存块中空缺了一块，而又刚好定位到那一块内存的时候，如果那块内存没有被占用就会返回空，如果不慎被其他数据占用，则会返回错误的结果，数组的偏移量就没有意义了
    2. 所以，数组在进行数据插入和删除的情况下，如果插入和删除位置都不是最后一个位置的话，每次插入和删除都需要进行一部分数据的移动操作，保证数组的内存空间连续
    3. 类似于柜子管理员要求要按照编号顺序使用柜子，中间柜子有空的，就把后面柜子的东西往前放，然后重新给你们分配钥匙；又或者有新来的死活要用中间的柜子，那就得把中间柜子空出来，往后挪出一格给他

  4. 有没有办法优化删除？

    1. 数组的删除需要将被删除位置之后的数据都往前移动一位，维持内存空间连续性，这个操作是很繁琐的
    2. 如果每次删除一个数据，都暂时先将它标记成删除状态，等到数组空间不足无法插入新数据再将标记为删除状态的数据进行删除，进行一次整体的数据移动，就会显得高效很多
    3. 类似于如果中间柜子空了，贴个字条写上是空的，有新来的人也只给他分配最后面的空的柜子；等到后面柜子不够用了，再来看看有哪些是空柜子，然后大家自觉把东西挪一挪，重新分配下钥匙，就可以在后面空出一些空的柜子给新人

  5. 容器能否代替数组？

    1. 不能
    2. 容器不能存储基本类型，如果声明泛型容器，参数化类型必须是继承自Object的引用类型，基本数据类型不在此列 ；虽然有基本类型的包装类可以进行自动拆箱装箱达到存储基本类型的目的，但是如果存储了相当量级的包装类，每一次的拆装箱都会损耗性能；因此使用泛型无法达到直接使用原始数据类型那样的高效表现
    3. 在数据量已知的情况下，使用固定长度的数组会比使用容易适合

  6. 你还知道什么关于数组的东西？

    1. 数组协变，泛型不变：
      1. 数组协变：如果 A是B的子类，则数组 A[] 也可以看作是数组 B[] 的子类，可能会导致运行时异常 ，例如 Object[] a = new Long[10]; a[0] = "test str";会抛出运行时异常 ： ArrayStoreException
      2. 泛型不变：对于任意的类型A,B ，List 和 List之间不存在任何父子关系。你可以从标有动物类别的箱子里拿出任意一只动物来，但是你不能从标有宠物狗的箱子里拿出一只猫来，这样的话这个宠物狗的标记将毫无意义。参考这个回答
    2. 数组类型运行时可知；泛型类型编译时可知，运行时擦除类型：
      1. 正如数组协变的描述那样，数组在运行时才会确存储的数据类型是否符合数组声明，因此可能导致运行时异常
      2. 而泛型在编译期间强制要求类型一致性，无法往A类型的的泛型容器中，插入B类型，会因为类型不一致导致编译错误。而在运行时，泛型的类型是被擦除的，为了和引入泛型之前的代码结合在一起使用。因为泛型在编译期已经确保了数据类型的一致性，泛型擦除后即使所有的类型都当作对象类型来看待，它们本身也还是一样的类型，显式的强制类型转换也不会导致转型异常，这样它们才能正常编译并一起使用

使用简单易懂的方式来阐述数组和数组有关的操作：

  1. 结构：一个数组就象是一排挨在一起的储物柜，按照各自的编号排列，有对应各自编号的钥匙，用来打开柜子：

    结构

  2. 删除操作：在数组中删除数据就像相当于把某个柜子清空，然后后面柜子的物品往前一个柜子移动，直到中间没有空柜子：

    ​

  3. 但是每次删除都这样清空柜子比较麻烦，因此可以先记录所有的空柜子，等待有新人没有柜子可以使用，再将空柜子一次占满，空出后面的柜子给新人用：