大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
今天我们来谈谈数组、列表和扩容,以及自写List和Java自带类ArrayList的异同。
Java学习笔记
第一节 Java 类与对象以及继承
第二节 Java 对象的保存和传递
第三节 Java 数组和集合的使用
前言
Java中数据的保存离不开数组,但数组的长度是不可变的,如果初始长度过大,则会造成内存的浪费,降低性能,而数组初始长度过小时,又无法满足大量数据的存储。这时候就需要集合类(ArrayList)来进行数组扩容等操作,同时列表还可以包含批量删除、修改等更方便的内容。
一、数组——同类型数据的集合
Java中的数组的方式和C语言结构类似,都有维度和长度,但由于Java数组的声明方式与C语言略有不同,有两种格式:
类型 数组名[]
类型 [] 数组名
二者也是有区别的,例如:
int a[], b; 声明一个数组a和单个变量b
int[] a, b; 声明数组a和数组b
同时声明数组时我们也可以对其进行初始化:
静态初始化:public String name[] = {
"candy","coffee"} ;
动态初始化:name = new String [2] ;
数组在声明时只能在动静态中选择一种方式初始化。数组属于引用型变量,数组变量中存放着数组的首元素的地址,通过数组变量的名字加索引使用数组的元素,这点与C语言类似。
二、ArrayList——封装数组的类
1. 定义集合
Java的列表是一个类,这个类中包含数组,也包含各种处理数组的方法,同时还有必要的get方法以取出保存的数组。实际上Java自带集合:java.util.ArrayList类(父类是List)。为了我们能更好的理解基层原理,我们先自己来定义一个集合类。
在定义集合之前,我们来思考这么一个问题:对于不同的数据类型,如果我们想要使用集合,就需要创建不同的集合来存取。我们可以使用Object类来创建初始数组,这样各种类型的元素都可以存进数组里了:
同时,一个集合至少包含要添加元素、获取数组、获取长度等方法:
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时可以通过泛型限制传入的元素,当出现不符合预期的元素时编译器便会报错:
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;
}
}
对于泛型使用的地方博主都进行了标注,这样我们就写好了一个相对好用且安全的类。
同时,使用了泛型的类在创建对象时的格式也有改变:
public static void main(String[] args) {
MyList<String> list1 = new MyList<String>();
}
同时等号后的””的的内容可以省略(自动转型),因此也可以写成:
MyList<String> list1 = new MyList<>();
值得注意的是,泛型不能指代八种基本类型类,只能替代“引用类型”。每个基本数据类型设计了一个对应的类进行代表,这样八个和基本数据类型对应的类统称为包装类,包装类均位于java.lang包,包装类和基本数据类型的对应关系如下表所示:
基本类型 | 包装类 | 基本类型 | 包装类 |
---|---|---|---|
byte | Byte | int | Integer |
boolean | Boolean | long | Long |
short | Short | float | Float |
char | Character | double | Double |
自动装箱与自动拆箱机制:装箱就是自动将基本数据类型转换为包装器类型,拆箱就是自动将包装器类型转换为基本数据类型。例如:
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类中使用的扩容方法是最“朴实”的:
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 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
很明显,如果保持低速的线性扩容,效率不高,不难想到根据当前数组的长度,按比例指数型扩容:
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方法:
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
我们继续查看grow的代码
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:
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保存,移位对于机器而言是经过底层优化的操作,乘除法也是通过多次移位来实现的,移位效率自然就比普通的乘除法计算高得多。
总结
不能轻视底层架构的学习
在我们一次次使用那些封装好的方法时,我们需要深入了解这些方法的简洁性和必要性,虽然都知道这些封装好的方法使用起来效率高却不知所以然,写的代码自然效率不会很高。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172291.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...