大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...

Java 数组和List的使用「建议收藏」

Java学习笔记

目录

前言

一、数组——同类型数据的集合

二、ArrayList——封装数组的类

1. 定义集合

2. 泛型的使用

3. 扩容机制优化

4. ArrayList的扩容机制

总结

发表回复

Java 数组和List的使用「建议收藏」

Java学习笔记

目录

前言

一、数组——同类型数据的集合

二、ArrayList——封装数组的类

1. 定义集合

2. 泛型的使用

3. 扩容机制优化

4. ArrayList的扩容机制

总结

相关推荐

pycharm远程运行_pycharm打开远程项目

java冒泡排序概练_Java的冒泡排序[通俗易懂]

Pycharm 安装插件[通俗易懂]

逻辑回归

swoole是如何实现任务定时自动化调度的？

python安装教程[通俗易懂]

发表回复