大家好，又见面了，我是你们的朋友全栈君。
今天我们来谈谈数组、列表和扩容，以及自写List和Java自带类ArrayList的异同。
Java学习笔记
第一节 Java 类与对象以及继承 第二节 Java 对象的保存和传递 第三节 Java 数组和集合的使用
目录- Java学习笔记
- 前言
- 一、数组——同类型数据的集合
- 二、ArrayList——封装数组的类
- 1. 定义集合
- 2. 泛型的使用
- 3. 扩容机制优化
- 4. ArrayList的扩容机制
- 总结
前言
Java中数据的保存离不开数组，但数组的长度是不可变的，如果初始长度过大，则会造成内存的浪费，降低性能，而数组初始长度过小时，又无法满足大量数据的存储。这时候就需要集合类（ArrayList）来进行数组扩容等操作，同时列表还可以包含批量删除、修改等更方便的内容。
一、数组——同类型数据的集合
Java中的数组的方式和C语言结构类似，都有维度和长度，但由于Java数组的声明方式与C语言略有不同，有两种格式： 类型 数组名[] 类型 [] 数组名 二者也是有区别的，例如：
代码语言：javascript复制int a[], b; 声明一个数组a和单个变量b
int[] a, b; 声明数组a和数组b同时声明数组时我们也可以对其进行初始化：
代码语言：javascript复制静态初始化：public String name[] = {
"candy","coffee"} ;
动态初始化：name = new String [2] ;数组在声明时只能在动静态中选择一种方式初始化。数组属于引用型变量，数组变量中存放着数组的首元素的地址，通过数组变量的名字加索引使用数组的元素，这点与C语言类似。
二、ArrayList——封装数组的类
1. 定义集合
Java的列表是一个类，这个类中包含数组，也包含各种处理数组的方法，同时还有必要的get方法以取出保存的数组。实际上Java自带集合：java.util.ArrayList类（父类是List）。为了我们能更好的理解基层原理，我们先自己来定义一个集合类。 在定义集合之前，我们来思考这么一个问题：对于不同的数据类型，如果我们想要使用集合，就需要创建不同的集合来存取。我们可以使用Object类来创建初始数组，这样各种类型的元素都可以存进数组里了： 同时，一个集合至少包含要添加元素、获取数组、获取长度等方法：
代码语言：javascript复制public class MyList {
// 原始数组
private Object[] arr = new Object[0];
private int size=0; // 记录数组中数据的长度
// 添加
public void add(Object element) {
// 扩容
// 创建更长的新数组
Object[] newArr = new Object[arr.length 1];
// 复制原数组中的数据：循环遍历
for(int i=0;i<arr.length;i ) {
newArr[i] = arr[i];
}
// 把新添加的数据保存到新数组中
newArr[arr.length] = element;
// 更新数组对象
arr = newArr;
//记录长度
size ;
}
// 获取数组
public Object[] get(){
return arr;
}
// 获取长度
public int size() {
return size;
}
}2. 泛型的使用
更多时候，我们需要一个数组里的元素都是同一个子类型的，比如String，或者是我们定义的其他类。 解决方法：泛型，其符号是“<>”。我们可以在类名后加上< E >或者< T >等，其中的字母相当于将类型参数化，就是将类型作为参数传入到方法，这样我们创建List时可以通过泛型限制传入的元素，当出现不符合预期的元素时编译器便会报错：
代码语言：javascript复制public class MyList<E> {
/*注意本行*/
private Object[] arr = new Object[0];
private int size=0;
public void add(E element) {
/*注意本行*/
Object[] newArr = new Object[arr.length 1];
for(int i=0;i<arr.length;i ) {
newArr[i] = arr[i];
}
newArr[arr.length] = element;
arr = newArr;
size ;
}
// 获取数组
public E get(){
/*注意本行*/
return (E)arr; /*注意本行*/
}
// 获取长度
public int size() {
return size;
}
}对于泛型使用的地方博主都进行了标注，这样我们就写好了一个相对好用且安全的类。 同时，使用了泛型的类在创建对象时的格式也有改变：
代码语言：javascript复制 public static void main(String[] args) {
MyList<String> list1 = new MyList<String>();
}同时等号后的””的的内容可以省略（自动转型），因此也可以写成：
代码语言：javascript复制 MyList<String> list1 = new MyList<>();值得注意的是，泛型不能指代八种基本类型类，只能替代“引用类型”。每个基本数据类型设计了一个对应的类进行代表，这样八个和基本数据类型对应的类统称为包装类，包装类均位于java.lang包，包装类和基本数据类型的对应关系如下表所示：
基本类型 | 包装类 | 基本类型 | 包装类 |
|---|---|---|---|
byte | Byte | int | Integer |
boolean | Boolean | long | Long |
short | Short | float | Float |
char | Character | double | Double |
自动装箱与自动拆箱机制:装箱就是自动将基本数据类型转换为包装器类型，拆箱就是自动将包装器类型转换为基本数据类型。例如：
代码语言：javascript复制 public static void main(String[] args) {
MyList<Integer> list = new MyList<Integer>();
int a = 10;
list.add(a);
System.out.println("arr[0] = " list.arr[0]);
注：本行list.arr正常情况并不合法
因为arr具有private修饰符
但是main函数在List类中运行恰巧能够调用
}arr[0] = 10
自动拆装箱使得int属性的变量可以被添加进Integer数组中。 我们还可以为MyList添加更多人性化的功能：删除元素，排序、查阅、修改等等。
3. 扩容机制优化
我们之前的MyList类中使用的扩容方法是最“朴实”的：
代码语言：javascript复制public void add(E element) {
Object[] newArr = new Object[arr.length 1];
for(int i=0;i<arr.length;i ) {
newArr[i] = arr[i];
}
newArr[arr.length] = element;
arr = newArr;
size ;
}每次添加元素时只扩容一个位置。由于每次扩容时都需要重新拷贝原数组中的元素，因此在添加元素数量非常巨大时，需要重复拷贝的元素数量也会越来越大，从而导致效率很低
代码语言：javascript复制public static void main(String[] args) {
MyList<Integer> list1 = new MyList<>();
ArrayList<Integer> list2 = new ArrayList<>();
/*获取系统时间*/
long time0 = System.currentTimeMillis();
for(int i=0;i<10000;i ) {
list1.add(i 1);
}
long time1 = System.currentTimeMillis();
for(int i=0;i<10000;i ) {
list2.add(i 1);
}
long time2 = System.currentTimeMillis();
System.out.println("ArrayList耗时间：" (time2-time1) "nShapeList耗时间：" (time1-time0));
}ArrayList耗时间：2 MyList耗时间：253
很明显，如果保持低速的线性扩容，效率不高，不难想到根据当前数组的长度，按比例指数型扩容：
代码语言：javascript复制public void add(E element) {
Object[] newArr = new Object[arr.length*3/2 1];
for(int i=0;i<arr.length;i ) {
newArr[i] = arr[i];
}
newArr[arr.length] = element;
arr = newArr;
size ;
}我们用改进的扩容算法和ArrayList的扩容作对比： 1w数据量已经看不出差距了，我们增加数据量到10w：
ArrayList耗时间：5 MyList耗时间：12
数据量增加到100w时，耗时已经实现了反超：
ArrayList耗时间：73 MyList耗时间：51
但在数据量达到1亿时，结果又是：
MyList耗时间：5504 ArrayList耗时间：2930
不难发现，列表扩容有点像计数“进制”，由于e进制是最高效的，于是我让扩容算法里每次扩大倍数变为e，同时由于数组有最大长度限制（2^31-1）我们需要判断扩容后的大小是否合法：
MyList耗时间：3899 ArrayList耗时间：3503
起初我认为这是由于创建对象也需要时间，大量创建空对象而不赋值，即占用内存又白白耗时。于是我调取了两者扩容时的内存占用，事实表明ArrayList的内存占用更大。
4. ArrayList的扩容机制
ArrayList中add方法的代码每次扩容的操作使用了grow方法：
代码语言：javascript复制 private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s 1;
}我们继续查看grow的代码
代码语言：javascript复制 private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}其中又调用了ArraysSupport.newLength：
代码语言：javascript复制public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// assert oldLength >= 0
// assert minGrowth > 0
int newLength = Math.max(minGrowth, prefGrowth) oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
return hugeLength(oldLength, minGrowth);
}
private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength minGrowth;
if (minLength < 0) {
// overflow
throw new OutOfMemoryError("Required array length too large");
}
if (minLength <= MAX_ARRAY_LENGTH) {
return MAX_ARRAY_LENGTH;
}
return Integer.MAX_VALUE;
}Capacity >> 1一行代表将原数组的长度size右移一位，最后在newLength方法中判断最终长度是否合法，再加到原size上。 实际上，先将旧容量右移1位，再加上旧容量就得到了新容量，正数右移1位相当于除以2，在该基础上加旧容量，则等价于新容量 = 旧容量 * 1.5，最后调用Arrays.copyOf()方法进行拷贝，并将elementData指向新数组，而旧数组因为没有引用指向它，很快就会被垃圾收集器回收掉。
我才发现效率差距的问题所在：对于存储器而言，数据都是通过二进制0和1保存，移位对于机器而言是经过底层优化的操作，乘除法也是通过多次移位来实现的，移位效率自然就比普通的乘除法计算高得多。
总结
不能轻视底层架构的学习
在我们一次次使用那些封装好的方法时，我们需要深入了解这些方法的简洁性和必要性，虽然都知道这些封装好的方法使用起来效率高却不知所以然，写的代码自然效率不会很高。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/172291.html原文链接：https://javaforall.cn
