Java集合面试(上)

Java集合面试(上)

集合概述

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对

说说List，Set,Queue，Map的区别

• List:存储的元素是有序的，可重复
• Set:存的元素不可重复
• Queue:按照特定的规则排序，可重复
• Map:存键值对，key和value无序，key不可重复

集合框架底层数据结构

List

• ArrayList:Object[] 数组
• Vector：Object[] 数组。
• LinkedList：双向链表

Set

• HashSet:基于 HashMap 实现的
• LinkedHashSet:LinkedHashMap 来实现的
• TreeSet：红黑树

queue

• PriorityQueue: Object[] 数组来实现小顶堆
• DelayQueue:PriorityQueue
• ArrayDeque: 可扩容动态双向数组。

Map

• LinkedHashMap:基于拉链式散列结构即由数组和链表或红黑树组成
• Hashtable：数组+链表组成的
• TreeMap：红黑树
• HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

怎么选用集合

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

为什么要使用集合

Java 集合的优势在于它们的大小可变、支持泛型、具有内建算法等

List

ArrayList和Array(数组)的区别

• 集合可以进行动态扩容或者缩容，数组被创建就不能改变了
• 集合可以用泛型来保证类型安全，数组不行
• 集合只能存对象，基本类型只能存对应包装类，数组可以存对象和基本数据类型
• 集合支持插入删除遍历等操作，还有很多api但是数组只能通过下标访问元素，不具备动态添加删除元素的能力
• 集合创建不需要指定大小，而数组需要

ArrayList可以添加null值吗

ArrayList 中可以存储任何类型的对象，包括 null 值

ArrayList插入和删除元素的时间复杂度?

插入:

• 头部插入O(n),因为所有元素向后移动一个位置
• 尾部插入:没到容量时是O(1),到了是O(n)，执行一次O(n)操作复制到新数组，在执行O(1)
• 指定位置插入:需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置O(n)

删除:

• 头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。
• 尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。
• 指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

LinkedList为什么不能实现RandomAccess接口?

RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）但是它底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问

ArrayList和LinkedList的区别

• 都不保证线程安全
• 数据结构:一个数组一个双向链表
• 插入和删除受元素位置影响
• 是否支持快速随机访问:ArrayList支持
• 内存空间占用:ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

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

ArrayList扩容机制

Set

Comparable 接口和 Comparator区别

• Comparable 接口用于定义对象自身的比较逻辑。当一个类实现了 Comparable 接口，它就表明该类的对象能够自然地相互比较，并且这种比较是基于对象本身的属性
• Comparator 接口用于定义外部比较逻辑，即一个类的对象可以通过外部比较器来决定排序顺序。这使得即使是在不修改对象自身的情况下，也可以根据不同的标准对对象进行排序。

无序性和不可重复性

• 无序性:不是随机性，只是没有按照数组索引顺序去添加，而是根据哈希值决定
• 不可重复性:就是equals返回false

HashSet和LinkedHasSet和TreeSet的区别?

• 三者线程不安全
• 底层数据结构不同
• 应用场景不同。HashSet用在不用保证顺序的场景，LinkedHashSet(链表哈希表)保证了FIFO(先进先出)，TreeSet用于自定义顺序

Queue

Queue和Deque的区别

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

ArrayDeque和LinkedList的区别

两者都实现了Deque接口，具有队列的功能

• 底层结构:ArrayDeque是可变长数组加双指针，另外一个是链表

• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。

• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。

• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：

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

什么是BlockingQueue

BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

BlockingQueue 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。

ArrayBlockingQueue和LinkedBlockingQueue区别

• 底层实现：ArrayBlockingQueue 基于数组实现，而 LinkedBlockingQueue 基于链表实现

• 是否有界：ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。

• 锁是否分离： ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。

• 内存占用：ArrayBlockingQueue 需要提前分配数组内存，而 LinkedBlockingQueue 则是动态分配链表节点内存。这意味着，ArrayBlockingQueue 在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间