盐边网站建设,常见的网络推广方式有哪些,哪些网站做ip向小说,wordpress电子商务主题 中文版ArrayList源码分析目标:一、 ArrayList的简介二、ArrayList原理分析2.1 ArrayList的数据结构源码分析2.2 ArrayList默认容量最大容量2.3 为什么ArrayList查询快#xff0c;增删慢#xff1f;2.4 ArrayList初始化容量1、创建ArrayList对象分析#xff1a;无参数2、创建A…
ArrayList源码分析目标:一、 ArrayList的简介二、ArrayList原理分析2.1 ArrayList的数据结构源码分析2.2 ArrayList默认容量最大容量2.3 为什么ArrayList查询快增删慢2.4 ArrayList初始化容量1、创建ArrayList对象分析无参数2、创建ArrayList对象分析带有初始化容量构造方法2.5 ArrayList扩容原理三、ArrayList线程安全问题及解决方案3.1 错误复现3.2 导致ArrayList线程不安全的源码分析3.3 解决方案四、ArrayList的Fail-Fast机制深入理解目标:
理解ArrayList的底层数据结构深入掌握ArrayList查询快增删慢的原因掌握ArrayList的扩容机制掌握ArrayList初始化容量过程掌握ArrayList出现线程安全问题原因及解决方案掌握ArrayList的Fail-Fast机制
一、 ArrayList的简介 ArrayList集合是Collection和List接口的实现类。底层的数据结构是数组。数据结构特点 : 增删慢查询快。线程不安全的集合 许多程序员开发的时候使用集合基本上无脑选取ArrayList不建议这种用法。 ArrayList的特点:
单列集合 : 对应与Map集合来说【双列集合】有序性 : 存入的元素和取出的元素是顺序是一样的元素可以重复 : 可以存入两个相同的元素含带索引的方法 : 数组与生俱来含有索引【下角标】
二、ArrayList原理分析
2.1 ArrayList的数据结构源码分析
//空的对象数组
private static final Object[] EMPTY_ELEMENTDATA {};
//默认容量空对象数组通过空的构造参数生成ArrayList对象实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};
//ArrayList对象的实际对象数组
transient Object[] elementData; // non-private to simplify nested class access
//1、为什么是Object类型呢利用面向对象的多态特性当前ArrayList的可以存储任意引用数据类型。
//2、ArrayList有一个问题不能存储基本数据类型就是数组的类型是Object类型2.2 ArrayList默认容量最大容量
//默认的初始化容量是10
private static final int DEFAULT_CAPACITY 10;
//最大容量 : 2^31 - 1 - 8 21 4748 3639【21亿】
private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;为什么最大容量要-8呢 目的是为了存储ArrayList集合的基本信息比如list集合的最大容量 2.3 为什么ArrayList查询快增删慢
ArrayList的底层数据结构就是一个Object数组一个可变的数组对于其的所有操作都是通过数组来实 现的。
数组是一种查询快、增删慢查询数据是通过索引定位查询任意数据耗时均相同。查询效率贼高删除数据时要将原始数据删除同时后面的每个数据迁移。删除效率就比较低新增数据在添加数组的位置加入数组同时在数组后面位置后移以为添加效率极低 2.4 ArrayList初始化容量
ArrayList底层是数组动态数组
底层是Object对象数组数组存储的数据类型是Object数组名字为elementData。 transient Object[] elementData; // non-private to simplify nested class access1、创建ArrayList对象分析无参数 创建ArrayList的之后ArrayList容量是多少呢回答10是错误的回答0是正确【限定条件在 JDK1.8中】 如何 初始化 动态数组的容量10个 构造方法
/*** Constructs an empty list with an initial capacity of ten. */
//空参构造时创建一个空数组
public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};在执行add()方法的时候初始化【懒加载】 判断当前数组的容量是否有存储空间如果没有初始化一个10的容量。
//向数组中添加一个元素
public boolean add(E e) {//确保有容量如果第一次添加会初始化一个容量为10的list //size当前集合元素的个数随着添加的元素递增ensureCapacityInternal(size 1); // Increments modCount!! //添加元素elementData[size] e; return true;
}
//ensureCapacityInternal确保有容量如果第一次添加会初始化一个容量为10的list
private void ensureCapacityInternal(int minCapacity) {//两个方法ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// calculateCapacity(elementData, minCapacity) 拿着当前ArrayList的数组与当前数组中的元素个数。计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity)
{//ArrayList的数组与默认的数组进行比较。 //{} {}if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {/true //DEFAULT_CAPACITY 10//minCapacity 1 //1和10比谁大 10return Math.max(DEFAULT_CAPACITY, minCapacity);//计算之后返回的初始化容量是10}return minCapacity;
}
// ensureExplicitCapacity() 确保不会超过数组的真实容量
private void ensureExplicitCapacity(int minCapacity) { //minCapacity 当前计算后容量 10modCount;//对当前数组操作计数器 // overflow-conscious code//最小的容量: 10 - 当前数组的容量{} 0if (minCapacity - elementData.length 0) grow(minCapacity);//做了扩容
}2、创建ArrayList对象分析带有初始化容量构造方法
//创建ArrayList集合并且设置固定的集合容量
public ArrayList(int initialCapacity) { //initialCapacity 手动设置的初始化容量if (initialCapacity 0) {//判断容量是否大于0如果大于0 //创建一个对象数组位指定容量大小并且交给ArrayList对象 this.elementData new Object[initialCapacity]; //如果设置的容量为0设置默认数组} else if (initialCapacity 0) {this.elementData EMPTY_ELEMENTDATA;//默认的元素数据数组{} } else {//如果不是0也不是大于0的数会抛出非法参数异常throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}
}注意 : 使用ArrayList的集合建议如果知道集合的大小最好提前设置。提示集合的使用效率
2.5 ArrayList扩容原理
add方法先要确保数组的容量足够防止数组已经填满还往里面添加数据造成数组越界
如果数组空间足够直接将数据添加到数组中如果数组空间不够了则进行扩容。扩容1.5倍扩容。扩容 : 原始数组copy新数组中同时向新数组后面加入数据
注意 : new的ArrayList的对象没有容量的在第一次添加的add会进行第一次扩容。0 - 10
//grow扩容数组
private void grow(int minCapacity) {//minCapacity 当前数组的最小容量存储了多少个元素 // overflow-conscious code//获取当前存储数据数组的长度int oldCapacity elementData.length;//新的容量 旧的容量 扩容的容量【旧容量/2 0.5旧容量】 //扩容1.5倍扩容int newCapacity oldCapacity (oldCapacity 1); //极端情况过滤 : 新的容量 - 旧的容量小于0【int值移除】 if (newCapacity - minCapacity 0)newCapacity minCapacity;//不扩容了 //新的容量比ArrayList的最大值还要大if (newCapacity - MAX_ARRAY_SIZE 0)//设置新的容量为ArrayList的最大值以ArrayList最大值为当前容量 newCapacity hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win: elementData Arrays.copyOf(elementData, newCapacity);
}总结:
扩容的规则并不是翻倍是原来容量的1.5倍ArrayList的数组最大值Integer.MAX_VALUE。不允许超过这个最大值新增元素时没有严格的数据值的检查。所有可用设置null
三、ArrayList线程安全问题及解决方案
3.1 错误复现
ArrayList 我们都知道底层是以数组方式实现的实现了可变大小的数组它允许所有元素包括null。 看下面一个例子开启多个线程操作List集合向ArrayList中增加元素同时去除元素 //全局线程共享集合ArrayListprotected static ArrayListObject arrayList new ArrayList();Testvoid arrayListTest() {//1.创建线程数组【500】Thread[] threads new Thread[500];//2.遍历数组向线程中添加500个线程对象for (int i 0; i threads.length; i) {threads[i] new MyThread();threads[i].start();//启动线程}//3.遍历线程等待线程执行完毕【等待所有线程执行完毕】for (int i 0; i threads.length; i) {try {threads[i].join();//等待线程执行完毕} catch (InterruptedException e) {e.printStackTrace();}}//线程执行内容 : 向集合中添加自己的线程名称//4.遍历list集合获取所有线程的名称for (Object threadName : arrayList) {System.out.println(threadName threadName);}}//线程执行内容是想集合中添加自己的线程名称class MyThread extends Thread {Overridepublic void run() {try {//线程休眠1000Thread.sleep(1000);//向集合中添加自己的线程名称【操作共享内容会出现线程安全问题】arrayList.add(Thread.currentThread().getName());} catch (InterruptedException e) {e.printStackTrace();}}}运行代码结果可知会出现以下几种情况:
①打印null②某些线程并未打印③数组角标越界异常 3.2 导致ArrayList线程不安全的源码分析
ArrayList成员变量
public class ArrayListE extends AbstractListEimplements ListE, RandomAccess, Cloneable, java.io.Serializable
{//ArrayList的Object的数组存所有元素。transient Object[] elementData; // non-private to simplify nested class
access//size变量保存当前数组中元素个数。 private int size;
//...
}ArrayList的Object的数组存储所有元素。size变量保存当前数组中元素个数。
出现线程不安全源码之一 : add()方法
public boolean add(E e) {//确保有容量如果第一次添加会初始化一个容量为10的list //size当前集合元素的个数随着添加的元素递增ensureCapacityInternal(size 1); // Increments modCount!! //添加元素elementData[size] e; return true;
}add添加元素实际做了两个大的步骤
判断elementData数组容量是否满足需求在elementData对应位置上设置值
线程不安全的隐患【1】导致③数组下标越界异常 线程不安全的隐患【2】导致①Null、②某些线程并未打印 致①Null、②某些线程并未打印深层次原因是因为多线程情况下出现了指令重排和不保证原子性问题。详见Volatile关键字 由此我们可以得出在多线程情况下操作ArrayList 并不是线性安全的。
3.3 解决方案
第一种方案使用Vector集合Vector集合是线程安全的
//线程安全问题解决方案1
protected static VectorObject vector new Vector();第二种方案使用Collections.synchronizedList。它会自动将我们的list方法进行改变最后返回给我们加锁了List
//线程安全问题解决方案2
//将集合改为同步集合
protected static ListObject synList Collections.synchronizedList(arrayList);第三种方案使用JUC中的CopyOnWriteArrayList类进行替换。
//线程安全问题解决方案3 JUC 【最佳选择】
protected static CopyOnWriteArrayListObject copyOnWriteArrayList new
CopyOnWriteArrayList();因为CopyOnWriteArrayList中的add操作使用了lock锁保证了原子性同时保证线程安全而且数组也使用了volatile关键字保证可见性和防止指令重排 四、ArrayList的Fail-Fast机制深入理解
什么是Fail-Fast机制 快速失败即Fail-Fast机制它是Java中一种错误检测机制 当多钱程对集合进行结构上的改变或者在迭代元素时直接调用自身方法改变集合结构而没有通知迭代器时有可能会触发Fail-Fast机制并抛出异常【ConcurrentModificationException】。注意是有可能 触发Fail-Fast而不是肯定
触发时机 : 在迭代过程中集合的结构发生改变而此时迭代器并不知情或者还没来得及反应便会 产生Fail-Fast事件。
再次强调迭代器的快速失败行为无法得到保证一般来说不可能对是否出现不同步并发修改或者 自身修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。
Java.util包中的所有集合类都是快速失败的而java.util.concurrent包中的集合类都是安全失败的快 速失败的迭代器抛出ConcurrentModificationException而安全失败的迭代器从不抛出这个异常。
ArrayList的Fast-Fail事件复现及解决方案 /*** 目标: 复现Fast_Fail机制* 1.产生条件 :* 当多线程操作同一个集合* 同时遍历这个集合该集合被修改* 2.解决方案 :使用并发编程包中的集合CopyOnWriteArrayList替换原有ArrayList集合。*///定义全局共享集合 :static ArrayListString list new ArrayList();//Fast_Fail机制CopyOnWriteArrayList// static CopyOnWriteArrayListString list new CopyOnWriteArrayList();Testvoid arrayListTest() {//创建线程1并且向集合添加元素打印集合中的内容Thread thread1 new Thread(() - {//并且向集合添加元素for (int i 0; i 6; i) {list.add( i);// 打印集合中的内容printAll();}});thread1.start();//启动线程1//创建线程2并且向集合添加元素打印集合中的内容Thread thread2 new Thread(() - {//并且向集合添加元素for (int i 10; i 16; i) {list.add( i);// 打印集合中的内容printAll();}});thread2.start();//启动线程2}/*** 使用迭代器打印集合*/public static void printAll() {//获取当前集合的迭代器IteratorString iterator list.iterator();//通过迭代器遍历集合while (iterator.hasNext()) {String value iterator.next();System.out.println(value ,);}}使用ArrayList在多线程情况下添加元素时出线ConcurrentModificationException 解决办法使用并发编程包中的集合CopyOnWriteArrayList替换原有ArrayList集合。
扩展连接 ArrayList集合底层原理 ArrayList集合特点为什么是增删慢、查询快
