Java面试总结（1）

2018-04-21

Java面试总结（1）

1. ArrayList、LinkedList、Vector的异同及源码分析

三者都实现了List接口，下面对他们各自的特点进行总结。

• ArrayList

  • 基本构造：

  public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable

  List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组和大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

  通过改变实例中容量来实现数组大小的可变，在添加大量元素前，应用程序需要ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

  • 数据结构

    private static final long serialVersionUID = 8683452581122892189L;  
            
    private static final int DEFAULT_CAPACITY = 10;  
              
    private static final Object[] EMPTY_ELEMENTDATA = new Object[0];  
            
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];  
            
    transient Object[] elementData;  
            
    private int size;  
            
    private static final int MAX_ARRAY_SIZE = 2147483639;
    

  • 常用函数

    • add()：首先确保数组长度，如果不够，则grow()扩大1.5倍，然后再指定位置添加元素
    • add(int index,E element)：首先确保数组长度，如果不够，则grow()扩大1.5倍，将index后面的元素向后移一位，最后再指定位置添加元素
    • get(int index)：首先检查index，获取指定位置元素
    • set(int index,E element)：首先检查index，然后修改指定位置元素，返回旧元素
    • contains()：调用indexOf()方法实现；需遍历数组；
    • remove()：首先判断index范围，将指定位置（index）上的元素保存到oldValue，将指定位置（index）上的元素都往前移动一位，将最后面的一个元素置空，好让垃圾回收器回收；
    • remove(E element)：需遍历数组

• LinkedList

  • 基本构造：

  public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable

  List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

  此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。

  此实现不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程从结构上修改了该列表，则它必须 保持外部同步。

  • 数据结构：

    transient int size = 0;
    
    transient Node<E> first;
    
    transient Node<E> last;
    
    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;
        }
    }
    

  • 常用函数：

    • add()：用linkLast()实现，在链表结尾加新元素
    • Deque接口操作：addFirst(E e)，addLast(E e)，offer(E e)，offerFirst(E e)

• Vector

  • 基本构造：

  public class Vector extends AbstractList implements List, RandomAccess, Cloneable, Serializable

  Vector 类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作。

  每个Vector会试图通过维护 capacity 和 capacityIncrement 来优化存储管理。capacity 始终至少应与向量的大小相等；Vector 是同步的。

  ​

• 三者区别

  • ArrayList 本质上是一个可改变大小的数组.当元素加入时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问.元素顺序存储 ,随机访问很快，删除非头尾元素慢，新增元素慢且费资源 ,较适用于无频繁增删的情况 ,比数组效率低，如果不是需要可变数组，可考虑使用数组 ,非线程安全.
  • LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList. 适用于 ：没有大规模的随机读取，大量的增加/删除操作.随机访问很慢，增删操作很快，不耗费多余资源 ,允许null元素,非线程安全.
  • Vector （类似于ArrayList）但其是同步的，开销就比ArrayList要大。如果你的程序本身是线程安全的，那么使用ArrayList是更好的选择。 Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间，而ArrayList每次对size增长50%.

• ConcurrentModificationException异常

  • 当循环中对ArrayList或HashSet中内容进行删除时会报ConcurrentModificationException异常
  • 其原因是因为在源码中的checkForComodification()方法检测出了异常，其中expectedModCount和modCount的值不相同。当调用容器本身的remove()方法时，使用的是fastRemove()方法，会对modCount加1，然后删除元素，此时就会报出上面的异常了。
  • 单线程解决方法：因为我的程序是一个单线程程序，所以解决方法也比较简单，只需要iterator类的remove方法，这个方法中在删除元素时会保证expectedModCount 和 modCount相同，因此就解决了这个问题
  • 然后，我在网上还看到了多线程程序也会出现这个问题：虽然Vector的方法采用了synchronized进行了同步，但是实际上通过Iterator访问的情况下，每个线程里面返回的是不同的iterator，也即是说expectedModCount是每个线程私有。假若此时有2个线程，线程1在进行遍历，线程2在进行修改，那么很有可能导致线程2修改后导致Vector中的modCount自增了，线程2的expectedModCount也自增了，但是线程1的expectedModCount没有自增，此时线程1遍历时就会出现expectedModCount不等于modCount的情况了。
  • 多线程解决方法：1）在使用iterator迭代的时候使用synchronized或者Lock进行同步；2）使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。

2. HashMap源码分析

• 简单介绍：
  • Hashmap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。它的key、value都可以为null，映射不是有序的。Hashmap不是同步的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。