探索 ArrayList 原理 - 第四节Arraylist 面试题
文章目录
- 探索 ArrayList 原理
- 5. 面试题
- 5.1、ArrayList 是如何扩容的；
- 5.1.1、java 位移运算符扩展
- 5.2、ArrayList 频繁扩容导致添加性能急剧下降，如何处理；
- 5.3、ArrayList 插入或删除元素一定比LinkedList慢么？
- 5.4、ArrayList 是线程安全的么？
- 5.5、如何复制某个ArrayList到另一个ArrayList 中去？
- 5.6、已知成员变量集合存储N多用户名称，在多线程的环境下，使用迭代器在读取集合数据的同时，如何保证还可以正常的写入数据到集合？
- 5.7、ArrayList 和 LinkList 区别
探索 ArrayList 原理
jdk1.8 API
黑马教学视频： java进阶教程丨全面深入解析ArrayList原理（源码分析+面试讲解）
- 接上文- 第三节ArrayList 常用方法源码分析
5. 面试题
5.1、ArrayList 是如何扩容的；
-
代码分析
//首先构造一个Arraylist ArrayList<String> arrayList = new ArrayList<>(); arrayList.add("aaa"); arrayList.add("bbb"); arrayList.add("ccc");- 无参构造
//初始化 执行构造方法 构造一个Arraylist 初始化为一个空数组， public ArrayList() { // Object[] elementData; //Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }- add 方法添加元素
public boolean add(E e) { ensureCapacityInternal(size + 1); // size 初始化为0 elementData[size++] = e; return true; } //ArraList初始化容量判断 private void ensureCapacityInternal(int minCapacity) { // minCapacity 初始化为0 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //ArraList 计算容量 private static int calculateCapacity(Object[] elementData, int minCapacity) { //初始化构造函数时，elementData 指向了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的引用 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 首次添加元素 初始化数组容量为10 return Math.max(DEFAULT_CAPACITY, minCapacity); //DEFAULT_CAPACITY = 10; 默认容量 } return minCapacity; } // 最终明确容量，如果不够进行扩容 // 初次添加时 初始化数组容量为10 所以此处 minCapacity = 10 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 初次添加元素 10 - 0 > 0 所以会执行扩容 // 再次执行的时候，因为已经经过了扩容，所以elementData.length = 10 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code // 初始化时 elementData.length = 0 所以 oldCapacity = 0 // 旧容量就是原数组的长度 int oldCapacity = elementData.length; // 右移：>> 右移几位就相当于除以2的n 次幂 // 左移：<< 左移几位就相当于乘以2的n 次幂 // 新容量 = 旧容量+右移过后的值 // 新容量 (newCapacity ) = 旧容量(oldCapacity ) + 旧容量右移1位，也就是扩大1.5倍) int newCapacity = oldCapacity + (oldCapacity >> 1); //初始化 第一次添加 0 - 10 < 0 newCapacity：新容量赋值为10 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 拷贝到新扩容后的elementData 中去，并返回elementData 一个新容量数组 elementData = Arrays.copyOf(elementData, newCapacity); //至此时，则完成一个数组的扩容 }
5.1.1、java 位移运算符扩展
- 右移位运算符（>>）
- >> 运算规则：按二进制形式把所有的数字向右移动对应位数，低位移出（舍弃），高位的空位补符号位，移位后得到的数字为正数则补0，负数补1。
- 例如11 >>2，则是将数字11右移2位
- 分析：11的二进制形式为：1011
0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。
则得到的最终结果是 0000 0000 0000 0000 0000 0000 0000 0010. 转换为十进制是3.
数学意义：右移一位相当于除2，右移n位相当于除以2的n次方。
- 左移位运算符（<<）
- << 运算规则：按二进制形式把所有的数字向左移动对应的位数，高位移出(舍弃)，低位的空位补零。
- 例如 3 << 2 //12 则是将数字3左移2位 322= 3*（2的2次方）
- 分析：首先把3转换为二进制数字 0011
0000 0000 0000 0000 0000 0000 0011，然后把该数字高位（左侧）的两个零移出，其他的数字都朝左平移2位，最后在低位（右侧）的两个空位补零。
则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，则转换为十进制是12.
数学意义：在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方
在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。
5.2、ArrayList 频繁扩容导致添加性能急剧下降，如何处理；
- 首先明确，频繁扩容为什么会导致性能下降；
- 性能下降的原因是在扩容之后，执行了拷贝的工作，需要把旧的数据复制到新的数据里面，频繁的如此操作就会导致性能的下降；
- 解决办法就是：在构造ArrayList的时候，可以对数组容量大小的初始化，避免其频繁扩容，同时能防止造成OOM异常；
5.3、ArrayList 插入或删除元素一定比LinkedList慢么？
- ArrayList 添加新元素是的步骤：
- 判断是否需要扩容，如果不需要，则直接在尾部添加，如果需要，则先扩容1.5倍，然后再进行拷贝元素，
- linkedList 添加数据步骤；
- 直接创建新的节点，移动指针即可
- 直接上代码分析
public static void main(String[] args) { ArrayList<String> arrayList = new ArrayList<>(); long startTime = System.currentTimeMillis(); for (int i = 0 ; i < 10000000 ; i++){ arrayList.add(i + "个元素"); } long endTime = System.currentTimeMillis(); System.out.println("addArrayList add 共耗时："+ (endTime - startTime)); LinkedList<String> LinkedList = new LinkedList<>(); startTime = System.currentTimeMillis(); for (int i = 0 ; i < 10000000 ; i++){ LinkedList.add(i + "个元素"); } endTime = System.currentTimeMillis(); System.out.println("LinkedList add 共耗时："+ (endTime - startTime)); // arrayList 当添加数据到一定量的时候，由于数据扩容会越来越少，所以添加就会越来越快 // 当LinkedList添加数据一直都需要创建新的节点，所以数量越大添加就会越来越慢 startTime = System.currentTimeMillis(); arrayList.remove(50000); endTime = System.currentTimeMillis(); System.out.println("addArrayList remove 共耗时："+ (endTime - startTime)); startTime = System.currentTimeMillis(); LinkedList.remove(50000); endTime = System.currentTimeMillis(); System.out.println("LinkedList remove 共耗时："+ (endTime - startTime)); // arrayList删除数据 根据索引算出数组移动位置，然后创建新数组，把旧数据拷贝过来 // linkList 删除数据 根据索引遍历出索引节点，然后移动前置 后置节点位置 }- 打印三次输出结果如下
--- 第一次 ---- addArrayList add 共耗时：4646 LinkedList add 共耗时：4800 addArrayList remove 共耗时：4 LinkedList remove 共耗时：1 --- 第二次 ---- addArrayList add 共耗时：5601 LinkedList add 共耗时：7139 addArrayList remove 共耗时：4 LinkedList remove 共耗时：1 --- 第三次 ---- addArrayList add 共耗时：5512 LinkedList add 共耗时：7107 addArrayList remove 共耗时：4 LinkedList remove 共耗时：1- 结论： 对于添加和删除操作add和remove，一般大家都会说LinkedList要比ArrayList快，因为ArrayList要移动数据。但是实际情况并非这样，要就实际情况，实际数据量而言，数据量大的时候addArrayList 比 LinkedList 效率还是高一些；删除数据同比还是LinkList 快一些，但也快不了多少1ms;
- LinkedList底层是一个一个查找的，虽然ArrayList底层具有复制的操作，但是也不见得LinkedList的查找效率一定比ArrayList要高。LinkedList中的node方法在节点多的情况下是很费时间的。
5.4、ArrayList 是线程安全的么？
- 答案：线程不安全
- 上代码测试
ArrayListThreadTask线程类，定义一个成员变量共享集合数据
public class ArrayListThreadTask implements Runnable { //成员变量 list 作为一个共享的集合使用 private List<String> list; public ArrayListThreadTask(List<String> list) { this.list = list; } @Override public void run() { try { Thread.sleep(50); } catch (InterruptedException e) { e.printStackTrace(); } // 共享集合中存储线程名称 list.add(Thread.currentThread().getName()); } }ArrayListThreadTaskDemo测试类(开启 5 个线程，查看存入list 中的数据是否为5个)
public class ArrayListThreadTaskDemo { public static void main(String[] args) throws InterruptedException { List<String> list = new ArrayList<>(); ArrayListThreadTask threadTask = new ArrayListThreadTask(list); //创建线程任务开启 5个线程 for(int i = 0 ; i < 5 ; i++){ new Thread(threadTask).start(); } Thread.sleep(3000); //创建线程任务开启 50个线程 for(int i = 0 ; i < list.size() ; i++){ System.out.println(list.get(i)); } System.out.println("集合长度："+ list.size()); } }- 输出结果如下：
null null Thread-1 Thread-3 Thread-2 集合长度：5造成这种情况的原因:当多条线程添加到集合的某一个位置上的时候，就会出现 其它位置为null的情况；因为程序执行是很快的，可能线程4 执行的时候把名称加到了集合索引3的位置上，线程而线程1同样也把线程名称加到了索引3的位置， 线程5同样如此也加到了对应的其它位置，导致0，1索引位置为null解决办法- 1、加锁或者synchronized。
- 修改
ArrayListThreadTask线程类，增加synchronized 同步 代码如下
public class ArrayListThreadTask implements Runnable { //成员变量 list 作为一个共享的集合使用 private List<String> list; public ArrayListThreadTask(List<String> list) { this.list = list; } @Override public void run() { synchronized (this){ try { Thread.sleep(50); } catch (InterruptedException e) { e.printStackTrace(); } // 共享集合中存储线程名称 list.add(Thread.currentThread().getName()); } } }- 测试结果如下
Thread-0 Thread-2 Thread-3 Thread-4 Thread-1 集合长度：5- 2、可以使用 Vector。但是线程安全就代表效率比较低，根据自己需求来选择对应集合使用。
- 修改代码
ArrayListThreadTaskDemo测试类 如下
public static void main(String[] args) throws InterruptedException { //List<String> list = new ArrayList<>(); List<String> list = new Vector<>(); ArrayListThreadTask threadTask = new ArrayListThreadTask(list); //创建线程任务开启 5个线程 for(int i = 0 ; i < 50 ; i++){ new Thread(threadTask).start(); } Thread.sleep(3000); //创建线程任务开启 50个线程 for(int i = 0 ; i < list.size() ; i++){ System.out.println(list.get(i)); } System.out.println("集合长度："+ list.size()); }- 测试结果都可以保证数据同时保存到list 中；
- 3、使用集合工具类 Collections.synchronizedList将ArrayList包装成线程安全集合。
- 代码如下
public static void main(String[] args) throws InterruptedException { List<String> list1 = new ArrayList<>(); // List<String> list = new Vector<>(); //通过collections 工具类把list1 变为线程安全的集合 List<String> list = Collections.synchronizedList(list1); ArrayListThreadTask threadTask = new ArrayListThreadTask(list); //创建线程任务开启 5个线程 for(int i = 0 ; i < 50 ; i++){ new Thread(threadTask).start(); } Thread.sleep(3000); //创建线程任务开启 50个线程 for(int i = 0 ; i < list.size() ; i++){ System.out.println(list.get(i)); } System.out.println("集合长度："+ list.size()); }- 测试结果都可以保证数据同时保存到list 中； -
5.5、如何复制某个ArrayList到另一个ArrayList 中去？
- 1、使用clone()方法；
- 2、使用ArrayList 构造方法；
- 3、使用addAll方法
5.6、已知成员变量集合存储N多用户名称，在多线程的环境下，使用迭代器在读取集合数据的同时，如何保证还可以正常的写入数据到集合？
- 直接上代码测试如下
ArrayListAddUserThreadTask线程类，定义共享集合，存储不同用户
public class ArrayListAddUserThreadTask implements Runnable { //成员变量 list 作为一个共享的集合使用 private static ArrayList<String> list = new ArrayList<>(); static { // 初始化用户数据 list.add("java"); list.add("python"); list.add("php"); } @Override public void run() { for (String str:list) { System.out.println(str); list.add("bigData"); } } }ArrayListAddUserThreadTaskDemo测试类，开启任务读写测试类
public class ArrayListAddUserThreadTaskDemo { public static void main(String[] args) { // 创建线程任务 ArrayListAddUserThreadTask arrayListAddUserThreadTask = new ArrayListAddUserThreadTask(); for (int i = 0; i < 10; i++) { new Thread(arrayListAddUserThreadTask).start(); } } }- 测试结果如下：
“ConcurrentModificationException”报错啦
java …… …… Exception in thread "Thread-9" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at source.arrayList.ArrayListAddUserThreadTask.run(ArrayListAddUserThreadTask.java:24) at java.lang.Thread.run(Thread.java:748)- 直接使用ArrayList 做数据读写遍历，最终报错
“ConcurrentModificationException” - 原因：1、使用了线程不安全的ArrayList 2、使用迭代器同时读、写集合操作 最终导致异常，如果非要进行如此操作，可以使用
CopyOnWriteArrayList一个读写分离的集合 CopyOnWriteArrayList介绍 一个读写分离的集合
public class CopyOnWriteArrayList<E> extends Object implements List<E>, RandomAccess, Cloneable, SerializableCopyOnWriteArrayList是一个线程安全的变体ArrayList- 该数组在迭代器的生命周期内永远不会改变，所以干扰是不可能的，迭代器保证不会丢弃ConcurrentModificationException 。
- 修改以上代码
public class ArrayListAddUserThreadTask implements Runnable { //成员变量 list 作为一个共享的集合使用 //private static ArrayList<String> list = new ArrayList<>(); private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(); static { list.add("java"); list.add("python"); list.add("php"); } @Override public void run() { for (String str:list) { System.out.println(str); list.add("bigData"); } } }
5.7、ArrayList 和 LinkList 区别
ArrayList- 1、
ArrayList基于动态数组的数据结构,说白了它的底层就是数组 - 2、
ArrayList对于随机访问的get和set，ArrayList要优于LinkedList - 3、
ArrayList对于随机操作的add和remove，ArrayList不一定比LinkedList慢，由于ArrayList底层是动态数组可以自己指定长度，不是每一次都需要扩容创建新数组。而LinkedList底层是链表，如果结点多查找的效率也低
- 1、
LinkedList- 1、基于双向链表的数据结构,说白了它的底层就是链表结构
- 2、对于顺序操作，
LinkedList不一定比ArrayList慢， - 3、对于随机操作，
LinkedList明显效率比较低。