首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >JAVA面试50讲之5:Vector,ArrayList,LinkedList的区别

JAVA面试50讲之5:Vector,ArrayList,LinkedList的区别

作者头像
用户1205080
发布2019-01-02 14:41:19
1.8K0
发布2019-01-02 14:41:19
举报
文章被收录于专栏:编码前线编码前线

1. Java集合类基本概念

Java容器类类库的用途是”保存对象”,并将其划分为两个不同的概念:

1) Collection

一组”对立”的元素,通常这些元素都服从某种规则   1.1) List必须保持元素特定的顺序   1.2) Set不能有重复元素   1.3) Queue保持一个队列(先进先出)的顺序

2) Map

一组成对的”键值对”对象 Collection和Map的区别在于容器中每个位置保存的元素个数:

  • Collection 每个位置只能保存一个元素(对象)
  • Map保存的是”键值对”,就像一个小型数据库。我们可以通过”键”找到该键对应的”值”

2. Java集合类架构层次关系

1. Interface Iterable迭代器接口,这是Collection类的父接口。实现这个Iterable接口的对象允许使用foreach进行遍历,也就是说,所有的Collection集合对象都具有"foreach可遍历性"。这个Iterable接口只有一个方法: iterator()。它返回一个代表当前集合对象的泛型<T>迭代器,用于之后的遍历操作1.1 CollectionCollection是最基本的集合接口,一个Collection代表一组Object的集合,这些Object被称作Collection的元素。Collection是一个接口,用以提供规范定义,不能被实例化使用
    1) Set
    Set集合类似于一个罐子,"丢进"Set集合里的多个对象之间没有明显的顺序。Set继承自Collection接口,不能包含有重复元素(记住,这是整个Set类层次的共有属性)。
    Set判断两个对象相同不是使用"=="运算符,而是根据equals方法。也就是说,我们在加入一个新元素的时候,如果这个新元素对象和Set中已有对象进行注意equals比较都返回false,  
   则Set就会接受这个新元素对象,否则拒绝。
    因为Set的这个制约,在使用Set集合的时候,应该注意两点:1) 为Set集合里的元素的实现类实现一个有效的equals(Object)方法、2) 对Set的构造函数,传入的Collection参数不能包
  含重复的元素
        1.1) HashSet
        HashSet是Set接口的典型实现,HashSet使用HASH算法来存储集合中的元素,因此具有良好的存取和查找性能。当向HashSet集合中存入一个元素时,HashSet会调用该对象的
     hashCode()方法来得到该对象的hashCode值,然后根据该HashCode值决定该对象在HashSet中的存储位置。
        值得主要的是,HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等,并且两个对象的hashCode()方法的返回值相等
            1.1.1) LinkedHashSet
            LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置,但和HashSet不同的是,它同时使用链表维护元素的次序,这样使得元素看起来是以插入的顺序保存的。
       当遍历LinkedHashSet集合里的元素时,LinkedHashSet将会按元素的添加顺序来访问集合里的元素。
            LinkedHashSet需要维护元素的插入顺序,因此性能略低于HashSet的性能,但在迭代访问Set里的全部元素时(遍历)将有很好的性能(链表很适合进行遍历)
        1.2) SortedSet    
        此接口主要用于排序操作,即实现此接口的子类都属于排序的子类
            1.2.1) TreeSet
            TreeSet是SortedSet接口的实现类,TreeSet可以确保集合元素处于排序状态
        1.3) EnumSet
        EnumSet是一个专门为枚举类设计的集合类,EnumSet中所有元素都必须是指定枚举类型的枚举值,该枚举类型在创建EnumSet时显式、或隐式地指定。EnumSet的集合元素也是有序的,
     它们以枚举值在Enum类内的定义顺序来决定集合元素的顺序
    2) List
    List集合代表一个元素有序、可重复的集合,集合中每个元素都有其对应的顺序索引。List集合允许加入重复元素,因为它可以通过索引来访问指定位置的集合元素。List集合默认按元素
   的添加顺序设置元素的索引
        2.1) ArrayList
        ArrayList是基于数组实现的List类,它封装了一个动态的增长的、允许再分配的Object[]数组。
        2.2) Vector
        Vector和ArrayList在用法上几乎完全相同,但由于Vector是一个古老的集合,所以Vector提供了一些方法名很长的方法,但随着JDK1.2以后,java提供了系统的集合框架,就将
     Vector改为实现List接口,统一归入集合框架体系中
            2.2.1) Stack
            Stack是Vector提供的一个子类,用于模拟"栈"这种数据结构(LIFO后进先出)
        2.3) LinkedList
        implements List<E>, Deque<E>。实现List接口,能对它进行队列操作,即可以根据索引来随机访问集合中的元素。同时它还实现Deque接口,即能将LinkedList当作双端队列
     使用。自然也可以被当作"栈来使用"
    3) Queue
    Queue用于模拟"队列"这种数据结构(先进先出 FIFO)。队列的头部保存着队列中存放时间最长的元素,队列的尾部保存着队列中存放时间最短的元素。新元素插入(offer)到队列的尾部,
   访问元素(poll)操作会返回队列头部的元素,队列不允许随机访问队列中的元素。结合生活中常见的排队就会很好理解这个概念
        3.1) PriorityQueue
        PriorityQueue并不是一个比较标准的队列实现,PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序,而是按照队列元素的大小进行重新排序,这点从它的类名也可以
     看出来
        3.2) Deque
        Deque接口代表一个"双端队列",双端队列可以同时从两端来添加、删除元素,因此Deque的实现类既可以当成队列使用、也可以当成栈使用
            3.2.1) ArrayDeque
            是一个基于数组的双端队列,和ArrayList类似,它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素,当集合元素超出该数组的容量时,系统会在底层重
       新分配一个Object[]数组来存储集合元素
            3.2.2) LinkedList1.2 MapMap用于保存具有"映射关系"的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另外一组值用于保存Map里的value。key和value都可以是任何引用类型的数据。Map的key不允许重复,即同一个Map对象的任何两个key通过equals方法比较结果总是返回false。关于Map,我们要从代码复用的角度去理解,java是先实现了Map,然后通过包装了一个所有value都为null的Map就实现了Set集合Map的这些实现类和子接口中key集的存储形式和Set集合完全相同(即key不能重复)Map的这些实现类和子接口中value集的存储形式和List非常类似(即value可以重复、根据索引来查找)
    1) HashMap
    和HashSet集合不能保证元素的顺序一样,HashMap也不能保证key-value对的顺序。并且类似于HashSet判断两个key是否相等的标准也是: 两个key通过equals()方法比较返回true、
   同时两个key的hashCode值也必须相等
        1.1) LinkedHashMap
        LinkedHashMap也使用双向链表来维护key-value对的次序,该链表负责维护Map的迭代顺序,与key-value对的插入顺序一致(注意和TreeMap对所有的key-value进行排序进行区分)
    2) Hashtable
    是一个古老的Map实现类
        2.1) Properties 
        Properties对象在处理属性文件时特别方便(windows平台上的.ini文件),Properties类可以把Map对象和属性文件关联起来,从而可以把Map对象中的key-value对写入到属性文
     件中,也可以把属性文件中的"属性名-属性值"加载到Map对象中
    3) SortedMap
    正如Set接口派生出SortedSet子接口,SortedSet接口有一个TreeSet实现类一样,Map接口也派生出一个SortedMap子接口,SortedMap接口也有一个TreeMap实现类
        3.1) TreeMap
        TreeMap就是一个红黑树数据结构,每个key-value对即作为红黑树的一个节点。TreeMap存储key-value对(节点)时,需要根据key对节点进行排序。TreeMap可以保证所有的
     key-value对处于有序状态。同样,TreeMap也有两种排序方式: 自然排序、定制排序
    4) WeakHashMap
    WeakHashMap与HashMap的用法基本相似。区别在于,HashMap的key保留了对实际对象的"强引用",这意味着只要该HashMap对象不被销毁,该HashMap所引用的对象就不会被垃圾回收。
  但WeakHashMap的key只保留了对实际对象的弱引用,这意味着如果WeakHashMap对象的key所引用的对象没有被其他强引用变量所引用,则这些key所引用的对象可能被垃圾回收,当垃
  圾回收了该key所对应的实际对象之后,WeakHashMap也可能自动删除这些key所对应的key-value对
    5) IdentityHashMap
    IdentityHashMap的实现机制与HashMap基本相似,在IdentityHashMap中,当且仅当两个key严格相等(key1 == key2)时,IdentityHashMap才认为两个key相等
    6) EnumMap
    EnumMap是一个与枚举类一起使用的Map实现,EnumMap中的所有key都必须是单个枚举类的枚举值。创建EnumMap时必须显式或隐式指定它对应的枚举类。EnumMap根据key的自然顺序
  (即枚举值在枚举类中的定义顺序)

3.Vector,ArrayList,LinkedList的特点和区别

3.1.Vector简介及特点

  • 1、Vector是内部是以动态数组的形式来存储数据的。
  • 2、Vector具有数组所具有的特性、通过索引支持随机访问、所以通过随机访问Vector中的元素效率非常高、但是执行插入、删除时效率比较地下、具体原因后面有分析。
  • 3、Vector实现了AbstractList抽象类、List接口、所以其更具有了AbstractList和List的功能、前面我们知道AbstractList内部已经实现了获取Iterator和ListIterator的方法、所以Vector只需关心对数组操作的方法的实现、
  • 4、Vector实现了RandomAccess接口、此接口只有声明、没有方法体、表示Vector支持随机访问。
  • 5、Vector实现了Cloneable接口、此接口只有声明、没有方法体、表示Vector支持克隆。
  • 6、Vector实现了Serializable接口、此接口只有声明、没有方法体、表示Vector支持序列化、即可以将Vector以流的形式通过ObjectOutputStream来写入到流中。
  • 7、Vector是线程安全的。

3.2.ArrayList的特点

  • 1、容量不固定,想放多少放多少(当然有最大阈值,但一般达不到)
  • 2、有序的(元素输出顺序与输入顺序一致)
  • 3、非线程安全
  • 4、插入元素的时候可能扩容,删除元素时不会缩小容量,不使用索引的元素查找需要遍历数组,并使用equals比较。 3.2.1增加详解: 1、因为是数组实现,ArrayList的代价会大一些,而且会考虑是否需要扩容,首先在原有元素个数上加一为minCapacity,用这个值和Ooject数组大小进行比较(容量),如果这个值大,那么就需要扩容了,将数组的size*1.5+1,如果此时还是minCapacity的话,那么新容量就用minCapacity来表示,然后就是生成新的容量的数组,原来的元素赋值进去即可,如果想更改扩容策略,继承ArrayList,重写ensureCapacity方法即可。2、add(E)把新添加的元素放到数组的末尾,只需要使用常数的时间。3、add(int,E)在数组指定位置添加元素,首先确定数组这个位置是否存在和容量是否允许,然后将指定位置后面的所有元素全部向后面移动一个位置,最后才将元素插入进指定位置,使用O(n)的时间代价。 3.2.2删除详解: 删除分两种删除,删除对象和按位置删除。 1. 删除对象(空,和非空,但都需要遍历) 1.1、如果删除的对象为空(null),首先遍历数组元素是否有为空,若有,将使用fastRemove方法删除,具体做法是,将此位置后面的元素全部向前移动一位,最后的那个留空,并可以gc回收了。1.2、如果不为空,使用equals方法进行比较,找到了相应的元素后,同样进行faseRemove方法进行删除。 2.按位置删除 1.remove(int)删除指定位置的元素,这是数组的优势,大大提升了性能,仅仅只需要判断index是否越界,剩下的就是直接删除了,不需要遍历。但是该元素后的元素同样需要全部向前移动一位。 3.2.3获取单个对象: get(int),首先判断是否越界,然后就是直接返回元素了,这也是数组的优势。 3.2.4遍历: 常用的迭代器设计模式,iterator方法返回一个父类实现的迭代器。 1、迭代器的hasNext方法的作用是判断当前位置是否是数组最后一个位置,相等为false,否则为true。2、迭代器next方法用于返回当前的元素,并把指针指向下一个元素,值得注意的是,每次使用next方法的时候,都会判断创建迭代器获取的这个容器的计数器modCount是否与此时的不相等,不相等说明集合的大小被修改过,如果是会抛出ConcurrentModificationException异常,如果相等调用get方法返回元素即可。 3.2.5判断元素是否存在: 1、首先判断条件元素是否为空,是则遍历集合,有就返回true,否则false。2、不为空,则使用equals方法,需要遍历集合。关于ArrayList源码详解,可参考ArrayList 3.3.LinkedList的特点 是一个双链表,在add和remove时比ArrayList性能好,但get和set时就特别慢了。 恶补下: 双向链表,链表的一种。每个数据结点中都有两个指针,分别指向直接前驱和直接后继。因此,我们可以方便的访问他的前驱结点和后继结点。 3.3.1、链表简介: 链表是常用的一种数据结构、关于链表这里只给出简单介绍、只是基础的概念。 1、概念: 如果一个节点包含指向另一个节点的数据值,那么多个节点可以连接成一串,只通过一个变量访问整个节点序列,这样的节点序列称为链表(linked list) 2、单向链表: 如果每个节点仅包含其指向后继节点的引用,这样的链表称为单向链表。 3、双向链表: 每个链表节点,包含两个引用,一个指向前驱节点,一个指向后驱节点,也就是——双向链表。 3.3.2、LinkedList的特点: 1、LinkedList以链表的形式存储数据、对增删元素有很高的效率、查询效率较低、尤其是随机访问、效率不忍直视、 2、LinkedList继承AbstractSequentialdList(其继承与AbstractList、所以要求其子类要实现通过索引操作元素)、使得LinkedList支持使用索引的“增删改查”操作、 3、LinkedList直接实现了List接口、使其可以内部存储元素有序并且为每个元素提供索引值、 4、LinkedList直接实现了Deque接口、Deque接口继承了Queue、使其可以作为双向链表这种数据结构来使用、操作元素、 5、LinkedList直接实现了Cloneable接口、使其可以复制其中的全部元素 6、在使用ObjectOutputStream/ObjectInputStream流时、会先讲LinkedList的capacity读取/写入到流中、然后将元素一一读取/写入。 7、LinkedList非线程安全
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-12-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 编码前线 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. Java集合类基本概念
    • 1) Collection
      • 2) Map
      • 2. Java集合类架构层次关系
      • 3.Vector,ArrayList,LinkedList的特点和区别
        • 3.1.Vector简介及特点
          • 3.2.ArrayList的特点
          相关产品与服务
          容器服务
          腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档