Java学习

Collection接口（无序、可重复），子接口List接口（有序（引入索引号，可插入修改顺序）、可重复），子接口Set接口（无序、不可重复）

线性表：数组、链表

Iterator 和 Iterable 接口

Collection 接口作为集合框架的顶级接口之一，继承于 Iterable 接口

public interface Collection extends Iterable

Iterable 接口

Iterable 接口用于引入可遍历的功能，要求接口的具体实现类必须提供 Iterator 的实现

Iterator 接口

Iterator 迭代器，走访器，可以理解为集合中元素的指针，用于实现集合中所有元素的遍历访问

public interface Iterator { 
    boolean hasNext(); //用于判断容器内是否还有可供访问的元素 
    E next();//返回迭代器刚越过的元素的引用，返回是 Object，需要强制转换或者使用泛型 
    default void remove() { //迭代器提供的删除元素的方法 
        throw new UnsupportedOperationException("remove"); 
    }
    default void forEachRemaining(Consumer < ? super E > action) { //获取剩余的元素，针对每个元素应用 action 函数 
        Objects.requireNonNull(action); 
        while (hasNext()) 
            action.accept(next());
    } 
}

编程使用

Collection cc = new ArrayList();
		for (int i = 0; i < 5; i++) {
			cc.add(cc);
		}
		Iterator it = cc.iterator();
		while (it.hasNext()) {
			Object tmp = it.next();
			System.out.println(tmp);
		}

对于大多数实现了Iterable接口的集合，可以多次调用forEach进行数据元素的遍历操作

Iterator和Iterable接口Collection接口作为集合框架的顶级接口之一，继承于Iterable接口public interface Collection extends IterableIterable接口Iterable接口用于引入可遍历的功能，具体的实现类必须提供Iterator的实现

一般不使用匿名内部类，代码编写太繁琐。一般建议使用lambda表达式

cc.forEach((obj)->{System.out.println(obj); });
cc.forEach(System.out::println);

forEachRemaining

Iterator接口的默认实现中提供了forEachRemaing方法，用于获取对应集合的迭代器Iterator访问的每个元素

Iterator it=list.iterator(); //获取迭代器对象

it.forEachRemaining((obj)->{System.out.pritln(obj); })

安全失败和快速失败

在多线程操作同时遍历集合时可以出现两种失败的情况—线程安全

安全失败是基于对底层集合进行拷贝，从而隔离修改和遍历访问，遍历不会受到修改的影响，是 juc 包中提供的实现类，不会报出异常

java.util 包中提供的集合类都是快速失败 fail-fast，当遍历的同时其它线程修改了集合结构，则抛出异常 ConcurrentModificationException。

快速失败

Collection cc = new ArrayList();
for (int i = 0; i < 20; i++) {
    cc.add(i);
}
new Thread(()->{
    Iterator it = cc.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    	try {
	        Thread.sleep(100);
    	} catch (InterruptedException e) {
        	e.printStackTrace();
        }
	}
}).start();
try {
    Thread.sleep(110);
} catch (InterruptedException e) { 
    e.printStackTrace();
}
cc.add(999);

安全失败

Collection cc = new CopyOnWriteArrayList();
for (int i = 0; i < 20; i++) {
    cc.add(i);
}
new Thread(()->{
    Iterator it = cc.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    	try {
	        Thread.sleep(100);
    	} catch (InterruptedException e) {
        	e.printStackTrace();
        }
	}
}).start();
try {
    Thread.sleep(110);
} catch (InterruptedException e) { 
    e.printStackTrace();
}
cc.add(999);

实现类

ArrayList底层数据结构就是数组，随机查询速度快、增删慢，线程不安全，效率高，允许存放重复元素

linkedList底层数据结构是双向链表，查询慢、增删快，线程不安全，效率高，允许存放重复元素

Vector底层数据结构是数组，随机查询速度快、增删慢，线程安全，效率低，允许存放重复数组

ArrayList实现类

ArrayList实现了List接口的可扩容的数组【System.arrayCopy】，它的内部不是基于数组实现的，相较于Java中的数组，容量能动态增长

继承于AbstractList抽象类，实现了List接口

RandomAccess接口，提供了随机访问支持。遍历元素的方法有两种，为快速随机访问和通过迭代器Iterator访问

Clonable接口，可以被克隆clone()

Serializable接口，支持序列化

ArrayList不是线程安全的，所以在无需考虑线程安全时使用，在需要考虑线程安全的多线程环境下可以考虑使用Vector或者juc中的CopyOnWriteArrayList

常量定义

private static final int DEFAUIT_CAPACITY = 10；默认数组元素的初始化容积

private static final Object[] EMPTY_ELEMENTDATA = {}; 没有元素的空对象数组，没有存储任何元素，数组长度为 0

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 构建 ArrayList 时默认使用的空数组

属性

transient Object[] elementData；就是用于存放元素的数组

private int size; 真实存放的元素个数

构造器 List list = new ArrayList();

默认构造器ArrayList(); 实际上并没有直接开辟空间，而是使用常量空数组

public ArrayList(){
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

带有初始化容积设置的构造器 new ArrayList(2000);

public ArrayList(int initialCapacity){        
    if (initialCapacity > 0) {   
        this.elementData =new Object[initialCapacity];//构建数组      
    }else if (initialCapacity == 0) {   							this.elementData =EMPTY_ELEMENTDATA;       
    }else {           
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);  
    }  
}

以另外一个集合Collection为参数构建对象

public ArrayList(Collection<?extends E>c) {
    elementData =c.toArray();  //将collection转换为数组，并赋值给elementData 属性       
    if ((size =elementData.length) != 0) {  //获取元素个数并赋值给size属性            // c.toArray might (incorrectly) not return Object[] (see 6260652)            
        if (elementData.getClass() != Object[].class)  //如果是对象数组则执行数组的拷贝       
            elementData = Arrays.copyOf(elementData,size,Object[].class); 
    }else {       
        this.elementData =EMPTY_ELEMENTDATA;      
    }   
}

概述

ArrayList实际上是通过数组保存数据，当构建ArrayList时，如果使用默认构造器，默认容积是10，但是采用延迟构建当ArrayList容积不足以存放元素时，会自动进行增容处理。新容积 = 原始容积 * 3 / 2 + 1ArrayList克隆函数是将全部元素克隆到一个数组中。elementData前面有transient修饰ArrayList实现序列化时，先写出容积值，再依次写出每个元素 add方法解析

public void add(int index,E element)

ArrayList在添加元素时，首先进行index范围检查，防止传入参数小于0或者超过数组的size大小，再和默认分配的大小值进行比对，如果大于默认大小则需要进行扩容处理。扩容时首先将创建一个大小为原始数组1.5倍的新数组，新数组大小不能超过Integer的最大值，检查完毕后进行数组元素的拷贝

public boolean add(E e) {
		ensureCapacityInternal(size + 1);
		elementData[size++] = e;
	}

首先进行容积检查和修改次数的统计，然后储存元素，并对 size+1

public void add(int index, E element){
	rangeCheckForAdd(index);
	
    ensureCapacityInternal(size +1);// Increments modCount!!
    System.arraycopy(elementData, index, elementData,index+1,
size - index);
    elementData[ index ] =element;
    size++;
}

rangeCheckForAdd 进行 index 的合法性检查，要求 index 必须是[0,size]之间，否则运行时异常

private void rangeCheckForAdd(int index){
    if(index > size || index < 0){
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

ensureCapacityInternal 用于保证容积正确

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity( calculateCapacity( elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
	// overflow- conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

如果所需要的最小容积大于数组的长度时调用 grow 方法进行扩容处理

private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity <0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE >0)
		newCapacity = hugeCapacity(minCapacity);
	// minCapacity is usually close to size, so this is a win:
	elementData = Arrays.copyOf(elementData, newCapacity);
}

int len=10;

len=len>>1; //5 相当于 len/2 使用位运算比直接的除法计算效率高

涉及一个思路–尽量减少扩容次数：如果需要 11 个容积值，不是新建数组为 11，因为这样后续的数据添加，例如添加第 12 个数据

还需要进行扩容，若以一次扩容比例为新增 50%容积，也就是新容积为 15，后续 5 个数据的添加则不需要进行扩容

这里涉及的常量值为 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
	if (minCapacity <0) // overflow
		throw new outofMemoryError();
	return (minCapacity > MAX_ ARRAY_ SIZE) ?
		Integer .MAX_ VALUE :
		MAX_ ARRAY_ SIZE;
}

minCapacity 所需要的最小容积小于 0，一定是超出 int 范围，此时抛出 Error， hugeCapacity 用于实现最大容积值为 Integer.max_value

Arrays 工具类是用于封装一组相关数组的操作。

public static  T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
public static  T[] copyof(U[] original, int newLength, Class newType) {
    @suppres sWarnings ("unchecked")
        T[] copy =((object )newType=(Object )0bject[].class)
        ? (T[]) new object [newLength]
		: (T[]) Array.newInstance( newType.getComponentType(), newLength);
    System. arraycopy(original,0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

Arrays.copyOf(elementData, newCapacity)可以创建一个指定长度的新数组，并且将原始数组中的内容拷贝到新数组，并返回新数组

System.arraycopy(elementData, index, elementData, index + 1,size - index);从 index 位置开始到整个数组中的有效元素全部向后拷贝移动一个位置

elementData[index] = element; 覆盖原始 index 位置上的数据，从而实现将输入插入 index 的目的

remove 方法解析

E remove(int index)

remove 方法首先进行 index 的范围检查，然后用 elementData(index)获取指定数组位置 index 对应的元素，在使用 size-index-1 转换为 numMoved 移动元素个数，接着使用 System.arrycopy 进行自我复制，将最后一个位置的元素赋值为 null

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IrpEDZGq-1646556359078)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216203934481.png)]

要求 index 必须在[0,size-1]的范围内

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1sgQ65ps-1646556359079)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204014072.png)]

modCount++; 统计修改次数，用于实现遍历同时修改数据的发现

E oldValue = elementData(index); 从数组中获取 index 位置上的元素

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rCU62RQw-1646556359079)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204035372.png)]

int numMoved = size - index - 1; 获取到移动元素个数

if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,numMoved);将原数组elementData 中的数据从 index+1 位置开始拷贝到目标数组 elemenentData 的 index 位置上，总共拷贝numMoved 个

elementData[–size] = null; 将最后一个位置上的元素值赋 null 值，同时 size-1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QHBmZQ2G-1646556359080)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204149342.png)]

remove(Object obj):boolean 方法中是先查找参数 obj 的位置，然后调用 fastRemove 通过索引号进行快速删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yvmdGiUI-1646556359080)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204206212.png)]

modCount++进行修改次数统计

使用 size-index-1 获取需要拷贝一定的元素个数

使用 System.arraycopy 进行拷贝移动操作

数组的最后位置赋值为 null

其它方法解析

size() 获取集合中的元素个数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yPL3Gwwd-1646556359081)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204301305.png)]

isEmpty()判断集合中的元素个数为 0

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YzqLO0NP-1646556359081)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204319447.png)]

contains 判断是否包含指定的元素indexOf 用于在集合中查找指定元素的第一个索引序号值，如果查询不到则返回-1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ufcZz448-1646556359082)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204334046.png)]

lastIndexOf 用于在集合中从后向前查找第一个满足条件的元素下标

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VAe1dEIX-1646556359082)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204343023.png)]

快速失败

由于 ArrayList 不是线程安全的容器，所以多个线程操作过程中会出现线程安全问题。

fail-fast 产生的条件：

当多个线程对 Collection 集合进行操作时，如果某个线程通过 Iterator 遍历集合时，该集合的内容被其它线程所改变，则会抛出 ConcurrentModificationException 异常

实现原理：

modCount 修改次数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W2HuQ4Wc-1646556359083)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204444651.png)]

调用 Itr 中的遍历方法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XZTarbzo-1646556359083)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204501390.png)]

具体编程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-i8P1ckah-1646556359083)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204513248.png)]

读取数据 get 方法

根据指定的索引编号获取指定位置上的元素。首先检查 index 的合法性，要求[0,size-1]范围内，如果不合法则异常，如果合法则根据下标从数组中获取对应的数据

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jIZ0cBCy-1646556359083)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204547718.png)]

线程安全问题

ArrayList 并没有提供线程安全处理，如果在开发中需要线程安全，则可以考虑 2 种解决方案：

方案 1：利用工具类实现线程安全

Collection ccc=Collections.synchronizedCollection(collection);

List lll=Collections.synchronizedList(list);

在整个集合种引入一个锁，实现整个集合的线程安全

方案 2：利用 juc 包中的类替代 java.util 包中的类不使用 ArrayList，而改成 CopyOnWriteArrayList。CopyonWrite 将读写进行分离，读取数据时读真实存放的数据，如果修改操作时，首先拷贝原始数据，对备份进行修改，最后再使用备份替换原始数据

clone 操作

首先 clone 当前对象，然后将数组拷贝到新对象的数组属性上，将修改次数设置为 0

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xgl7r2H3-1646556359084)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204646730.png)]

序列化处理

写出对象时首先写出 size 表示当前集合中的元素个数，然后逐个写出集合存放的元素

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D5snVsae-1646556359084)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204706923.png)]

Vector 实现类

内部实现仍旧是采用数组的方式实现，但是大部分方法上都有 synchronized 同步约束，所以当前类是一个线程安全的类

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vy1BBAE0-1646556359085)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204759022.png)]

elementData 用于存放数据的数组

elementCount 存放的数据个数—size

capacityIncrement 数组扩容时的步长值

构造器

public Vector() { //无参构造器 
    this(10); //调用当前类的只有一个 int 类型参数的构造器，无参构造的初始化数组长度为 10 
}public Vector(int initialCapacity) { //参数就是初始化容积值，也就是默认的数组长度 
    this(initialCapacity, 0); //调用其它构造器 
}public Vector(int initialCapacity, int capacityIncrement) { //参数 1 是初始化容积值，参数 2 是扩容的步长值 
    super(); 
    if (initialCapacity < 0) //初始化容积值不能小于 0 
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; //初始化数组 
    this.capacityIncrement = capacityIncrement; 
}

add 方法解析

最大的区别点在于 synchronized 同步处理，默认扩容 100%

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R0G1FE6r-1646556359085)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216204954879.png)]

ensureCapacityHelper 方法在发现当前容积不足时会调用 grow 方法进行扩容处理

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nuZTqnRi-1646556359085)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216205030837.png)]

如果不设置 capacityIncrement 参数，则默认扩容为原始容积的 2 倍。

linkedList 实现类

linkedList 底层的数据结构是基于双向链表的结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3ryb0l0C-1646556359086)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216205113189.png)]

size 元素个数

first 和 last 是头节点和尾节点

Node 节点定义

item 就是具体存储的数据

next 用于指向下一个节点的引用

prev 用于指向前一个节点的引用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X9x0lFwn-1646556359086)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216205126032.png)]

构造器

因为底层采用的是链表结构，所以没有容器的概念，从理论上来说可以无限制添加元素；但是 int size 限制了其中最大的元素个数为 Integer.max_value

public linkedList(){
    
}
public linkedList(Collection c){
    this();
    addAll(c);
}

特性：

可以添加 null 值元素

允许元素重复

可以通过索引编号有序

非线程安全

add 方法的实现

新增元素时就是向链表的末尾追加元素

public boolean add(E e){
    linkLast(e);
    return true;
}

void linkLast(E e){
    final Node l = last;
    final Node newNode = new Node<>(l,e,null);
    last = newNode;
    if(l == null){
        first = newNode;
    }else{
        l.next = newNode;
    }
    size++;
    modCount++;
}

remove 方法解析

删除指定元素值则是从头指针开始遍历整个链表，查找指定值的 Node 节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mc9hw7Ub-1646556359087)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216205809592.png)]

具体的删除操作是通过 unlink 实现的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L2Fg9IxU-1646556359087)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216205900308.png)]

按照索引序号删除指定元素

public E remove (int index){
    checkElementIndex(index);
    return unlink(node(index));
}

checkElementIndex 用于判断 index 的合法性，要求取值必须[0,size-1],否则抛出异常

node 方法用于获取指定索引位置上的节点 Node 对象，size>>1 表示 size/2，根据 index 距离头部还是尾部近，从头部（indexsize/2)开始查找

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BPGPI2sN-1646556359088)(C:Users阿白AppDataRoamingTyporatypora-user-imagesimage-20220216210056883.png)]

获取指定位置的元素

public E get(int index){
	checkElementIndex(index);
	return node(index).item;
}

checkElementIndex 用于判断 index 的合法性，要求取值必须[0,size-1]，否则抛出异常

node 方法用于获取指定索引位置上的节点 Node 对象，size>>1 表示 size/2，根据 index 距离头部还是尾部近，从头部（indexsize/2)开始查找

实现类总结

	ArrayList	linkedList	Vector
实现方式	数组，按照索引编号访问速度快 O(1)，但是删除或者添加元素可能会导致元素的移动，速度慢 O(n)	双向链表，按照索引编号访问元素速度慢 O(n)，但是删除或者添加元素，速度快 O(1)	数组，按照索引编号访问速度快O(1)，但是删除或者添加元素可能会导致元素的移动，速度慢 O(n)
是否同步	不同步，线程不安全，但是并发性高，访问效率高	不同步，线程不安全，但是并发性高，访问效率高	同步，所以线程安全，但是并发性低，访问效率低
如何选择	经常需要快速访问，较少在中间增加删除元素时使用；如果多线程访问，则需要自行编程解决线程安全问题	经常需要在内部频繁增删元素，但是很少需要通过索引编号进行访问时使用。如果多线程访问，则需要自行编程解决线程安全问题	一般不使用，如果在多线程并发访问并要求线程安全时可以考虑使用

--------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 实现方式 | 数组，按照索引编号访问速度快 O(1)，但是删除或者添加元素可能会导致元素的移动，速度慢 O(n) | 双向链表，按照索引编号访问元素速度慢 O(n)，但是删除或者添加元素，速度快 O(1) | 数组，按照索引编号访问速度快O(1)，但是删除或者添加元素可能会导致元素的移动，速度慢 O(n) |
| 是否同步 | 不同步，线程不安全，但是并发性高，访问效率高 | 不同步，线程不安全，但是并发性高，访问效率高 | 同步，所以线程安全，但是并发性低，访问效率低 |
| 如何选择 | 经常需要快速访问，较少在中间增加删除元素时使用；如果多线程访问，则需要自行编程解决线程安全问题 | 经常需要在内部频繁增删元素，但是很少需要通过索引编号进行访问时使用。如果多线程访问，则需要自行编程解决线程安全问题 | 一般不使用，如果在多线程并发访问并要求线程安全时可以考虑使用 |

Java学习

Java相关栏目本月热门文章