List

ArrayList和Array的区别？

ArrayList 内部基于动态数组实现，比 Array（静态数组）使用起来更加灵活：

ArrayList会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了
ArrayList 允许你使用泛型来确保类型安全，Array 则不可以
ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象
ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力
ArrayList创建时不需要指定大小，而Array创建时必须指定大小

ArrayList和Vector的区别？

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

ArrayList可以添加null值吗？

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

@Test
public void testArrayList() {
    ArrayList<String> arrayList = new ArrayList<>();
    arrayList.add("String");
    arrayList.add(null);
    System.out.println(arrayList);
}

运行结果：

[String, null]

虽然可以添加null值，但是不建议，因为null值无意义，而且会让代码难以维护，比如忘记做判空处理就会导致空指针异常（NPE）

ArrayList与LinkedList的区别？

线程安全
- ArrayList和LinkedList都是不同步的，也就是不保证线程安全
底层数据结构
- ArrayList底层使用Object[]数组
- LinkedList底层使用双向链表数据结构（JDK1.6以前为循环链表，JDK1.7取消了循环。注意不是双向循环链表）
插入和删除是否受元素位置的影响
- ArrayList采用数组存储，所以插入和删除的时间复杂度受元素位置影响
  
  执行add(E e)方法，默认将元素加到元素列表的末尾，这种情况的时间复杂度就是O(1)
  
  如果是指定位置插入和删除元素（add(index index, E element)），时间复杂度为O(n)
- LinkedList采用双向链表存储，所以在头尾插入和删除元素不受元素位置的影响例如：add(E e)、addFirst(E e)、removeFirst()、removeLast()时间复杂度是0(1)
  
  如果是指定位置插入和删除元素（add(int index, E element)，remove(Object o)、remove(int index)）时间复杂度为O(n)
是否支持快速随机访问（快速随机访问：通过元素的序号快速获取元素对象（get(int index)））
- LinkedList不支持高效的随机元素访问
- ArrayList因为实现了RandomAccess接口，所以支持
内存空间占用
- ArrayList的空间花费主要体现在：在list列表的结尾会预留一定的容量空间
- LinkedList的空间花费主要体现在：它的每一个元素都要消耗比ArrayList更多的空间（因为要存放直接前驱和直接后继和数据）

ArrayList：ArrayList | Feliks

LinkedList：LinkedList | Feliks

ArrayList的扩容机制？

ArrayList

Set

HashSet：基于HashSet实现，底层用HashMap保存元素
LinkedHashSet：LinkedHashSet是HashSet的子类，并且其内部是通过LinkedHashSet来实现的
TreeSet：红黑树，自平衡的排序二叉树

Comparable和Comparator的区别

Comparable接口和Comparator接口都是Java中用于排序的接口，他们在实现类对象之间比较大小、排序等方面发挥重要的作用

Comparable接口实际上是出自java.lang包下的，他有一个compareTo(T o)方法用来排序

package java.lang;
import java.util.*;

public interface Comparable<T> {
    public int compareTo(T o);
}

Comparator接口实际上是java.util包下的，他有一个compare(T o1, T o2)方法用来排序

package java.util;

import java.io.Serializable;
import java.util.function.Function;
import java.util.function.ToIntFunction;
import java.util.function.ToLongFunction;
import java.util.function.ToDoubleFunction;
import java.util.Comparators;

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
}

一般我们需要对一个集合使用自定义排序时，需要重写compareTo()或compare()，当我们需要对某一个集合实现两种排序方式，比如一个Song对象中的歌名和歌手分别采用一种排序方法的话，可以重写compareTo()方法和使用自制的Comparator方法或者以两个Comparator()来实现歌名排序和歌星名字排序，第二种代表我们只能使用Collections.sort()

Comparator()定制排序

public void testComparator() {
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(-1);
    arrayList.add(3);
    arrayList.add(3);
    arrayList.add(-1);
    arrayList.add(7);
    arrayList.add(4);
    arrayList.add(-9);
    arrayList.add(-7);
    System.out.println("原始数组：");
    System.out.println(arrayList);

    // 反转数组
    Collections.reverse(arrayList);
    System.out.println("Collections.reverse(arrayList)：");
    System.out.println(arrayList);

    // 按自然排序的升序排序
    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);
}

compareTo()

public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

输出：

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

如果指定的数与参数相等返回 0。

如果指定的数小于参数返回 -1。

如果指定的数大于参数返回 1。

所以这里是按照从大到小的顺序进行排列，如果要从小到大进行排序的话：o1.compareTo(o2)

重写compareTo()来实现自定义排序

这里我们定义一个Person类，按照Person类中的年龄进行排序

Person对象并没有实现Comparable接口，所以必须实现，这样才可以使treemap中的数据按照顺序排列

String类、Integer类等都默认实现了Comparable接口，所以就不需要另外实现了

public class Person implements Comparable<Person> {

    private String name;
    private int age;

    public Person() {
    }

    public Person(String name, int age) {
        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;
    }

    /**
     * 重写comparTo方法进行自定义排序
     * @param o the object to be compared.
     * @return
     */
    @Override
    public int compareTo(Person o) {
        if(this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}

测试：

public void testCompareTo() {
    TreeMap<Person, String> personStringTreeMap = new TreeMap<>();
    personStringTreeMap.put(new Person("张三", 20), "zhangsan");
    personStringTreeMap.put(new Person("李四", 32), "lisi");
    personStringTreeMap.put(new Person("王五", 12), "wangwu");
    personStringTreeMap.put(new Person("赵六", 43), "zhaoliu");
    personStringTreeMap.put(new Person("小红", 23), "xiaohong");
    // 得到key的同时获得key对印的个value值
    Set<Person> keySet = personStringTreeMap.keySet();
    for (Person key : keySet) {
        System.out.println(key.getAge() + "-" + key.getName());
    }
}

输出：

12-王五
20-张三
23-小红
32-李四
43-赵六

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

无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序进行添加，而是根据数据的哈希值来决定的
不可重复性是指添加的元素按照equals()判断时，返回false，需要同时重写equals()和hashCode()方法

HashSet、LinkedHashSet和TreeSet区别？

HashSet、LinkedHashSet和TreeSet三者都是Set接口的实现类，都能保证元素唯一，并且不是线程安全的
HashSet、LinkedHashSet和TreeSet他们之间的主要区别在于底层数据结构不同
- HashSet的底层数据结构：哈希表（HashMap实现的）
- LinkedHashSet的底层数据结构：链表和哈希表，元素的插入和取出顺序满足FIFO
- TreeSet的底层数据结构：红黑树，元素是有序的，排序的方法有自然排序和定制排序
他们之间底层的数据结构不同又导致三者的应用场景不同
- HashSet：用于不需要保证元素插入和取出顺序的场景
- LinkedHashSet：用于保证元素的插入和取出顺序满足FIFO的场景
- TreeSet：用于支持元素自定义排序规则的场景

Queue

Queue与Deque的区别？

Queue是单向队列，只能从一端插入严肃，另一端删除元素，遵循着FIFO的原则（先进先出）

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

`Queue`接口	失败后抛出异常	失败后返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

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

Deque扩展了Queue接口

public interface Deque<E> extends Queue<E> {}

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

`Deque`接口	失败后抛出异常	失败后返回特殊值
插入队首	addFirsr(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst(E e)	pollFirst()
删除队尾	removeLast(E e)	pollLast()
查询队首元素	getFirst(E e)	peekFirst()
删除队尾元素	getLast(E e)	peekLast()

此外，Deque还提供有push()和pop()等其他方法，可用于模拟栈（LIFO）的操作

ArrayDeque和LinkedList的区别？

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

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

区别：

ArrayDeque是基于可变长的数组和双指针来实现的，而LinkedList则是通过链表来实现的
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

public interface BlockingQueue<E> extends Queue<E> {
    // ......
}

BlockingQueue是基于阻塞机制实现的线程安全的队列，而阻塞机制的实现是通过在入队和出队时加锁的方式避免并发操作

BlockingQueue不同于普通的Queue的主要区别：

通过在入队和出对时进行加锁，保证了队列的线程安全
支持阻塞的入队和出队方法：当队列为满时，会阻塞入对的线程，知道队列不为满；当队列为空的时候会阻塞出队的线程，直到队列中有元素

BlockingQueue常用于生产者-消费者模型中，往队列里添加元素就是生产者，从队列中获取元素就是消费者

在通常情况下生产者和消费者都是由多个线程组成的

BlockingQueue的实现类？

在Java中常用的阻塞队列实现类：

ArrayBlockingQueue：使用数组实现的有界阻塞队列，在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制
LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列，在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE，和ArrayBlockingQueue不同的是，它仅支持非公平的锁访问机制
PriorityBlockingQueue：支持优先级排序的无解阻塞队列，元素必须实现Comparable接口或者在构造器中传入Comparator对象，且不能插入null元素
SynchronousQueue：同步队列，是一种不存储元素的阻塞队列，每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作，因此SynchronousQueue通常用于线程之间的直接传递数据
DelayQueue：延迟队列，其中的元素只有到了指定的延时时间才会从队列中出队

ArrayBlockingQueue和LinkedBlockingQueue区别？

二者都是Java并发包（java.util.concurrent）中常用的两种阻塞队列实现，他们都是线程安全的

区别：

底层实现
- ArrayBlockingQueue：基于数组实现
- LinkedBlockingQueue：基于链表实现
是否有界
- ArrayBlockingQueue：有界队列，创建时必须指定大小
- LinkedBlockingQueue：无界队列，创建时可不指定大小，默认为Integer.MAX_VALUE，如果指定队列大小就会变成有界的
锁是否分离
- ArrayBlockingQueue：锁不分离，生产者和消费者用的是同一个锁
- LinkedBlockingQueue：锁分离，生产者用的是putLock，消费者用的是takeLock，可以防止生产者和消费者线程之间的锁争夺
内存占用
- ArrayBlockingQueue：需要提前分配数组内存
- LinkedBlockingQueue：动态分配链表节点内存
- 意味着：ArrayBlockingQueue在创建时就会占用一定空间的内存，往往申请的内存比实际使用的内存要大，而LinkedBlockingQueue则是根据元素的增加而逐渐占用内存空间

Feliks

https://qetuop91.github.io/2024/04/15/ji-he-kuang-jia-2.0-list-set-queue/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Feliks !

Java 面试集合

集合框架-3.0-Map

Java集合框架

2024-04-15 Java

Java 面试集合

Java基础1.0

Java基础

2024-04-15 Java

Java 面试

集合框架-2.0-List、Set、Queue

List

ArrayList和Array的区别？

ArrayList和Vector的区别？

ArrayList可以添加null值吗？

ArrayList与LinkedList的区别？

ArrayList的扩容机制？

Set

Comparable和Comparator的区别

Comparator()定制排序

重写compareTo()来实现自定义排序

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

HashSet、LinkedHashSet和TreeSet区别？

Queue

Queue与Deque的区别？

ArrayDeque和LinkedList的区别？

⭐PriorityQueue？

BlockingQueue？

BlockingQueue的实现类？

ArrayBlockingQueue和LinkedBlockingQueue区别？

扫码请作者喝杯咖啡