数组: 用一组连续的内存空间、存储一组具有相同数据类型的线性表数据结构
1
2
| 1.线性表: 数据只有前、后两个方向. 链表、队列、桟也是线性结构
2.连续空间、数据类型相同: 使得数组可以随机访问、但: 插入、删除数据的效率就低很多、需要数据重排
|
插入和删除
1
2
3
4
5
6
7
8
9
10
11
12
| 1.插入
1) 末尾插入、无需移动元素、复杂度 O(1)
2) 头部插入、搬移全部元素、复杂度 O(n)
每个位置插入的概率相同、平均复杂度为 (1+2+3+...n)/n = O(n)
若数组有序、只需要搬移k之后的数据
若数组无序、且不要求有序、将k位置的元素直接搬移到最后、只需要一次搬移 O(1)
2.删除
1) 与插入类似、最好O(1) 最坏O(n) 平均O(n)
2) 删除多(m)个元素时、可先标记删除(只标记)、后一次性删除、节省m*O(n)次操作
JVM的标记清除算法的核心
|
容器能否代替数组 ?
1
2
3
4
5
6
7
8
| 1. arrayList 将数组操作的细节封装. eg. 数据搬移
2. arrayList 支持动态扩容、默认扩容是1.5
扩容涉及到内存申请和数据搬移、比较耗时、若知道数据存储大小时、最好指定大小
1. 容器无法存储基础类型、eg. int, long, 需要封装为 Integer、Long 而自动装箱则有部分性能损耗
2. 若数据大小已知、且操作特别简单、可直接使用数组
所以、对业务开发基本上直接使用容器就好、省力、不易出错、丢失的性能可以不太关注、不影响整体性能
对底层开发、性能要做到极致、数组就优于容器成为首选
|
为什么大部分编程语言中、数组从0开始编号
1
2
3
4
5
6
| 下标确切定义是: 偏移offset、
1.使用a表示首地址、a[0]就是偏移为0的位置、即首地址、a[k]表示第k个type_size的地址
a[k]_addr = base_addr + k*type_size
2.若使用1开始计数、则
a[k]_addr = base_addr + (k-1)*type_size
从1开始编号、对于CPU来说、就是多了一次减法运算
|