实习面试准备——List

柔情只为你懂 2023-07-04 15:52 76阅读 0赞

## 实习面试准备——List ##

寒假一直在家学习Java基础知识、数据结构与算法、多线程、Redis、MySQL优化等，准备开学后投出实习简历，下面是我的实习准备（根据虎牙校招的面经来总结的）

#### 1.Java集合List详解 ####

集合框架：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]

在Collection中，List集合是有序的，可对其中每个元素的插入位置进行精确地控制，可以通过索引来访问元素，遍历元素。在List集合中，我们常用到ArrayList和LinkedList这两个类。  
在List集合中，常用到**ArrayList**和**LinkedList**  
**ArrayList**底层通过**数组**实现，**随着元素的增加而动态扩容**  
**LinkedList**底层通过**链表**来实现，随着元素的增加不断**向链表的后端增加节点。**

**ArrayList:**  
它继承于AbstractList，实现了List, RandomAccess, Cloneable, Serializable接口。  
(1)ArrayList实现List，得到了List集合框架基础功能；  
(2)ArrayList实现RandomAccess，获得了快速随机访问存储元素的功能，RandomAccess是一个标记接口，没有任何方法；  
(3)ArrayList实现Cloneable，得到了clone()方法，可以实现克隆功能；  
(4)ArrayList实现Serializable，表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议。  
**特点：**  
(1)容量不固定，随着容量的增加而动态扩容（阈值基本不会达到）  
(2)有序集合（插入的顺序==输出的顺序）  
(3)插入的元素可以为null  
(4)随机访问的效率高，增删改效率较低（相对于LinkedList来说）  
(5)线程不安全

**LinkedList**  
它继承AbstractSequentialList，实现了List, Deque, Cloneable, Serializable接口。  
(1)LinkedList实现List，得到了List集合框架基础功能；  
(2)LinkedList实现Deque，Deque 是一个双向队列，也就是既可以先入先出，又可以先入后出，说简单些就是既可以在头部添加元素，也可以在尾部添加元素；  
(3)LinkedList实现Cloneable，得到了clone()方法，可以实现克隆功能；  
(4)LinkedList实现Serializable，表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议。  
**特点：**  
(1)是一个双向链表，每一个节点都拥有指向前后节点的引用  
(2)相比于ArrayList来说，LinkedList的随机访问效率更低。

**List接口中的常用方法**

A:添加功能
    boolean add(E e):向集合中添加一个元素
    void add(int index, E element):在指定位置添加元素
    boolean addAll(Collection<? extends E> c)：向集合中添加一个集合的元素。
    
    B:删除功能
    void clear()：删除集合中的所有元素
    E remove(int index)：根据指定索引删除元素，并把删除的元素返回
    boolean remove(Object o)：从集合中删除指定的元素
    boolean removeAll(Collection<?> c):从集合中删除一个指定的集合元素。
    
    C:修改功能
    E set(int index, E element):把指定索引位置的元素修改为指定的值，返回修改前的值。
    
    D:获取功能
    E get(int index)：获取指定位置的元素
    Iterator iterator():就是用来获取集合中每一个元素。
    
    E:判断功能
    boolean isEmpty()：判断集合是否为空。
    boolean contains(Object o)：判断集合中是否存在指定的元素。
    boolean containsAll(Collection<?> c)：判断集合中是否存在指定的一个集合中的元素。
    
    F:长度功能
    int size():获取集合中的元素个数
    
    G:把集合转换成数组
    Object[] toArray():把集合变成数组。

ArrayList具体实现List接口方法就不一一列出了，因为JDK源码里面已经非常细致和完整

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    { 
    	//实现Serializable接口，生成的序列版本号：
    	private static final long serialVersionUID = 8683452581122892189L;
    	//ArrayList初始容量大小：在无参构造中不使用了
        private static final int DEFAULT_CAPACITY = 10;
    	//空数组对象：初始化中默认赋值给elementData
        private static final Object[] EMPTY_ELEMENTDATA = { };
    	//空数组对象
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    	//ArrayList中实际存储元素的数组，非私有是为了简化嵌套类的访问
        transient Object[] elementData; 
        //集合实际存储元素长度：
        private int size;
    
    	//ArrayList有参构造：容量大小
        public ArrayList(int initialCapacity) { 
        	//initialCapacity大于0，初始化一个大小为initialCapacity的Object数组
            if (initialCapacity > 0) { 
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
            //initialCapacity等于0，初始化一个空数组
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
            //否则，抛出异常
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    
        //ArrayList无参构造
        public ArrayList() { 
        	//初始化数组：空数组，容量为0
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        //ArrayList有参构造：Java集合
        public ArrayList(Collection<? extends E> c) { 
        	//将集合转换为数组
            elementData = c.toArray();
            if ((size = elementData.length) != 0) { 
            //如果elementData的长度不为0
              
                if (elementData.getClass() != Object[].class)
                 // 官方的说法：c.toArray might (incorrectly) not return Object[] (see 6260652)
                 // 这是因为实现 Collection接口的类可能会重写toArray()方法，可能返回的就不是Object 数组了
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else { 
                // 否则，初始化一个空数组
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

用于添加元素—add()方法：

//往ArrayList添加元素
    	public boolean add(E e) { 
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //索引后移，将对应角标下的元素赋值为e：
            elementData[size++] = e;
            return true;
        }
        //得到最小扩容量
        private void ensureCapacityInternal(int minCapacity) { 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
        //扩展时modCount值改变
        private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
            // overflow-conscious code
             //如果扩展的容量比原有容量大，才扩展。
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            //如果数组为空，数组的扩容量为10
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            //如果数组非空，数组的扩容量为size+1
            return minCapacity;
        }
    	private void grow(int minCapacity) { 
            int oldCapacity = elementData.length;//原来数组的长度
            int newCapacity = oldCapacity + (oldCapacity >> 1);//oldCapacity >> 1，右移1位，即除以了2，即newCapacity =1.5*oldCapacity 
            if (newCapacity - minCapacity < 0)//如果想要扩展的容量比新容量大，那么将新容量置为作者要求的大小。
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)//如果想要扩展的容量大于Integer.MAX_VALUE - 8，则取最大容量值和指定值之间较小的一个作为新容量
                newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity);//调用Arrays.copyOf()方法，该方法的底层就是数组的拷贝，实现数组扩容
        }

用于删除元素:  
remove(int index)是针对于角标来进行删除，不需要去遍历整个集合，效率更高；  
remove(Object o)是针对于对象来进行删除，需要遍历整个集合进行equals()方法比对，所以效率较低；  
**无论是哪种形式的删除，最终都会调用System.arraycopy()方法进行数组复制操作，所以效率都会受到影响；**

//在ArrayList的移除index位置的元素
    	public E remove(int index) { 
    		//检查角标是否合法：不合法抛异常
            rangeCheck(index);
    		//AbstractList中的成员变量protected transient int modCount = 0，操作数+1：
            modCount++;
            //获取当前角标的value:
            E oldValue = elementData(index);
    		//获取需要删除元素 到最后一个元素的长度，也就是删除元素后，后续元素移动的个数；
            int numMoved = size - index - 1;
            //如果移动元素个数大于0 ，也就是说删除的不是最后一个元素
            if (numMoved > 0)
            	// 将elementData数组index+1位置开始拷贝到elementData从index开始的空间
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            //size减1，并将最后一个元素置为null，
            elementData[--size] = null; // GC，垃圾收集
    		 //返回被删除的元素
            return oldValue;
        }
        //在ArrayList的移除对象为O的元素，不返回被删除的元素：
    	public boolean remove(Object o) { 
    		//如果o==null，则遍历集合，判断哪个元素为null：
            if (o == null) { 
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) { 
                    	//快速删除，和前面的remove（index）一样的逻辑
                        fastRemove(index);
                        return true;
                    }
            } else { 
            	//同理：
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) { 
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
         //快速删除：
    	 private void fastRemove(int index) { 
    	 	//操作数+1
            modCount++;
            //获取需要删除元素 到最后一个元素的长度，也就是删除元素后，后续元素移动的个数；
            int numMoved = size - index - 1;
            //如果移动元素个数大于0 ，也就是说删除的不是最后一个元素：
            if (numMoved > 0)
            	// 将elementData数组index+1位置开始拷贝到elementData从index开始的空间
                System.arraycopy(elementData, index+1, elementData, index,numMoved);
    		//size减1，并将最后一个元素置为null
            elementData[--size] = null; // clear to let GC do its work
        }

用于改变ArrayList某个位置的值  
set(int index, E element)方法，由于ArrayList实现了RandomAccess，所以具备了随机访问特性，调用elementData()可以获取到对应元素的值

//设置index位置的元素值为element，返回该位置的原来的值
     public E set(int index, E element) { 
     		//检查index是否合法：判断index是否大于size，否则抛出IndexOutOfBoundsException异常
            rangeCheck(index);
    		//获取该index原来的元素
            E oldValue = elementData(index);
            //替换成新的元素
            elementData[index] = element;
            //返回旧的元素
            return oldValue;
        }

获取index位置上的元素  
get(int index)方法

public E get(int index) { 
     		//检查index是否合法：
            rangeCheck(index);
            //获取数组index位置的元素：返回时类型转换
            return elementData(index);
        }
     	//获取数组index位置的元素：返回时类型转换
    	@SuppressWarnings("unchecked")
        E elementData(int index) { 
            return (E) elementData[index];
        }

上面的源码中出现了挺多次modCount，下面让我们来看一下modCount的含义：  
首先：modCount是AbstractList中的成员变量  
AbstractList.java

protected transient int modCount = 0;

ArrayList获取迭代器对象：  
ArrayList.java

//返回一个Iterator对象，Itr为ArrayList的一个内部类，其实现了Iterator<E>接口
    	public Iterator<E> iterator() { 
            return new Itr();
        }

下面看一下Itr类：  
Itr实现了Iterator接口，是ArrayList集合的迭代器对象

private class Itr implements Iterator<E> { 
    		//类似游标，指向迭代器下一个值的位置
            int cursor = 0;
             //迭代器最后一次取出的元素的位置
            int lastRet = -1;
         	//Itr初始化时候ArrayList的modCount的值。
            int expectedModCount = modCount;
    		//利用游标，与数组长度size的比较，判断迭代器是否还有下一个元素
            public boolean hasNext() { 
                return cursor != size();
            }
    		//迭代器获取下一个元素：
            public E next() { 
            	//检查modCount是否改变：
                checkForComodification();
                try { 
                    int i = cursor;
                    E next = get(i);
                    lastRet = i;
                    cursor = i + 1;
                    return next;
                } catch (IndexOutOfBoundsException e) { 
                    checkForComodification();
                    throw new NoSuchElementException();
                }
            }
    
            public void remove() { 
                if (lastRet < 0)
                    throw new IllegalStateException();
                 //检查modCount是否改变：防止并发操作集合 
                checkForComodification();
    
                try { 
    				 //删除这个元素： 
                    AbstractList.this.remove(lastRet);
                    if (lastRet < cursor)
                        cursor--;
                    lastRet = -1;
                    //重置expectedModCount：
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException e) { 
                    throw new ConcurrentModificationException();
                }
            }
    		//并发检查：
            final void checkForComodification() { 
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }

使用modCount变量其实是一种Fail-Fast机制，这种机制的详解见这篇博客：  
[java集合中常见异常fail-fast（面试常问）][java_fail-fast]

transient修饰符  
当我们序列化对象时，如果对象中某个属性不进行序列化操作，那么在该属性前添加transient修饰符即可实现；例如：

transient Object[] elementData;

为什么ArrayList不想对elementData属性进行序列化呢？elementData可是集合中保存元素的数组啊，如果不序列化elementData属性，那么在反序列化时候，岂不是丢失了原先的元素？

ArrayList在添加元素时，可能会对elementData数组进行扩容操作，而扩容后的数组可能并没有全部保存元素。

例如：我们创建了new Object\[10\]数组对象，但是我们只向其中添加了1个元素，而剩余的9个位置并没有添加元素。当我们进行序列化时，并不会只序列化其中一个元素，而是将整个数组进行序列化操作，那些没有被元素填充的位置也进行了序列化操作，间接的浪费了磁盘的空间，以及程序的性能。

所以，ArrayList才会在elementData属性前加上transient修饰符。

ArrayList的writeObject()、readObject()：  
ArrayList在序列化时会调用writeObject()，直接将elementData写入ObjectOutputStream；  
而反序列化时则调用readObject()，从ObjectInputStream获取elementData；

private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{ 
            int expectedModCount = modCount;
            s.defaultWriteObject();
            s.writeInt(size);
            for (int i=0; i<size; i++) { 
                s.writeObject(elementData[i]);
            }
            if (modCount != expectedModCount) { 
                throw new ConcurrentModificationException();
            }
        }
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException { 
            elementData = EMPTY_ELEMENTDATA;
            s.defaultReadObject();
            s.readInt(); 
            if (size > 0) { 
                int capacity = calculateCapacity(elementData, size);
                SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
                ensureCapacityInternal(size);
                Object[] a = elementData;
                for (int i=0; i<size; i++) { 
                    a[i] = s.readObject();
                }
            }
        }

Arrays.copyOf()  
该方法在内部创建了一个新数组，底层实现是调用System.arraycopy()；  
original - 要复制的数组  
newLength - 要返回的副本的长度  
newType - 要返回的副本的类型

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { 
            @SuppressWarnings("unchecked")
            T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }

System.arraycopy()  
该方法是用了native关键字，调用的为C++编写的底层函数.

/** *src - 源数组。 *srcPos - 源数组中的起始位置。 *dest - 目标数组。 *destPos - 目标数据中的起始位置。 *length - 要复制的数组元素的数量。 */
    public static native void arraycopy(Object src,  int  srcPos,
                                            Object dest, int destPos,
                                            int length);

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200212205154543.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ==,size_16,color_FFFFFF,t_70
[java_fail-fast]: https://baijiahao.baidu.com/s?id=1638201147057831295&wfr=spider&for=pc