JavaGuide知识点整理——集合常见知识点（上）

集合概述

Java集合概览

java集合，也叫作容器，主要由两大接口派生而来：

• Collection接口，主要用于存放单一元素。
  Collection接口下面有三个主要子接口：List,Set,Queue
• Map接口，用于存在键值对。

java集合框架图

这个图中只列举了主要的继承派生关系，并不是所有关系。很多工具类，抽象类都没列出来。

List,Set,Queue,Map四者的区别

• List:对付顺序的好帮手，存储的元素是有序的，可重复的
• Set:注重独一无二的性质，存储的元素是无序的，不可重复的
• Queue:实现排队功能的叫号器，按照特定的排队规则来确定先后顺序，存储到元素是有序的，可重复的
• Map:用key来搜索的专家，使用键值对存储，key是无序的，不可重复的，value是无序的，可重复的。每个键最多映射到一个值。

集合框架底层数据结构总结

• Collection:
  • List:
    • ArrayList:Object[] 数组
    • Vector:Object[] 数组
    • LinkedList:双向链表(JDK1.6之前为循环链表，1.7取消了循环)
  • Set:
    • HashSet(无序，唯一):基于HashMap实现的，元素是key，value设置为一个空对象。
    • KinkedHashSet:LinkedHashSet是HashSet的子类，并且内部是通过LinkedHashMap来实现的，有点类似于我们之前说的LinkedHashMap，其内部是基于HashMap实现一样，不过还是有一点点区别。
    • TreeSet(有序，唯一)：红黑树(自平衡的排序二叉树)
  • Queue：
    • PriorityQueue:Object[]数组来实现的二叉堆
    • ArrayQueue:Object[]数组+双指针
• Map:
  • HashMap:JDK1.8之前HashMap由数组+链表组成，数组是HashMap的主体，链表则主要是为了解决哈希冲突而存在的(拉链法解决冲突)。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认8)(将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转化为红黑树)时，将链表转化为红黑树，以减少搜索时间。
  • LinkedHashMap:LinkedJHashMap继承自HashMap,所以它的底层仍然是拉链式散列结构(数组+链表)或者红黑树组成。另外LinkedHashMap在上面结构的基础上增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
  • Hashtable:数组+链表组成的，数组是Hashtable的主体，链表则主要是为了解决哈希冲突存在的。
  • TreeMap：红黑树(自平衡的排序二叉树)

如何选用集合？

主要根据集合的特点来选用，比如我们需要根据键获取到元素值时就选择Map接口下的集合。需要排序时选择TreeMap，不需要排序时选择HashMap，需要保证线程安全就选用ConcurrentHashMap。
当我们只需要保存元素值时，就选择Collection接口的集合，需要保证元素唯一的时候选择实现Set，接口的集合比如TreeSet或者HashSet，不需要就选择实现List接口的比如ArrayList或者LinkedList。再根据这些接口的集合的特定来选用。

为什么要使用集合？

当我们保存一组类型相同的数据时，我们应该是用一个容器来保存。这个容器就是数组，但是使用数组存储对象具有一定的弊端。因为我们在实际开发中，存储的数据类型是多种多样的，于是就出现了‘集合’。集合同样也是用来存储多个数据的。
数组的缺点是一旦声明之后，长度就不可变了。同事声明数组时的数据类型也决定了该数组存储的数据的类型。而且数组存储的数据是有序的，可重复的，特点单一。
但是集合提高了数据存储的灵活性，java集合不仅可以用来存储不同类型，不同数量的对象，还可以保存具有映射关系的数据。

Collection子接口之List

ArrayList 和Vector的区别？

• ArrayList 是List的主要实现类。底层使用Object'[]存储，适用于频繁的查找工作，线程不安全。
• Vector是List的古老实现类，底层使用Object[]存储，线程安全的。

ArrayList与LinkedList的区别？

1. 是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全的。
2. 底层数据结构：ArrayList底层使用Object数组，LinkedList底层使用双向链表数据结构。
3. 插入和删除元素是否受元素位置的影响：
   • ArrayList采用数组存储。所以插入和删除元素的时间复杂度受元素位置的影响。比如执行add(E e)方法的时候，ArrayList会默认在指定的元素追加到此列表的末尾。这种情况的时间复杂度就是O(1).但是如果指定位置插入和删除元素的话add(int index , E e)时间复杂度就会为O(n-i)。因为在进行上述操作的时候集合中第i个元素之后的(n-i)个元素都要执行向后/向前移动一位的操作。
   • LinkedList采用链表存储，所以如果是在头尾插入或者删除元素不受元素位置的影响。add(E e),addFirst(E e),addLast(E e),removeFirst(),removeLast() 这些操作时间复杂度都为O(1).如果是要在指定位置i插入和删除元素的话，时间复杂度是O(n),因为需要先移动到指定位置再插入。
4. 是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持。快速访问就是通过元素的序号快速获取元素对象(对应get(int index)方法)
   5.内存空间占用：ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间。而LinkedList的空间花费则主要体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为链表结构要存放前面和后面数据)

我们在项目中一般不会用到LinkedList的，需要用到LinkedList的场景几乎都可以使用ArrayList代替，并且性能通常会更好。

ArrayList的扩容机制

ArrayList的底层是数组队列。相当于动态数组。与java中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量。这可以减少递增式再分配的数量。
ArrayList继承与AbstractList，实现了List,RandomAccess,Cloneable,Serializable这些接口。

• RandomAccess是一个标志性接口，标明实现了这个接口的集合是支持快速随机访问的，在ArrayList中，我们可以通过下标快速获取元素对象，这就是快速随机访问(LinkedList不支持快速随机访问)。
• Cloneable是实现了这个接口的类可以调用clone()方法，不然虽然都继承自Object，有这个方法，但是调用会报错。
• Serializable实现了这个接口的类支持序列化，能通过序列化传输。

说到ArrayList的扩容机制，可以先从构造函数说起(源码采用JDK8版本)：
ArrayList有三种方式来初始化，构造方法源码如图：

ArrayList三种构造函数

以无参数构造方法创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10.下面我们一起走一下第一个add的源码走向：

ArrayList的add方法

如上图，add的时候会调用一个ensureCapacityInternal方法，点进去会发现这个方法调用的是ensureExplicitCapacity这个方法：

ensureCapacityInternal方法

注意这里传了个参数，而计算参数的方法是这样的：

默认值10

也就是这个方法最后返回的是10.而调用这个ensureExplicitCapacity方法参数传10的话，

调用grow方法

grow方法其实就是我们说的扩容方法：

grow扩容方法

其实代码逻辑挺清晰的，就是newCapacity是oldCapacity + (oldCapacity >> 1)。这里>>1是位运算除2的意思。如果奇数会直接舍去。这也就告诉我们ArrayList的扩容每次都是之前的1.5倍左右(因为会出现舍弃小数的情况，所以是1.5倍左右)。
同理我们继续其实就可以推测了，当加到2,3,4,等元素的时候其实minCapacity 应该是size+1,也就是元素数。而数组的长度是默认是10，所以这里判断不成立不会调用grow方法，也就不会扩容。
而等到第11个元素的时候，判断成立，也就是继续扩容成长度15.....ArrayList的扩容机制大概就是这么实现的，其实源码写的很简单，而且逻辑清晰。

Collection子接口之Set

comparable 和 Comparator的区别

• comparable接口实际上是出自java.lang包，它有一个compareTo(Object obj)方法用来排序。
• comparator接口实际上是出自java.util包，它有一个compare(Object o1,Object o2)方法用来排序

一般我们需要对一个集合使用自定义排序时，我们就重写compareTo()方法或者compare()方法，当我们需要对某一个集合实现两种排序方式，比如song对象中的歌名和歌手名分别采用一种排序方法的话，可以重写compareTo()方法。

无序性和不可重复性的含义是什么？

1. 什么是无序性？无序性不等于随机性。无序性是指存储的数组在底层数据中并非是按照数组索引的顺序添加的，而是根据数据的哈希值决定的。
2. 什么是不可重复性？不可重复性是指添加元素按照equals()判断时，如果已经存在不可添加，返回false。

比较HashSet,LinkedHashSet和TreeSet三者的异同

• HashSet,LinkedHashSet 和TreeSet都是set接口的实现类，都能保证元素唯一，且都不是线程安全的。
• HashSet,LinkedHashSet 和TreeSet的主要区别在于底层数组结构不同。Hashset的底层数据结构是哈希表(基于HashMap实现)，LinkedHashMap的底层数据结构是链表+哈希表，元素的插入和取出顺序满足先入先出。TreeSet的底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
• 底层数据结构不同又导致这三者的应用场景不同。HashSet用于不需要保证元素插入和取出顺序的场景，LinkedHashSet用于保证元素的插入和取出满足先入先出的场景，TreeSet用于支持对元素自定义排序规则的场景。

Collection子接口之Queue

Queue与Deque的区别

Queue是单端队列，只能从一端插入，另一端删除。实现上一般遵循先进先出(FIFO)规则。
Queue扩展了Collection的接口，因为容量问题而导致操作失败后处理方式的不同可以分为两类方法：一种是操作失败直接抛出异常，一种是返回特殊值。

Queue的两类方法

Deque是双端队列，在队列两端都可以插入或者删除元素
Deque扩展了Queue接口，增加了队首和队尾都可以插入和删除的方法。同样根据失败后处理方式不同分为两类：

Deque方法

事实上，Deque还有push，pop等方法可以用于模拟栈。

ArrayDeque与LinkedList的区别

ArrayDeque和LinkedList都实现了Deque接口，两者都有队列的功能。但是两者还是有一些区别：

• ArrayDeque是基于可变长的数组和双指针来实现的，LinkedList是通过链表来实现的。
• ArrayDeque不支持存储null数据，而LinkedList支持。
• ArrayDeque是在JDK1.6才被引入的，而LinkedList在JDK1.2就存在了。
• ArrayDeque插入时可能存在扩容过程，不过均摊后插入操作依然是O(1),虽然LinkedList不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊后性能相比更慢。

说一说PriorityQueue

PriorityQueue是在JDK1.5中被引入的，其与Queue的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
还有一些其他的要点：

• PriorityQueue利用了二叉堆的数据结构来实现，底层使用可变长的数组来存储数据。
• PriorityQueue通过堆元素的上浮和下沉，实现了在O(logN)的时间复杂度内插入元素和删除堆顶元素。
• PriorityQueue是非线程安全的，且不支持存储null和non-comparable的对象。
• PriorityQueue默认是小顶堆，但是可以接收一个Comparator作为构造参数，从而自定义元素优先级的先后。

PriorityQueue在面试中一般会出现在手撕算法的时候，典型例题包括堆排序，第K大的数，带权图的遍历等。