关于java:Java-集合常见知识点面试题总结上2022-最新版

你好，我是 Guide。秋招行将到来（提前批曾经开始），我对 JavaGuide 的内容进行了重构欠缺，公众号同步一下最新更新，心愿可能帮忙你。

你也能够在网站 (javaguide.cn) 上在线浏览，浏览体验会更好！

前 3 篇：

Java 根底常见知识点 & 面试题总结(上)，2022 最新版！
Java 根底常见知识点 & 面试题总结(中)，2022 最新版
Java 根底常见知识点 & 面试题总结(下)，2022 最新版！

Java 汇合，也叫作容器，次要是由两大接口派生而来：一个是 Collection接口，次要用于寄存繁多元素；另一个是 Map 接口，次要用于寄存键值对。对于Collection 接口，上面又有三个次要的子接口：List、Set 和 Queue。

Java 汇合框架如下图所示：

注：图中只列举了次要的继承派生关系，并没有列举所有关系。比如省略了 AbstractList, NavigableSet 等抽象类以及其余的一些辅助类，如想深刻理解，可自行查看源码。

List(凑合程序的好帮手): 存储的元素是有序的、可反复的。
Set(重视举世无双的性质): 存储的元素是无序的、不可反复的。
Queue(实现排队性能的叫号机): 按特定的排队规定来确定先后顺序，存储的元素是有序的、可反复的。
Map(用 key 来搜寻的专家): 应用键值对（key-value）存储，相似于数学上的函数 y=f(x)，”x” 代表 key，”y” 代表 value，key 是无序的、不可反复的，value 是无序的、可反复的，每个键最多映射到一个值。

先来看一下 Collection 接口上面的汇合。

Arraylist：Object[] 数组
Vector：Object[] 数组
LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 勾销了循环)

HashSet(无序，惟一): 基于 HashMap 实现的，底层采纳 HashMap 来保留元素
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其外部是通过 LinkedHashMap 来实现的。有点相似于咱们之前说的 LinkedHashMap 其外部是基于 HashMap 实现一样，不过还是有一点点区别的
TreeSet(有序，惟一): 红黑树(自均衡的排序二叉树)

PriorityQueue: Object[] 数组来实现二叉堆
ArrayQueue: Object[] 数组 + 双指针

再来看看 Map 接口上面的汇合。

HashMap：JDK1.8 之前 HashMap 由数组 + 链表组成的，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的（“拉链法”解决抵触）。JDK1.8 当前在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果以后数组的长度小于 64，那么会抉择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以缩小搜寻工夫
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层依然是基于拉链式散列构造即由数组和链表或红黑树组成。另外，LinkedHashMap 在下面构造的根底上，减少了一条双向链表，使得下面的构造能够放弃键值对的插入程序。同时通过对链表进行相应的操作，实现了拜访程序相干逻辑。具体能够查看：《LinkedHashMap 源码详细分析（JDK1.8）》
Hashtable：数组 + 链表组成的，数组是 Hashtable 的主体，链表则是次要为了解决哈希抵触而存在的
TreeMap：红黑树（自均衡的排序二叉树）

次要依据汇合的特点来选用，比方咱们须要依据键值获取到元素值时就选用 Map 接口下的汇合，须要排序时抉择 TreeMap, 不须要排序时就抉择 HashMap, 须要保障线程平安就选用 ConcurrentHashMap。

当咱们只须要寄存元素值时，就抉择实现Collection 接口的汇合，须要保障元素惟一时抉择实现 Set 接口的汇合比方 TreeSet 或 HashSet，不须要就抉择实现 List 接口的比方 ArrayList 或 LinkedList，而后再依据实现这些接口的汇合的特点来选用。

当咱们须要保留一组类型雷同的数据的时候，咱们应该是用一个容器来保留，这个容器就是数组，然而，应用数组存储对象具备肯定的弊病，
因为咱们在理论开发中，存储的数据的类型是多种多样的，于是，就呈现了“汇合”，汇合同样也是用来存储多个数据的。

数组的毛病是一旦申明之后，长度就不可变了；同时，申明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可反复的，特点繁多。
然而汇合进步了数据存储的灵活性，Java 汇合不仅能够用来存储不同类型不同数量的对象，还能够保留具备映射关系的数据。

ArrayList 是 List 的次要实现类，底层应用 Object[]存储，实用于频繁的查找工作，线程不平安；
Vector 是 List 的古老实现类，底层应用Object[] 存储，线程平安的。

是否保障线程平安： ArrayList 和 LinkedList 都是不同步的，也就是不保障线程平安；
底层数据结构： Arraylist 底层应用的是 Object 数组 ；LinkedList 底层应用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 勾销了循环。留神双向链表和双向循环链表的区别，上面有介绍到！）
插入和删除是否受元素地位的影响：
- ArrayList 采纳数组存储，所以插入和删除元素的工夫复杂度受元素地位的影响。比方：执行 add(E e) 办法的时候，ArrayList 会默认在将指定的元素追加到此列表的开端，这种状况工夫复杂度就是 O(1)。然而如果要在指定地位 i 插入和删除元素的话（add(int index, E element)）工夫复杂度就为 O(n-i)。因为在进行上述操作的时候汇合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作。
- LinkedList 采纳链表存储，所以，如果是在头尾插入或者删除元素不受元素地位的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、removeLast()），工夫复杂度为 O(1)，如果是要在指定地位 i 插入和删除元素的话（add(int index, E element)，remove(Object o)），工夫复杂度为 O(n)，因为须要先挪动到指定地位再插入。
是否反对疾速随机拜访： LinkedList 不反对高效的随机元素拜访，而 ArrayList 反对。疾速随机拜访就是通过元素的序号疾速获取元素对象 (对应于get(int index) 办法)。
内存空间占用： ArrayList 的空间节约次要体现在在 list 列表的结尾会预留肯定的容量空间，而 LinkedList 的空间破费则体现在它的每一个元素都须要耗费比 ArrayList 更多的空间（因为要寄存间接后继和间接前驱以及数据）。

咱们在我的项目中个别是不会应用到 LinkedList 的，须要用到 LinkedList 的场景简直都能够应用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）本人都说从来不会应用 LinkedList。

另外，不要下意识地认为 LinkedList 作为链表就最适宜元素增删的场景。我在下面也说了，LinkedList 仅仅在头尾插入或者删除元素的时候工夫复杂度近似 O(1)，其余状况增删元素的工夫复杂度都是 O(n)。

双向链表： 蕴含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。

另外举荐一篇把双向链表讲清楚的文章：https://juejin.cn/post/6844903648154271757

双向循环链表： 最初一个节点的 next 指向 head，而 head 的 prev 指向最初一个节点，形成一个环。

public interface RandomAccess {}

查看源码咱们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。标识什么？标识实现这个接口的类具备随机拜访性能。

在 binarySearch（) 办法中，它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用 indexedBinarySearch() 办法，如果不是，那么调用 iteratorBinarySearch() 办法

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 实现了 RandomAccess 接口，而 LinkedList 没有实现。为什么呢？我感觉还是和底层数据结构无关！ArrayList 底层是数组，而 LinkedList 底层是链表。数组人造反对随机拜访，工夫复杂度为 O(1)，所以称为疾速随机拜访。链表须要遍历到特定地位能力拜访特定地位的元素，工夫复杂度为 O(n)，所以不反对疾速随机拜访。，ArrayList 实现了 RandomAccess 接口，就表明了他具备疾速随机拜访性能。RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具备疾速随机拜访性能的！

详见笔主的这篇文章:ArrayList 扩容机制剖析

comparable 接口实际上是出自 java.lang 包它有一个 compareTo(Object obj)办法用来排序
comparator接口实际上是出自 java.util 包它有一个 compare(Object obj1, Object obj2) 办法用来排序

个别咱们须要对一个汇合应用自定义排序时，咱们就要重写 compareTo() 办法或 compare() 办法，当咱们须要对某一个汇合实现两种排序形式，比方一个 song 对象中的歌名和歌手名别离采纳一种排序办法的话，咱们能够重写 compareTo() 办法和应用自制的 Comparator 办法或者以两个 Comparator 来实现歌名排序和歌星名排序，第二种代表咱们只能应用两个参数版的 Collections.sort().

        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        arrayList.add(-1);
        arrayList.add(3);
        arrayList.add(3);
        arrayList.add(-5);
        arrayList.add(7);
        arrayList.add(4);
        arrayList.add(-9);
        arrayList.add(-7);
        System.out.println("原始数组:");
        System.out.println(arrayList);
        // void reverse(List list)：反转
        Collections.reverse(arrayList);
        System.out.println("Collections.reverse(arrayList):");
        System.out.println(arrayList);

        // void sort(List list), 按天然排序的升序排序
        Collections.sort(arrayList);
        System.out.println("Collections.sort(arrayList):");
        System.out.println(arrayList);
        // 定制排序的用法
        Collections.sort(arrayList, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);
            }
        });
        System.out.println("定制排序后：");
        System.out.println(arrayList);

Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：[7, 4, 3, 3, -1, -5, -7, -9]

// person 对象没有实现 Comparable 接口，所以必须实现，这样才不会出错，才能够使 treemap 中的数据按顺序排列
// 后面一个例子的 String 类曾经默认实现了 Comparable 接口，具体能够查看 String 类的 API 文档，另外其余
// 像 Integer 类等都曾经实现了 Comparable 接口，所以不须要另外实现了
public  class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {super();
        this.name = name;
        this.age = age;
    }

    public String getName() {return name;}

    public void setName(String name) {this.name = name;}

    public int getAge() {return age;}

    public void setAge(int age) {this.age = age;}

    /**
     * T 重写 compareTo 办法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {if (this.age > o.getAge()) {return 1;}
        if (this.age < o.getAge()) {return -1;}
        return 0;
    }
}

    public static void main(String[] args) {TreeMap<Person, String> pdata = new TreeMap<Person, String>();
        pdata.put(new Person("张三", 30), "zhangsan");
        pdata.put(new Person("李四", 20), "lisi");
        pdata.put(new Person("王五", 10), "wangwu");
        pdata.put(new Person("小红", 5), "xiaohong");
        // 失去 key 的值的同时失去 key 所对应的值
        Set<Person> keys = pdata.keySet();
        for (Person key : keys) {System.out.println(key.getAge() + "-" + key.getName());

        }
    }

Output：

5- 小红
10- 王五
20- 李四
30- 张三

1、什么是无序性？无序性不等于随机性，无序性是指存储的数据在底层数组中并非依照数组索引的程序增加，而是依据数据的哈希值决定的。

2、什么是不可重复性？不可重复性是指增加的元素依照 equals()判断时，返回 false，须要同时重写 equals()办法和 HashCode()办法。

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保障元素惟一，并且都不是线程平安的。
HashSet、LinkedHashSet 和 TreeSet 的次要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出程序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的形式有天然排序和定制排序。
底层数据结构不同又导致这三者的利用场景不同。HashSet 用于不须要保障元素插入和取出程序的场景，LinkedHashSet 用于保障元素的插入和取出程序满足 FIFO 的场景，TreeSet 用于反对对元素自定义排序规定的场景。

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

Queue 扩大了 Collection 的接口，依据 因为容量问题而导致操作失败后处理形式的不同 能够分为两类办法: 一种在操作失败后会抛出异样，另一种则会返回非凡值。

`Queue` 接口	抛出异样	返回非凡值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查问队首元素	element()	peek()

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

Deque 扩大了 Queue 的接口, 减少了在队首和队尾进行插入和删除的办法，同样依据失败后处理形式的不同分为两类：

`Deque` 接口	抛出异样	返回非凡值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查问队首元素	getFirst()	peekFirst()
查问队尾元素	getLast()	peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其余办法，可用于模仿栈。

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具备队列的性能，但两者有什么区别呢？

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不反对存储 NULL 数据，但 LinkedList 反对。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就曾经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作仍然为 O(1)。尽管 LinkedList 不须要扩容，然而每次插入数据时均须要申请新的堆空间，均摊性能相比更慢。

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

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

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

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

PriorityQueue 在面试中可能更多的会呈现在手撕算法的时候，典型例题包含堆排序、求第 K 大的数、带权图的遍历等，所以须要会纯熟应用才行。

专一 Java 原创干货分享，大三开源 JavaGuide（「Java 学习 + 面试指南」一份涵盖大部分 Java 程序员所须要把握的外围常识。筹备 Java 面试，首选 JavaGuide！），目前曾经 120k+ Star。

如果本文对你有帮忙的话，欢送点赞分享，这对我持续分享 & 创作优质文章十分重要。感激 🙏🏻

关于java:Java-集合常见知识点面试题总结上2022-最新版

汇合概述

Java 汇合概览

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

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

List

Set

Queue

Map

如何选用汇合?

为什么要应用汇合？

Collection 子接口之 List

Arraylist 和 Vector 的区别?

Arraylist 与 LinkedList 区别?

补充内容: 双向链表和双向循环链表

补充内容:RandomAccess 接口

说一说 ArrayList 的扩容机制吧

Collection 子接口之 Set

comparable 和 Comparator 的区别

Comparator 定制排序

重写 compareTo 办法实现按年龄来排序

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

比拟 HashSet、LinkedHashSet 和 TreeSet 三者的异同

Collection 子接口之 Queue

Queue 与 Deque 的区别

ArrayDeque 与 LinkedList 的区别

说一说 PriorityQueue

后记