集合源码1
一、List接口分析
1、list接口的特点
①List集合的所有元素是由一种线性方式进行存储的。
②它是一个元素存储有序的集合。即元素的存入顺序和取出顺序有保证。
③他是一个带有索引的集合，通过索引就可以精确的操作集合中的元素
④集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素
1.1List接口的主要实现类
①ArrayList：动态数组
②Vector：动态数组
③LinkedList：双向列表
④Stack:栈
2、ArrayList与Vector的区别
他们底层的物理结构都是数组，我们称为动态数组
①ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。
②动态数组的扩容机制不同，ArrayList默认扩容为原来的1.5倍，Vector默认扩容增加为原来的2倍
③数组的初始化容量，如果在构建ArrayList与Vector的集合对象，没有显式指定初始化容量
●Vector初始化默认为10，ArrayList在jdk6.0及之前的版本也是10
●JDK8.0之后的版本ArrayList初始化长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。
ArrayList和LinkedList的区别总结如下：
●ArrayList底层使用了动态数组实现，实质上是一个动态数组
●LinkedList底层使用了双向列表实现，可当作堆栈、队列、双端队列使用
●ArrayList在随机存取方面的效率高于LinkedList
●LinkedList在节点的增删方面效率高于ArrayList
●ArrayList必须预留一定的空间，当空间不足时，会进行扩容操作
●LinkedList的开销是必须存储节点的信息以及节点的指针信息
ArrayList的实现原理是动态数组，它是线程不安全的，允许其中元素为null。ArrayList实现了 List, RandomAccess, Cloneable, java.io.Serializable接口，如下所示：
其中RandomAccess代表了其拥有随机快速访问的能力，ArrayList可以以O(1)的时间复杂度去根据下标访问元素。
3、常用API
/** ①AbstractList<E>是一个抽象类，它提供了List接口的骨架实现，以最小化实现此接口所需的工作。* 继承AbstractList使得ArrList无需从头开始实现list接口中中的所有方法，只需要关注那些与动态数组特性紧密相关的方法。* ②List<E>接口，继承自Collection<E>接口，有序，可重复* ③RandomAccess是一个标记接口，不包含任何方法。它用来声明实现该接口的列表类支持快速随机访问。ArrayList* 基于动态数组实现，因此可以高效的通过使用索引访问元素（时间复杂度为O（1））.实现RandomAccess可以作为一种提示，* 告诉算法或集合操作可以用更高效的方式来遍历或操作这个列表* ④Cloneable是一个标记接口，它本身不包含任何方法。他的存在主要是为了在运行时由Object类的clone方法检查* 对象是否可以被克隆。如果一个类没有实现Cloneable接口，并且尝试调用其对象的clone（）方法，那么会抛出一个* CloneNotSupportedException异常* clone()方法。Object类提供的，用于创建并返回调用该方法对象的一个副本。只有实现了Cloneable接口的对象* 才能被克隆。*ArrayList中的clone（）方法* ArrayList实现了Cloneable接口，并覆盖了Object类的clone()方法以提供自己的实现。当你调用ArrayList对* 象的clone（）方法是，他会创建一个新的ArrayList实例，这个新实例包含原始列表中所有元素的浅拷贝。* 浅拷贝：在 ArrayList 的上下文中，浅拷贝意味着新列表中的元素是原始列表中元素的引用，而不是元素本身的副本。* 修改了新列表中某个元素的状态，那么原始列表中对应的元素也会受到影响，因为它们实际上指向内存中的同一个对象。* 深拷贝：不仅复制对象本身，还复制对象中的引用类型字段所指向的对象* ⑤Serializable 接口也是一个标记接口，用于启用其实现类的序列化机制。序列化是将对象的状态信息转换为可以* 保存或传输的形式的过程。ArrayList 实现 Serializable 接口，意味着其实例可以被序列化为字节流，进而可* 以保存到文件、数据库或通过网络发送到另一个运行环境中的另一个 Java 虚拟机。这对于分布式应用或需要将对象* 状态持久化到存储介质的场景非常有用。** @param <E>*/
public class ArrayList1<E>extends AbstractList<E>implements List<E>, RandomAccess,Cloneable, java.io.Serializable {private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/** transient关键字用于声明一个字段不应该是对象序列化的的一部分，当你将一个对象的状态保存到文件，数据库* 或通网络发送时，这个过程称为序列化（serialization）。这个过程对象被转换成一系列字节，序列化的目的是将对* 象的状态信息转换成可以存储或传输的格式，以便稍后可以通过反序列化恢复对象的状态* transient在private transient Object[] elementData;中的作用是避免序列化过程中不必要的数据膨胀* 特别是处理动态数组或集合时，这些数据结构可能包含大量未使用的空间，通过使用transient，开发者可以精确控制那* 些数据应该被序列化，从而优化性能和减少存储需求**/
//属性
private transient Object[] elementData;//存储底层的数组元素private int size; //记录数组中存储的元素的个数//构造器private ArrayList1(){this(10); //指定初始容量为10}@Overridepublic int size() {return 0;}public ArrayList1(int initialCapacity){/** 子类的构造方法必须首先调用父类的构造方法，这是因为子类在创建时必须首先调用父类的构造方法。这是* 因为子类在创建时，首先需要初始化从父类继承的部分*/super();//检查初始容量的合法性if (initialCapacity<0)throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);//数组初始化长度为initialCapacity的数组this.elementData=new Object[initialCapacity];}//add()相关方法public boolean add(E e){ensureCapacityInternal(size+1);//查看当前数组是否能够多存一个元素elementData[size++]=e;//将元素e添加到elementData数组中return true;}
//检查当前数组的容量elementDate.length是否小于minCapacityprivate void ensureCapacityInternal(int minCapacity) {/** modCount用于支持快速失败机制，快速失败机制是Java集合中的一种迭代器行为，当迭代器创建之后，如果在* 迭代过程中检测的集合的结构被修改（非通过迭代器自身的remove或add方法），则抛出* ConcurrentModificationException异常，这里的被修改指的是集合的大小发生变化，或者某些方式改变了* 集合的迭代顺序，使得迭代器无法按照预期的方式遍历集合* 集合的结构发生变化是指集合的元素和顺序变化*/modCount++; //集合被修改的次数//如果if条件满足，则进行扩容if (minCapacity-elementData.length>0)/** minCapacity在ArrayList上下文中表示最小容量，即ArrayList底层数组将要添加元素后所需达到的最小容量*如果小于，说明当前数组容量不足，需要进行扩容，此时会调用grow(int minCapacity)* 如果不小于，则直接进行添加操作*/grow(minCapacity);}
/*** 扩容动态数组*/private void grow(int minCapacity) {int oldCapacity= elementData.length;/** 新数组容量是旧数组容量的1.5；* oldCapacity>>1:这是一个位运算操作，具体是右移一位，在二进制表示中，右移一位相当于/2* 这里使用位运算符>>1是因为她等同于oldCapacity/2,但位运算通常更快*/int newCapacity=oldCapacity+(oldCapacity>>1);//判断就数组的1.5倍是否超过最大数组限制，// 如果超过了最大数组限制，会调用hugeCapacity(minCapacity)来计算一个新的合适的容量if (newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//复制一个新数组，// 使用Arrays.copyOf方法创建一个新的数组，将旧数组的内容复制到新数组中，// 并更新elementData引用指向新数组/** Arrays.copyOf(T[] original,int newLength)方法是用来创建一个新数组，他的内容是原始数组的* 一个副本，但是新数组的长度是由第二个参数指定，这个方法常用于在需要扩展或缩小数组大小时使用。** 这个新数组的引用被赋值给了elementDate变量。这样elementDate变量就指向了一个新的，* 长度不同的数组（如果newCapacity大于原始数组的长度，则新数组中剩余的位置将被初始化为* 该类型的默认值，对于对象数组，这些位置将是null）*/elementData= Arrays.copyOf(elementData,newCapacity);}/** 当所需的最小容量大于MAX_ARRAY_SIZE时，计算一个新的合适的容量* @param minCapacity* @return*/private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) //overflowthrow new OutOfMemoryError();/** MAX_ARRAY_SIZE是ArrayList内部定义的常量，它通常背设置为Integer.MAX_VALUE-8(或者类似的值，具体取决于* JVM的实现。)这个值是为了确保在创建新数组时，有足够的空间来存储数据*/return (minCapacity>MAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE; //这是为了防止创建过大的数组而导致内存溢}//方法：remove的相关方法public E remove(int index){rangeCheck(index);//判断index是否在有效范围内modCount++;//修改次数加1//取出index位置的元素，[index]位置的元素就是要被删除的元素E oldValue=elementData(index);/** 这行代码用于计算当从列表中删除一个元素，需要向后移动的元素数量。* 删除这个元素，索引index及之后的元素都需要向前移动一个位置来填补空缺* index+1到size-1--->size-1-index*/int numMoved=size-index-1;//确定要移动的次数//如果需要移动次数，就用System.arrayCopy移动元素if (numMoved>0)/**这行代码是把elementData数组中从索引index+1开始的numMoved个元素复制到该数组的*index索引开始的位置，这样做的结果是，原来位于index位置处的元素被覆盖（即被删除），*而他后面的所有的元素都向前移动了一个位置System.arraycopy方法的参数解释：●第一个参数：src（在这里是elementData）：源数组●第二个参数：srcPos(index+1)：源数组中的起始位置(包含)●第三个参数：dest(elementData)：目标数组，(在这种情况下目标数组和源数组是一致的)●第四个参数：destPos(index)目标数组的起始位置（包含）●第五个参数：length(numMoved):要复制的数组元素的数量**/System.arraycopy(elementData,index+1,elementData,index,numMoved);//将elementData[size-1]位置置空，让GC回收空间，元素个数减少elementData[--size]=null;return oldValue;}public void rangeCheck(int index) {if (index>=size)//throw new IndexOutOfBoundsException(outOfBoundsMsg(index));throw new IndexOutOfBoundsException("index"+index+",size"+size);}E elementData(int index){return (E)elementData[index];
}//方法：set()方法相关public E set (int index, E element){rangeCheck(index);//检验index是否合法//取出【index】位置的元素，【index】位置的元素就是要被替换的元素，用于最后返回被替换的元素E oldValue=elementData(index);//用element替换【index】处的元素elementData[index]=element;return oldValue;}//方法：get()相关方法public E get(int index){rangeCheck(index);//检验index是否合法return elementData(index);//返回index位置的元素}//方法：indexOf()public int indexOf(Object o){//分为o是否为空两种情况if (o==null){for (int i = 0; i < size; i++)if (elementData[i]==null)return i;}else{for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}//lastIndexOf()public int lastIndexOf(Object o){//分为o是否为空两种情况if (o==null){//从后往前找for (int i = size-1; i >=0 ; i--)if (elementData[i]==null)return i;}else{for (int i = size-1; i >=0 ; i--)if (o.equals(elementData[i]))return i;}return -1;}//contains方法public boolean contains(Object o){return indexOf(o)>=0;}//clear方法public void clear(){modCount++;for (int i = 0; i < size; i++) {elementData[i]=null;size=0;}}/*public int size(){return size;}*/public boolean isEmpty(){return size==0;}//toArray方法public Object[] toArray(){return Arrays.copyOf(elementData,size);}public <T> T[] toArray(T [] a){//如果传入数组a的大小小于集合的大小，则创建一个新的数组if (a.length<size)//使用Arrays.copyOf创建一个新的数组，其类型与a相同，大小为size//注意：这里需要强制类型转化(T[])，但由于类型信息在运行时丢失，所以可能会抛出ClassCastException//注意：使用@SuppressWarnings("unchecked")来抑制这个警告return (T[]) Arrays.copyOf(elementData, size, a.getClass());//如果传入的数组a的大小足够大，则直接使用它System.arraycopy(elementData, 0, a, 0, size);//如果传入的数组a的大小大于集合的大小，则将多余的元素设置为nullif (a.length > size)a[size] = null;//返回填充了集合元素的数组return a;}//迭代器Iteratorpublic Iterator<E> iterator(){return new Itr();}
//检查迭代器是否还有更多的元素可以遍历public class Itr implements Iterator<E>{//表示迭代器当前遍历到的位置//在迭代开始时，cursor通常被初始化为指向集合的第一个元素（在ArrayList集合中，他可能被初始化为0）//随着next的调用，cursor会递增以指向下一个元素
int cursor;
/*
lastRet用于记录上一次调用next（）方法时返回的元素的索引。它被初始化为-1，表示第一次调用
next（）之前，没有元素被返回*/
int lastRet=-1;
/*
expectedModCount字段迭代器创建集合的修改次数。这是快速失败机制的一部分，用于检测在迭代
过程中集合是否被并发修改*/
int expectedModCount=modCount;//用于判断集合是否修改过的标志@Overridepublic boolean hasNext() {// 它检查 cursor 是否不等于 size。如果不等，表示还有更多的元素可以遍历，因此方法返回// true；如果相等，表示没有更多的元素，因此方法返回 false。return cursor!=size;}
@SuppressWarnings("unchecked")@Overridepublic E next() {//检查集合是否被并发修改checkForComodification();int i=cursor;//检查cursor是否越界if (i>=size) //判断是否越界throw new NoSuchElementException();//获取集合的底层数组，并再次检查cursor是否越界Object []elementData=ArrayList1.this.elementData;if (i>=elementData.length)//再次判断是否越界，在我们这里的操作时throw new ConcurrentModificationException();//递增cursorcursor=i+1;//游标+1//更新lastRet为当前元素的索引，进行类型转换后并返回该元素return (E)elementData[lastRet=i];}//从集合中移除最后一个通过迭代器返回的元素
public void remove(){/*检查lastRet是否有效*/if (lastRet<0)throw new IllegalStateException();/*检查集合的并发修改用于检查迭代器自创建以来是否被修改过，如果迭代器被非迭代器方法修改过，则抛异常这是迭代器的一个常见特性，用于保证迭代过程中的集合一致性*/checkForComodification();try{/*移除元素*/ArrayList1.this.remove(lastRet);//删除元素 remove方法内会修改modCount，所以后面要更新Iterator里的标志词//要删除的游标cursor=lastRet;//不能重复删除 所以修改删除的标志位lastRet=-1;//更新 判断集合是否修改的标志expectedModCount=modCount;}catch (IndexOutOfBoundsException ex){throw new ConcurrentModificationException();}}
//用于检查迭代过程中集合是否被并发修改，如果有修改，则抛出异常private void checkForComodification() {if (modCount!=expectedModCount)throw new ConcurrentModificationException();}}}迭代器是一个内部类，包括Itr和ListItr
Iterator和ListIterator的区别如下：
①前者可以遍历list和set集合，后者只能用来遍历list集合
②前者只能前向遍历集合；后者可以前向和后向遍历集合
③后者实现了前者，增加了一些新的功能
ArrayList源码总结
①ArrayList内部基于动态数组实现，所以可以进行扩容操作，每一次扩容增量都是50%，
②基于数组实现，所以内部多个API都避免不了对数组的copy操作，比如set和remove操作，所以大桥欧治ArrayList插入和删除效率低下
③基于数组实现，并且实现了RandomAccess，所以可以随机访问，根据index来找元素的致，所以ArrayList获取元素的效率很高
④提供了多个迭代器，都是基于内部类实现的
⑤底层源码没有做同步处理，所以是线程不安全的，之前版本Vector原理基本一致，但是Vector在方法的实现上都会加上synchronized关键字
⑥modeCount会在适当的时候进行++操作，可以实现快速失败
什么是快速失败？
快速失败（fail-fast）是编程中的一个概念，特别是在处理集合（如Java中的List、Set等）时尤为重要。它指的是在程序运行过程中，当某个线程正在遍历集合（通过迭代器Iterator）时，如果集合的内容被其他线程所修改（如添加、删除元素），则遍历过程会立即感知到这种变化，并抛出ConcurrentModificationException异常，从而中断遍历。这种机制的主要目的是让程序能够尽早地报告潜在的问题，帮助开发人员快速定位并修复问题，保证系统的可靠性和稳定性。
快速失败的好处
快速定位问题：通过立即抛出异常，开发人员可以迅速知道集合在迭代过程中被修改了，从而更容易地定位问题所在。
保证系统可靠性：防止因为集合内容的不一致而导致后续操作出现错误，保证系统的稳定性和可靠性。
快速失败的缺点
快速失败机制虽然能够尽早地暴露问题并帮助开发人员快速定位修复，但也存在一些缺点，如可能导致程序中断、用户体验差、可能掩盖真正的问题、增加系统复杂性以及不适用于所有场景等。
Vector类简介
1、Vector类是单列集合List接口的一个实现类。与ArrayList类似，Vector也实现了一个可以动态修改的数组。两者最本质的区别在于-------Vector类是支持线程同步的，因此它线程安全，支持多线程，而ArrayList是线程不同步的，线程不安全。
2、Vector内部是以动态十足的形式来存储数据的。
3、Vector具有动态数组所具有的特性，通过索引支持随机访问，所以通过随机访问Vector中的元素效率非常高，但是执行插入删除时效率比较低。
4、Vector实现了AbstractList抽象类，List接口，所以其更具有了AbstractList和List的功能，前面我们知道AbstractList实现了
内部已经实现了获取Iterator和ListIterator的方法、所以Vector只需关心对数组操作的方法的实现、
5、Vector实现了RandomAccess接口、此接口只有声明、没有方法体、表示Vector支持随机访问。
6、Vector实现了Cloneable接口、此接口只有声明、没有方法体、表示Vector支持克隆。
7、Vector实现了Serializable接口、此接口只有声明、没有方法体、表示Vector支持序列化、即可以将Vector以流的形式通过ObjectOutputStream来写入到流中。
8、Vector是线程安全的。
Vector类属于Java.base模块，Java.util包下
线程同步是什么意思？
线程同步是指多个线程在访问共享资源时，按照一定的顺序或规则来执行，以避免数据竞争和冲突，确保数据的一致性和完整性。具体来说，当一个线程在对某个内存地址（通常是共享资源）进行操作时，其他线程不能同时对该内存地址进行操作，直到该线程完成操作并释放资源后，其他线程才能继续操作。线程同步的目的是为了避免数据混乱，解决与时间有关的错误，确保多个线程能够协调工作，达到一致性的状态。
为什么ArrayList线程不安全？
ArrayList线程不安全的原因主要有以下几点：
- 非同步机制：ArrayList没有实现任何同步机制，这意味着多个线程可以同时访问和修改ArrayList中的数据，而没有任何锁或其他同步机制来确保数据的一致性。
- 基于数组的实现：ArrayList底层是通过数组来实现的，而数组的长度是固定的。当进行增删操作时，需要改变数组的长度，这可能会导致多个线程同时操作同一个数组，从而引发线程安全问题。
- 数据不一致：如果多个线程同时对ArrayList进行写操作（如add、remove等），可能会导致数据不一致的情况。例如，一个线程正在修改一个元素，而另一个线程正在读取该元素，这时就会出现数据不一致的情况。
- 索引越界：如果多个线程同时进行添加或删除元素操作，就可能导致索引越界的情况。例如，一个线程正在删除ArrayList中最后一个元素，而另一个线程正在向ArrayList中添加元素，这时就可能导致索引越界。
Vector线程安全？
Vector是线程安全的，但需要注意的是，这种线程安全是相对的，并且有一定的局限性。Vector通过在其方法上添加synchronized关键字来实现线程安全，这意味着当一个线程在调用Vector的某个同步方法时，其他线程不能同时调用该同步方法。然而，这种同步机制只保证了Vector的单个方法是线程安全的，并不能保证多个线程在调用不同方法时的整体安全性。
此外，虽然Vector是线程安全的，但在高并发场景下，其性能可能会受到影响。因为synchronized关键字会导致线程在访问同步方法时进行阻塞和唤醒操作，这会增加线程切换的开销。因此，在需要高并发性能的场合，通常会选择使用其他并发集合，如ConcurrentHashMap、CopyOnWriteArrayList等。