数组

一.为何编程语言的数组下标从0开始

1.从数组内存存储类型来看，数组的下标可以看作“偏移量”--offset；如果a为首地址，那么a[0] 就是偏移量为0的位置。
2.历史原因：C 语言设计者用 0 开始计数数组下标，之后的 Java等其它语言开始使用，这样节省了学习成本。
3 . 内存地址计算方法：

• 一维数组：a[k]_address = base_address + k * type_size
• 二维数组：二维数组假设是mn， a[i][j]_address=base_address + (in+j)*type_size
• 三维数组：假设mnq， a[i][j][k]_address=base_address + (inq + jq + k)type_size

二.如何实现随机访问

1.数组

• 一种线性表，每个线性表上的数据最多只有前和后两个方向。
• 连续的内存空间和相同的数据类型。
• 这两种限制同时赋予了数组一种特质：随机访问；但为了保衡数据的连续性，那么插入，删除操作变得低效，需要对数据进行搬运行为。

2.数组如何实现下标的随机访问

• 计算机会给每个内存单元分配一个地址，通过地址来访问内存。计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址方法寻找：
  a[k]_address = base_address + k * type_size

• 数组和链表的区别纠错
  数组是适合查找操作，但是查找的时间复杂度并不为 O(1).数组支持随机访问，根据下标的 随机访问的时间复杂度为O(1).

三.一些别的思考

• 插入操作：
  如果数组中数据时无序的，而且只当作一种存储集合，为了避免大规模的数据搬运，可以直接将第K位的数据搬运到数组的最后。
• 删除操作：
  不必追求数组中的数据的连续性，将多次删除操作集中在一起，删除的效率会提高。因为每一次删除后，都要重新搬运数据（为了内存的连续性）。
  我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬运数据，而是做一个已删除的标记，等到存储空间没有更多的空间时，一次性删除被标记的数据。-----JVM的标记清理垃圾回收算法的核心思想。
• 数组的下标越界问题。
  C语言中的数组下标越界是一种未决行为，没有规定下标越界时编译器应该如何处理。因为访问数组的本质就是方位一段连续的内存地址，只要数组通过计算偏移后得到的地址时可用的，就不会报错。
  JAVA中本身就会检测下标越界，抛出异常。

四.数组和容器

比如数组和ArrayList容器。

• 容器的优势
  将很多数组操作的细节隐藏起来。实现了动态扩容。
• 数组的优势
  容器无法存储基础类型int等，只能包装后Integer使用，浪费了性能。更关注性能，一般用于底层开发。

五.标记清除垃圾回收算法

基本算法：

• 由标记阶段 和 清除阶段构成
• 标记将所有的活动的对象打上标记。
• 清除即将将那些没有标记的对象进行回收。

标记与清除

• 遍历GC,ROOT引用，递归标记（设置对象头中的标志位）对象；
• 标记时如果标记位已被标记已跳过
• 遍历对象有深度优先遍历和广度优先遍历，其搜索步骤一致，但是深度优先的内存使用量更小，因此一般使用深度优先遍历。
• 清除阶段将再次遍历堆，未标记的对象加入到空闲表中，标记的对象则出区标记。

分配与合并

• 分配指mutator申请分块时获取内存块的过程。
• 分配即通过搜索空闲链表，找到一个大小合适的块。分配测量有如下：First-fit，找到第一个大于要求大小的块即返回；Best-fit，找到比要求大小大的最小块；Worst-fit，找出最大的块将其分割成要求大小块和剩余的，一般不使用(容易产生碎片)。
• 对于内存中连续的垃圾可以对其进行合并，减少碎片。

优缺点：

• 优点：
  1.算法实现简单。
  2.与保守式GC算法兼容(对象不能被移动)。
• 缺点
  1. 碎片化。
  2. 分配速度慢，每次分配需要遍历空闲链表。
  3. 与写时复制(copy-on-write)冲突，因为做GC时需要将对象头进行标记，这将导致大量的数据发生复制
  4. STW(Stop-The-World)长，两个阶段均要遍历整个堆。