ArrayList知识点(面试)

        上一篇我们说了hashmap的相关知识点，这一篇我们再说一些ArrayList的相关知识，因为ArrayList也是我们项目中比较常用的。

ArrayList(底层是数组)

底层工作原理

• 首先，在构造ArrayList的时候会先看有没有指定容量，如果没有，则会先构造一个空数组，如果有，则会根据指定容量创建数组。

• 在插入数据的时候，会先判断当前数组是否有足够的空间插入新数据，如果没有则会按照1.5倍的扩容标准进行扩容，同时如果容量足够，或再判断插入的位置有没有越界，以及该位置是否有元素

• 在获取元素的时候同样也是先判断当前下标是否有越界，没有才能从数组中获取元素。

扩容机制

1. 首先，ArrayList初始化的长度为10，如果插入的数据长度超过10则会自动触发扩容机制

2. ArrayList会创建一个比原来数组长1.5倍的新数组，然后通过Arrays.copyof方法将原来的数组copy到新数组中

3. 最后将新元素插入到新数组中

线程不安全是怎么解决的

先看一段代码

 @Test
     void testArrayList() {
         List list = new ArrayList<>(12);
         list.add(1);
         list.add(2);
         list.add(3);
         System.out.println(list);
 //        遍历元素
         Thread t1 = new Thread(() -> {
             for (Integer integer : list) {
                 System.out.println(integer);
             }
         });
 //              新增元素
         Thread t2 = new Thread(() -> {
             for (int i = 4; i < 8; i++) {
                 list.add(i);
             }
         });
         t1.start();
         t2.start();
     }

以上代码运行后结果如下：

ArrayList在遍历的时候会去调用Collection中的next方法，然后通过checkForComodification()方法检查modCount和expectedModeCount是否相等，若不等则抛出ConcurrentModificationException，在上面的代码中我们对于list在遍历的同时也在增加数组中对的元素，modCount和expectedModeCount肯定不相等啦，所以就报错了。

modCount表示集合被修改的次数，每修改一次次数加1，而expectedModeCount是迭代器的属性，在迭代器创建时被赋予和modCount一样的值

其实在这里也是用到了fail-fast(快速失效)系统，这里简单说明一下这个是什么

fail-fast和fail-safe是什么意思？

fail-fast简单通俗的来讲就是在做系统设计的时候考虑异常情况，如果有异常情况，则抛出异常并且不会执行后面的代码

 public int divide(int dividend,int divisor){
     if(divisor == 0){
         throw new RuntimeException("divisor can't be zero");
     }
     return dividend/divisor;
 }

        以上的代码中，如果divisor为0，我们就会抛出一个异常并终止程序继续运行下面的代码，这样做的好处是一方面可以停止运行复杂的代码，另一方面，可以将一些异常单独进行处理。

        fail-safe就是为了避免触发fail-fast机制引发出来的异常，用java中一些带有fail-safe机制的集合类来控制。

        这样的集容器在遍历的时候会先拷贝一份出来而不是直接在原集合上进行操作，java.util.concurrent下的包都是fail-safe机制的，可以在多线程下进行并发修改(remove/add)，就比如下面要说到的CopyOnWriteArrayList也是这种机制

        但是，通过这样的方式虽然是可以防止ConcurrentModificationException异常的，但是不能通过迭代器遍历元素，即元素中的元素如果发生改变，迭代器是不知道的，迭代器拿到的只是刚开始集合中的元素。

所以这个时候我们可以对其进行加锁

使用synchronized进行加锁

@Test
     void testArrayList() {
         List list = new ArrayList<>(12);
         list.add(1);
         list.add(2);
         list.add(3);
         System.out.println(list);
 //        遍历元素
         Thread t1 = new Thread(() -> {
             synchronized (list){
                 for (Integer integer : list) {
                     System.out.println(integer);
                 }
             }
 ​
         });
 //              新增元素
         Thread t2 = new Thread(() -> {
             synchronized (list) {
                 for (int i = 4; i < 8; i++) {
                     list.add(i);
                 }
             }
         });
         t1.start();
         t2.start();
     }

使用ReentrantLock进行加锁

 @Test
     void testArrayList() {
         List list =new ArrayList<>(12);
         list.add(1);
         list.add(2);
         list.add(3);
         System.out.println(list);
         Lock lock=new ReentrantLock();
         // 遍历元素
         Thread t1 = new Thread(() -> {
 //            加锁
             lock.lock();
                 for (Integer integer : list) {
                     System.out.println(integer);
                 }
 //                释放锁
             lock.unlock();
         });
         // 新增元素
         Thread t2 = new Thread(() -> {
 //            加锁
             lock.lock();
             for (int i = 4; i < 8; i++) {
                 list.add(i);
             }
 //            释放锁
             lock.unlock();
         });
         t1.start();
         t2.start();
     }

        或者可以使用Collections.synchronizedxxxx来解决，把创建list的那行代码改成List list = Collections.synchronizedList(new ArrayList<>())就行了

或者使用 CopyOnWriteArrayList来实现

  @Test
     void testArrayList() {
         List list = new CopyOnWriteArrayList<>();
         list.add(1);
         list.add(2);
         list.add(3);
         System.out.println(list);
         // 遍历元素
         Thread t1 = new Thread(() -> {
             for (Integer integer : list) {
                 System.out.println(integer);
             }
         });
         // 新增元素
         Thread t2 = new Thread(() -> {
             for (int i = 4; i < 8; i++) {
                 list.add(i);
             }
         });
         t1.start();
         t2.start();
     }

这里扩展一下什么是Copy-On-Write？

        简称COW，其基本思路是一开始大家共享一个内容，后来如果有人来修改这个资源，这时就会先copy一份出来(延时懒惰策略)，在这份中进行修改，修改完成后再把原来的容器指向这份新的容器。

序列化是怎么解决的

        在序列化中，如果被序列化的类中定义了readObject和writeObject方法，则虚拟机就会尝试去通过用户自定义的这两个方法进行序列化，对于自定义的序列化方法好处是可以在序列化的过程中动态修改序列化的值。

        如果类中没有定义，则会用ObjectOutPutStream中默认的DefaultReadStream和DefaultWriteStream方法。

好了，现在再来说一下面试中最常被问到的内容

ArrayList和LinkList有什么区别？

• 从地址上来说，ArrayList底层是一个数组，因此对于数组这种数据结构的话，它的地址是连续的，而对于LinkList来说，它的底层是一个循环双向链表的结构，地址就不是连续的。

• 从操作上来讲，ArrayList在查询元素方面快于LinkList，且时间复杂度可以达到O(1),而LinkList的时间复杂度达到了O(n)；但是在修改元素和增加元素上来讲，ArrayList时间复杂度达到了O(n),LinkList时间复杂度为O(1).