Java面试汇总(一)

:2019年12月13日 本站(微博
分享到:

一、集合的大体架构图希望大家能牢牢记住下面这张框架图,一旦面试官让你“说说集合吧”,希望大家能立马给他画出来,边画边逐一介绍每个集合的特点,以及彼此的差异。重点是要从底层源代码的角度来给面...

一、集合的大体架构图

希望大家能牢牢记住下面这张框架图,一旦面试官让你“说说集合吧”,希望大家能立马给他画出来,边画边逐一介绍每个集合的特点,以及彼此的差异。重点是要从底层源代码的角度来给面试官分析。

一说到底层代码,可能很多人就头疼了,总认为知道和不知道对开发根本没多大实用价值,会应用就行了。这个观点,我暂不做评论。但是大家很庆幸的是,看到了本篇博客,博主将会带大家,来分析一些在面试中一定会用到的集合底层实现原理。

二、List

1.ArrayList和Vector的区别

第一句话:ArrayList和Vector底层都是数组实现的,初始容量都为10;ArrayList的底层,是通过定义一个DEFAULT_CAPACITY的常量来指定的,而Vector的底层,是直接在空参构造中,通过写死了一个this(10)来指定的;

   (PS:标色的部分,估计学过Java的人都会说,人云亦云,但是你要是在面试中,说出了后面标的部分,虽然意思一样,但是,你这样一讲,绝对瞬间提升了一个档次,立马就能够脱颖而出。后面的解析同理:色是众人皆知的常识,色字体才是精髓)

ArrayList源码片段:

    /**
     * Default initial capacity.默认初始容量
     */
private static final int DEFAULT_CAPACITY = 10;=

Vector源码片段:

   /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.空参构造,其内部数据数组的大小为10,并且它的标准容量增量为零
     */
    public Vector() {
        this(10);
    }

   第二句话:Vector大部分方法的底层实现,都加了 synchronized关键字,所以Vector是线程同步的,而 ArrayList不是

Vector源码片段:

   /**
     * Returns the number of components in this vector.
     */
    public synchronized int size() {
        return elementCount;
    }
    /**
     * Tests if this vector has no components.
     */
    public synchronized boolean isEmpty() {
        return elementCount == 0;
    }

第三句话:在查看API时,发现Vector有4个构造方法,比 ArrayList多了一个。而多的这个构造方法,是跟扩容有关的。ArrayList默认的扩容,在JDK1.6时,是按照新容量 =(原容量*3)/2+1来计算的,大约50%左右;而JDK1.7以后,是按照新容量 = 原容量 +(原容量 >> 1)来计算的,大约也在50%左右,所以都不是很多资料上说的就是50%,同时由于位运算的速度比快,所以ArrayList在JDK1.7之后效率更高,也可以看出来,;而在Vector中,默认情况下,是100%增长的,但是我们可以通过比ArrayList多的那个构造方法来指定它增容的大小

ArrayList源码片段:

    /**
     * jdk1.6中:int newCapacity = (oldCapacity * 3)/2 + 1;
     */
    public void ensureCapacity(int minCapacity) {
     modCount++;
     int oldCapacity = elementData.length;
     if (minCapacity >oldCapacity) {
         Object oldData[] = elementData;
         int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity <minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
     }
    }
    /**
     * jdk1.7之后:int newCapacity = oldCapacity + (oldCapacity >> 1);
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity =elementData.length;
        int newCapacity =oldCapacity + (oldCapacity >> 1);
        if (newCapacity -minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity -MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData,newCapacity);
    }


Vector源码片段:

    /**
     * Vector中int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
     */  
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity =elementData.length;
        int newCapacity =oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement :oldCapacity);
        if (newCapacity -minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity -MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData,newCapacity);
    }


2.ArrayList与LinkedList

第一句话ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构,它继承于AbstractSequentialList的双向链表,由于AbstractSequentialList 实现了get(i)、set()、add() 和 remove()这些骨干性函数,这也降低了List接口的复杂程度

LinkedList源码片段:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

第二句话ArrayList与LinkedList都是不是同步的。如果多个线程同时访问一个链接列表,而其中至少一个线程从结构上修改了该列表,则它必须保持外部同步。同步的方法就是使用Collections.synchronizedList(Collection<T> c)“包装”该列表。

static <T> Collection<T>  synchronizedCollection(Collection<T> c) 
返回指定 collection 支持的同步(线程安全的)

第三句话:对于随机访问get和set,ArrayList绝对优于LinkedList,因为从源码可以看出,ArrayList想要get(int index)元素时,直接返回index位置上的元素;而LinkedList需要通过for循环进行查找,虽然LinkedList已经在查找方法上做了优化,比如index < size / 2,则从左边开始查找,反之从右边开始查找,但是还是比ArrayList(随机查找)要慢。

ArrayList源码片段:

    public E get(int index) {
        rangeCheck(index); 
        checkForComodification();
        return ArrayList.this.elementData(offset +index); //直接返回索引
    }

LinkedList源码片段:

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item; //get()方法会调用node()方法,
}
//node()方法需要循环遍历查找索引;
    Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {  //加速机制
            Node<E> x = first;
            for (int i = 0;i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i =size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
}


第四句话从源码来看,ArrayList想要在指定位置插入或删除元素时,主要耗时的是System.arraycopy动作,会移动index后面所有的元素;LinkedList主耗时的是要先通过for循环找到index,然后直接插入或删除。这就导致了两者并非一定谁快谁慢!

具体情况,可参看如下测试数据(数据来源于网络):

#在index=1000出插入结果:
  array time:4
  linked time:240
  array insert time:20
  linked insert time:18
#在index=5000处插入结果: 
  array time:4
  linked time:229
  array insert time:13
  linked insert time:90
#在index=9000处插入结果:
  array time:4
  linked time:237
  array insert time:7
  linked insert time:92

    所以,不是很多资料中说得那样简单:以为ArrayList查询快,增删慢,因为它是集合实现的,要改角标;而LinkedList是链表实现的,所以查询慢,增删快!!
         结论:当插入的数据量很小时,两者区别不太大;当插入的数据量大时,大约在容量的1/10之前,LinkedList会优于ArrayList;在其后就完全劣于ArrayList,且越靠近后面越差。所以个人觉得,一般首选用ArrayList,因为LinkedList还可以实现栈、队列以及双端队列等数据结构。

文/  宋聪乔
关键词: 集合 大体 构图 希望 大家

来源:本文内容搜集或转自各大网络平台,并已注明来源、出处,如果转载侵犯您的版权或非授权发布,请联系小编,我们会及时审核处理。
声明:江苏教育黄页对文中观点保持中立,对所包含内容的准确性、可靠性或者完整性不提供任何明示或暗示的保证,不对文章观点负责,仅作分享之用,文章版权及插图属于原作者。

您在阅读:Java面试汇总(一)

Copyright©2013-2020 JSedu114 All Rights Reserved. 江苏教育信息综合发布查询平台保留所有权利

苏公网安备32010402000125苏ICP备14051488号-3南京思必达教育科技有限公司版权所有

技术支持:南京博盛蓝睿网络科技有限公司  

最热文章
最新文章
  • 卡尔蔡司镜片优惠店,镜片价格低
  • 苹果原装手机壳