List总结

王守钰 2020-03-09 16:03:24

List体系

image

ArrayList和LinkedList有什么区别?

ArrayList的底层结构是数组, LinkedList的底层结构是双向链表。

ArrayList是怎么扩容的?

当数组长度不够时进行扩容,每次加一半的空间。

private void grow(int minCapacity) {
    // overflow-conscious code
    // 数组长度
    int oldCapacity = elementData.length;
    // 容量大小 = 原数组长度 + 原数组长度的0.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量发现比需要的容量还小,则以需要的容量为准
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量发现比最大容量还大,则使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 拷贝出来原有的数据
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList插入、删除、查询元素的时间复杂度各是多少?

  • ArrayList支持随机访问,通过索引访问元素极快,时间复杂度为O(1);
  • ArrayList添加元素到尾部极快,平均时间复杂度为O(1);
  • ArrayList添加元素到中间比较慢,因为要搬移元素,平均时间复杂度为O(n);
  • ArrayList从尾部删除元素极快,时间复杂度为O(1);
  • ArrayList从中间删除元素比较慢,因为要搬移元素,平均时间复杂度为O(n);

怎么求两个集合的并集、交集、差集?

  • ArrayList支持求并集,调用addAll(Collection<? extends E> c)方法即可;
  • ArrayList支持求交集,调用retainAll(Collection<? extends E> c)方法即可;
  • ArrayList支持求单向差集,调用removeAll(Collection<? extends E> c)方法即可;

ArrayList是怎么实现序列化和反序列化的?

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // 防止序列化期间有修改
    int expectedModCount = modCount;
    // 写出非transient非static属性(会写出size属性)
    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;

    // 读入非transient非static属性(会读取size属性)
    s.defaultReadObject();

    // 读入元素个数,没什么用,只是因为写出的时候写了size属性,读的时候也要按顺序来读
    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();
        }
    }
}

查看writeObject()方法可知,先调用s.defaultWriteObject()方法,再把size写入到流中,再把元素一个一个的写入到流中。

一般地,只要实现了Serializable接口即可自动序列化,writeObject()和readObject()是为了自己控制序列化的方式,这两个方法必须声明为private,在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。

在ArrayList的writeObject()方法中先调用了s.defaultWriteObject()方法,这个方法是写入非static非transient的属性,在ArrayList中也就是size属性。同样地,在readObject()方法中先调用了s.defaultReadObject()方法解析出了size属性。

elementData定义为transient的优势,自己根据size序列化真实的元素,而不是根据数组的长度序列化元素,减少了空间占用。

集合的方法toArray()有什么问题?

返回的有可能不是Object[]类型。

public class ArrayTest {
    public static void main(String[] args) {
        Father[] fathers = new Son[]{};
        // 打印结果为class [Lcom.coolcoding.code.Son;
        System.out.println(fathers.getClass());

        List<String> strList = new MyList();
        // 打印结果为class [Ljava.lang.String;
        System.out.println(strList.toArray().getClass());
    }
}

class Father {}

class Son extends Father {}

class MyList extends ArrayList<String> {
    /**
     * 子类重写父类的方法,返回值可以不一样
     * 但这里只能用数组类型,换成Object就不行
     * 应该算是java本身的bug
     */
    @Override
    public String[] toArray() {
        // 为了方便举例直接写死
        return new String[]{"1", "2", "3"};
    }
}

什么是fail-fast?

fail-fast机制是java集合中的一种错误机制。

当使用迭代器迭代时,如果发现集合有修改,则快速失败做出响应,抛出ConcurrentModificationException异常。

这种修改有可能是其它线程的修改,也有可能是当前线程自己的修改导致的,比如迭代的过程中直接调用remove()删除元素等。

另外,并不是java中所有的集合都有fail-fast的机制。比如,像最终一致性的ConcurrentHashMap、CopyOnWriterArrayList等都是没有fast-fail的。

fail-fast是怎么实现的?

像ArrayList、HashMap中都有一个属性叫 modCount,每次对集合的修改这个值都会加1,在遍历前记录这个值到 expectedModCount中,遍历中检查两者是否一致,如果出现不一致就说明有修改,则抛出ConcurrentModificationException异常。

LinkedList是单链表还是双链表实现的?

双向链表

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList除了作为List还有什么用处?

双端队列、栈

LinkedList插入、删除、查询元素的时间复杂度各是多少?

  • LinkedList在队列首尾添加、删除元素非常高效,时间复杂度为O(1);
  • LinkedList在中间添加、删除元素比较低效,时间复杂度为O(n);
  • LinkedList获取第几个元素,依次遍历,复杂度O(n)

什么是随机访问?

java集合类中元素的访问分为随机访问和顺序访问。随机访问一般是通过index下标访问,行为类似数组的访问。而顺序访问类似于链表的访问,通常为迭代器遍历。以List接口及其实例为例。ArrayList是典型的随机访问型,而LinkedList则是顺序访问型。List接口既定义了下标访问方法又定义了迭代器方法。所以其实例既可使用下标随机访问也可以使用迭代器进行遍历。但这两种方式的性能差异很明显。

哪些集合支持随机访问?他们都有哪些共性?

ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。

CopyOnWriteArrayList是怎么保证并发安全的?

ReentrantLock, 以及 private transient volatile Object[] array 修饰元素。

CopyOnWriteArrayList的实现采用了什么思想?

写入时复制(CopyOnWrite,简称COW)思想是计算机程序设计领域中的一种优化策略。其核心思想是,如果有多个调用者(Callers)同时要求相同的资源(如内存或者是磁盘上的数据存储),他们会共同获取相同的指针指向相同的资源,直到某个调用者视图修改资源内容时,系统才会真正复制一份专用副本(private copy)给该调用者,而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的(transparently)。此做法主要的优点是如果调用者没有修改资源,就不会有副本(private copy)被创建,因此多个调用者只是读取操作时可以共享同一份资源。

CopyOnWriteArrayList是不是强一致性的?

不是,CopyOnWriteArrayList只保证最终一致性,不保证实时一致性,因为读写是在两个容器进行的,只有当写操作执行完毕引入指向新容器后,读才能感知到容器的变化。

CopyOnWriteArrayList适用于什么样的场景?

适用于读多写少的场景

CopyOnWriteArrayList插入、删除、查询元素的时间复杂度各是多少?

CopyOnWriteArrayList的写操作都要先拷贝一份新数组,在新数组中做修改,修改完了再用新数组替换老数组,所以空间复杂度是O(n),性能比较低下;

CopyOnWriteArrayList的读操作支持随机访问,时间复杂度为O(1);

删除也是空间复杂度是O(n)

CopyOnWriteArrayList为什么没有size属性?

因为每次修改都是拷贝一份正好可以存储目标个数元素的数组,所以不需要size属性了,数组的长度就是集合的大小,而不像ArrayList数组的长度实际是要大于集合的大小的。

比如,add(E e)操作,先拷贝一份n+1个元素的数组,再把新元素放到新数组的最后一位,这时新数组的长度为len+1了,也就是集合的size了。