Java集合常见面试题总结(上)

Java 集合概览

Comparator 定制排序

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);

重写Comparator方法

// 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;
    }
}

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

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

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

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

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

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

• 

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

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

Deque、ArrayList 和 ArrayDeque 都是 Java 集合框架中的数据结构，但它们在内部实现、应用场景和性能特点上各有差异。以下是对每一个的详细分析：

1. Deque

Deque（双端队列）是一个接口，表示支持在两端进行插入和删除操作的线性集合。Deque 继承自 Queue 接口，可以作为队列（FIFO）或栈（LIFO）来使用。常用的实现类有 ArrayDeque 和 LinkedList。

• 主要特点:

• • 双端操作：Deque 支持在队列的两端插入和删除元素，分别使用 addFirst、addLast、removeFirst 和 removeLast 等方法。
  • 接口方法：Deque 接口中有 push 和 pop 方法，使其可以作为栈使用，同时也提供 offer、poll、peek 等方法，使其可以作为队列使用。
  • 常见应用：Deque 常用于实现栈和队列，例如浏览器的历史记录、任务调度等。

• 主要实现类:

• • ArrayDeque：基于数组实现，支持高效的固定大小扩展。
  • LinkedList：基于双向链表实现，适合频繁插入和删除的场景。

2. ArrayList

ArrayList 是 List 接口的一个实现类，内部使用动态数组来管理数据。它提供了一个动态扩容机制，当数组容量不够时会自动增加。

• 主要特点:

• • 顺序存储：ArrayList 的元素是顺序存储的，因此可以根据索引随机访问（即 O(1) 复杂度），性能优于链表类的数据结构。
  • 动态扩容：ArrayList 会自动扩容，通常新容量为旧容量的 1.5 倍。
  • 线程不安全：ArrayList 是非线程安全的，适合单线程环境。如果在多线程环境中使用，建议使用 Collections.synchronizedList 或 CopyOnWriteArrayList。
  • 插入和删除性能：由于内部是数组实现，ArrayList 在添加和删除时需要移动元素，在首位插入或删除的性能较低（O(n)），但在尾部添加元素时性能较好（O(1)）。
  • 适用场景：当需要快速随机访问和少量增删操作时，ArrayList 是理想的选择，例如保存学生名单、订单列表等。

3. ArrayDeque

ArrayDeque 是 Deque 接口的一个实现，使用数组作为内部存储结构，但与 ArrayList 不同，ArrayDeque 是为双端操作设计的。它是 Java 中最常用的双端队列实现之一。

• 主要特点:

• • 双端队列操作：支持在两端高效插入和删除操作 (O(1) 复杂度)。
  • 无固定容量限制：当容量不足时，ArrayDeque 会动态扩容，以适应不断增长的元素数量。
  • 非线程安全：和 ArrayList 一样，ArrayDeque 不是线程安全的。如果需要在多线程环境中使用，需手动同步。
  • 不允许存储 null：ArrayDeque 不允许存储 null 值，这样可以区分有效值和空槽。
  • 不适合作为随机访问容器：ArrayDeque 不是 List，不提供基于索引的随机访问。若需随机访问，用 ArrayList 更合适。
  • 适用场景：适合实现栈和队列，例如任务调度、缓存机制、浏览器历史记录等。

对比总结

选择建议

• 使用 Deque：在需要双端操作的情况下，例如实现双端队列、栈、或有需要的缓存机制时。选择具体实现时，ArrayDeque 性能高于 LinkedList，适合多数情况。
• 使用 ArrayList：在需要频繁访问某一位置的元素，且增删操作主要集中在末尾的情况，例如保存学生记录、订单列表等。
• 使用 ArrayDeque：在需要双端队列操作且无需随机访问时，例如任务调度、栈的实现等。