java集合框架List

DBC 700 0

1.java集合框架里面List常见基础面试题

说下Vector和ArrayList、LinkedList联系和区别?分别的使用场景

温馨提示

答案:

  • 线程安全
    • ArrayList:底层是数组实现,线程不安全,查询和修改非常快,但是增加和删除慢
    • LinkedList: 底层是双向链表,线程不安全,查询和修改速度慢,但是增加和删除速度快
    • Vector: 底层是数组实现,线程安全的,操作的时候使用synchronized进行加锁
  • 使用场景
    • Vector已经很少用了
    • 增加和删除场景多则用LinkedList
    • 查询和修改多则用ArrayList

2.List的掌握情况(追问系列)

如果需要保证线程安全,ArrayList应该怎么做,用有几种方式

温馨提示

方式一:自己写个包装类,根据业务一般是add/update/remove加锁

方式二:Collections.synchronizedList(new ArrayList<>()); 使用synchronized加锁

方式三:CopyOnWriteArrayList<>() 使用ReentrantLock加锁

java集合框架List插图

3.基于CopyOnWriteArrayList进行继续追问

如果回答到上面的点则继续问,了解CopyOnWriteArrayList吗?和 Collections.synchronizedList实现线程安全有什么区别, 使用场景是怎样的?

温馨提示
  • CopyOnWriteArrayList:执行修改操作时,会拷贝一份新的数组进行操作(add、set、remove等),代价十分昂贵,在执行完修改后将原来集合指向新的集合来完成修改操作,源码里面用ReentrantLock可重入锁来保证不会有多个线程同时拷贝一份数组
    • 场景:读高性能,适用读操作远远大于写操作的场景中使用(读的时候是不需要加锁的,直接获取,删除和增加是需要加锁的, 读多写少)

     

  • Collections.synchronizedList:线程安全的原因是因为它几乎在每个方法中都使用了synchronized同步*锁
    • 场景:写操作性能比CopyOnWriteArrayList好,读操作性能并不如CopyOnWriteArrayList

CopyOnWriteArrayList的设计思想是怎样的,有什么缺点?

温馨提示

答案:设计思想:读写分离+最终一致

缺点:内存占用问题,写时复制机制,内存里会同时驻扎两个对象的内存,旧的对象和新写入的对象,如果对象大则容易发生Yong GC和Full GC

补概念——Yong GC和Full GC

MinorGC、YoungGC

其实所谓的 MinorGC,也可以称为 YoungGC,这二者是相同的,都是专门针对于新生代的GC.

「新生代」也可以称为「年轻代」,在新生代的Eden内存区域被占满之后,就会触发「新生代」的GC,或者叫「年轻代」的GC,也就是所谓的 MinorGC 和 YoungGC

FullGC

从字面上意思其实就可以理解了,“Full” 就是整个的,完整的意思,所以就是对 JVM 进行一次整体 垃圾回收,把各个内存空间区域,不管是新生代,老年代,永久代的垃圾统统都回收掉。

总结

温馨提示

但这里,往往有一些人会把 FullGC 和 OldGC 混淆:

说实话,不同的人对同一个概念肯定会有不同理解和看法的,这个大家可以相互讨论 。

有的人也把MajorGC [ˈmeɪdʒər] 和FullGC划等号,也有人把 FullGC 和 OldGC 划等号,其实这些概念在国内混淆还是很严重的。

那么为什么会这样呢:

其实大家在很多地方看到一个说法,意思就是说: 「OldGC执行的时候,一般都会带上一次YoungGC」

很多人不理解,其实如果你把各个GC触发的条件分析清楚了就知道了,

(1)YoungGC 就是在新生代的Eden区域满了之后,就会触发,采用复利算法来回收新生代的垃圾

(2)发生YoungGC之前往往会先检查一下老年代的空间,如果说明本次YoungGC后可能升入老年代对象的大小,可能超过了老年代当前可用内存空间,此时必须先触发一次OldGC给老年代腾出更多的空间,然后再执行YoungGC

所以,一般OldGC 很可能就是在 YoungGC 之前触发,所以自然OldGC一般都会跟一次YoungGC连带关联在一起了。 那他触发的实际上就是FullGC,因为我们知道 FullGC会包含YoungGC、OldGC和永久代的GC 也就是说触发FullGC的时候,可能就会去回收年轻代、老年代和永久代三个区域的垃圾对象。

我们可以通过jstat -gcutil 命令监控当前系统的GC状况
java集合框架List插图2
可以看到在GC日志中,FullGC会同时对年轻代、老年代、永久代都进行了垃圾回收。

最后,小结一下:

YoungGC 就是年轻代的gc ,OldGC就是老年代的gc ,FullGC是针对年轻代、老年代、永久代进行的整体的gc 。 而且还有几个其他的名词跟他们有重叠的含义,

比如 MinorGC也可以称之为YoungGC,MajorGC也可以称之为OldGC,

有的人也把Major GC和Full GC划等号,也有人把Full GC和Old GC划等号。

所以以后大家在外面跟人聊起各种GC名词的时候,一定要问清楚他指代的到底是什么哦!

以上转载自:https://www.icode9.com/content-1-891506.html

4.基于List进行继续二次追问,进阶扩容机制+源码剖析

说下ArrayList的扩容机制是怎样的

温馨提示

注意:JDK1.7之前ArrayList默认大小是10,JDk1.7之后是0

未指定集合容量,默认是0,若已经指定大小则集合大小为指定的;
当集合第一次添加元素的时候,集合大小扩容为10
ArrayList的元素个数大于其容量,扩容的大小= 原始大小+原始大小/2

5.基于List进行继续追问,进阶连环炮,代码实战

设计一个简单的ArrayList【需要包含 构造函数(有参和无参)、add(obj)、 扩容机制】

设计一个简单的ArrayList【remove(index)、get(index) 、indexOf(o) ,set(int index,Object obj)】

import java.io.Serializable;

public class MyArrayList implements Serializable {
    //使用这个字段,来判断当前集合类是否被并发修改,即迭代器并发修改的fail-fast机制
    private transient int modCount = 0;

    //第一次扩容的容量
    private static final int DEFAULT_CAPACITY = 10;

    //用于初始化空的list
    private static final Object[] EMPTY_ELEMENT_DATA = {};


    //实际存储的元素
    transient Object[] elementData;

    //实际list集合大小,从0开始
    private int size;

    public MyArrayList() {
        this.elementData = EMPTY_ELEMENT_DATA;
    }

    public MyArrayList(int initialCapcity) {
        if (initialCapcity > 0) {
            this.elementData = new Object[initialCapcity];
        } else if (initialCapcity == 0) {
            this.elementData = EMPTY_ELEMENT_DATA;
        } else {
            throw new IllegalArgumentException("参数异常");
        }
    }

    public boolean add(Object e) {
        //判断容量
        ensureCapacityInternal(size + 1);
        //使用下标赋值,尾部插入

        elementData[size++] = e;

        return true;
    }


    /**
     * 计算容量+确保容量
     * @param minCapacity 需要的容量
     */
    private void ensureCapacityInternal(int minCapacity) {

        //用于并发判断
        modCount++;
        //如果是初次扩容,则使用默认的容量
        if (elementData == EMPTY_ELEMENT_DATA) {

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        //是否需要扩容,需要的最少容量大于现在数组的长度则要扩容
        if (minCapacity - elementData.length > 0) {
            int oldCapacity = elementData.length;

            int newCapacity = oldCapacity + (oldCapacity >> 1);

            //如果新容量 < 最小容量, 则讲最新的容量赋值给新的容量
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }

            //创建新数组
            Object[] objects = new Object[newCapacity];

            //将旧的数组复制到新的数组里面
            System.arraycopy(elementData, 0, objects, 0, elementData.length);

            //修改引用
            elementData = objects;

        }

    }


    /**
     * 通过下标获取对象
     * @param index
     * @return
     */
    public Object get(int index){
        rangeCheck(index);
        return elementData[index];
    }


    private void rangeCheck(int index) {
        if (index > size || size<0){
            throw new IndexOutOfBoundsException("数组越界");
        }
    }

    /**
     * 判断对象所在的位置
     * @param o
     * @return
     */
    public int indexOf(Object 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++){
                return i;
            }
        }
        return -1;
    }

    public Object set(int index,Object obj){
        rangeCheck(index);
        Object oldValue = elementData[index];

        elementData[index]= obj;
        return oldValue;
    }

    /**
     * 根据索引删除元素
     * @param index
     * @return
     */
    public Object remove(int index){
        rangeCheck(index);
        //用于并发判断
        modCount++;
        Object oldValue = elementData[index];

        //计算要删除的位置后面有几个元素
        int  numMoved = size - index - 1;
        if (numMoved>0){
            System.arraycopy(elementData,index+1,elementData,index,numMoved);
        }
        //将多出的位置设置为空,没有引用对象,垃圾收集器可以回收,如果不设置为空,将会保存一个引用,可能会造成内存泄漏
        elementData[--size] = numMoved;
        return oldValue;
    }

    /**
     * 获取数组实际大小
     * @return
     */
    public int size(){
        return this.size;
    }


}
测试一下
import java.io.File;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class test {
    public static void main(String[] args) {

        MyArrayList list = new MyArrayList();
        for (int i = 1;i<10;i++){
            list.add(""+i);

        }

        list.remove(5);
        list.set(2,"qwqe");
        for (int i = 0;i<list.size();i++){
            System.out.println(list.get(i));
        }

    }

}



控制台输出

java集合框架List插图4

这里补充几个小知识点

Math.max()

Math.max()

Math.max() 函数返回一组数中的最大值。下面是js例子

console.log(Math.max(1, 3, 2));
// expected output: 3

console.log(Math.max(-1, -3, -2));
// expected output: -1

const array1 = [1, 3, 2];

console.log(Math.max(...array1));
// expected output: 3
输出结果

System.arraycopy

System.arraycopy

System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制。其函数原型是:
public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length);
* @param src the source array. 源数组
* @param srcPos starting position in the source array. 源数组的起始位置
* @param dest the destination array. 目标数组
* @param destPos starting position in the destination data. 目标数组的起始位置
* @param length the number of array elements to be copied. 复制的长度
举个栗子:
将array数组复制到新的数组中;
int[] array = {1, 2, 3, 4, 5};
int[] targetArr = new int[array.length];
System.arraycopy(array,0,targetArr,0,array.length);

fail-fast

fail-fast

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。例如:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。

外文名
fail-fast
概    念
是一种机制
要了解fail-fast机制,我们首先要对ConcurrentModificationException 异常有所了解。当方法检测到对象的并发修改,但不允许这种修改时就抛出该异常。同时需要注意的是,该异常不会始终指出对象已经由不同线程并发修改,如果单线程违反了规则,同样也有可能会抛出该异常。
诚然,迭代器的快速失败行为无法得到保证,它不能保证一定会出现该错误,但是快速失败操作会尽最大努力抛出ConcurrentModificationException异常,所以因此,为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法,正确做法是:ConcurrentModificationException 应该仅用于检测 bug。
还需要更详细的,可以看这篇文章: 浅谈fail-fast机制

 

发表评论 取消回复
表情 图片 链接 代码

分享