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

Java 数组和List的使用「建议收藏」Java中数据的保存离不开数组,但数组的长度是不可变的。这时候就需要列表类(List)来进行数组扩容等操作,同时列表还可以包含批量删除、修改等更方便的内容。同时ArrayList作为使用相当频繁的List类,它的扩容算法效率很高,本文通过其源代码来分析其扩容高效的原因。

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

(0)


相关推荐

  • 测试知识整理「建议收藏」

    测试知识整理「建议收藏」测试流程:需求分析–>测试设计(测试计划,测试用例)–>执行测试–>提交BUG–>测试总结测试过程:单元测试、集成测试、系统测试、验收测试单元测试属于白盒测试

  • Flex实现QQ网页提取天气信息

    Flex实现QQ网页提取天气信息

  • Mysql 添加字段或者创建表SQL语句「建议收藏」

    Mysql 添加字段或者创建表SQL语句「建议收藏」最近要向测试和运维发SQL脚本,习惯了用工具,忘记了原始操作手法

    2022年10月10日
  • 了解图形数据库_图形数据库neo4j

    了解图形数据库_图形数据库neo4j企业架构师应该知道什么您在Google上获得的图表数据库的描述主要是学术性的。我看到很多关于图形数据库的描述,它们讨论了Königsberg的七座桥梁或互联网的发明者Berners-Lee。有理论和愿景很好,但对我来说,我仍然认为引导相关性很重要。为什么图形数据库对您很重要?想象一下存储在当地连锁餐厅的数据。如果您要跟踪,则将客户信息存储在一个数据库表中,将您提供的项目存储在另一个数据…

    2022年10月29日
  • vue中如何关闭eslint「建议收藏」

    vue中如何关闭eslint「建议收藏」1.在目录中新建vue.config.js2.在新建文件中输入module.exports={lintOnSave:false}就可以关闭啦~

  • 第一章 语音信号处理概述

    第一章 语音信号处理概述一、语音交互语音交互(VUI:VoiceUserInterface)是指人与人或者人与设备通过自然语音进行信息传递的过程。语音交互的优势输入效率高:相对于键盘输入,语音输入的速度是传统输入方式的3倍以上(有权威统计分析得到的数据)。语音检索效率高;可跨空间,也称为远程语音交互,至少一米以上;指令可组合,比如:看一部周星驰的电影,评分8分以上。 解放双手和双眼,更安全:如车载系统的语音点播和语音导航场景(不可能一般用手开车,一边用手点播音乐);比如医疗场景,医生可以一边动手术,一边口语记录病.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号