Java集合常见面试题（三）

Collection 子接口之 Set

comparable 和 Comparator 的区别

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

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

Comparator 定制排序

 ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(9);
        arrayList.add(8);
        arrayList.add(7);
        arrayList.add(6);
        arrayList.add(5);
        arrayList.add(4);
        arrayList.add(3);
        arrayList.add(2);
        arrayList.add(1);

        System.out.println("原始数组:");
        System.out.println(arrayList);

        // void sort(List list),按自然排序的升序排序
        Collections.sort(arrayList);
        System.out.println("Collections.sort(arrayList):");
        System.out.println(arrayList);

        Collections.reverse(arrayList);
        System.out.println("Collections.reverse(arrayList):");
        System.out.println(arrayList);
        
        //自定义排序方法:
        Collections.sort(arrayList, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        System.out.println("自定义排序方法:");
        System.out.println(arrayList);

Output:

原始数组:
[9, 8, 7, 6, 5, 4, 3, 2, 1]
Collections.sort(arrayList):
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Collections.reverse(arrayList):
[9, 8, 7, 6, 5, 4, 3, 2, 1]
自定义排序方法
[1, 2, 3, 4, 5, 6, 7, 8, 9]

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

 /**
   * 在set.add()方法添加的是一个自定义类对象的时候由于这个类默认没有实现Comparable接口并重写compareto()方法所以set在添加这个类     
   * 对象set.add(new Person())会抛出没有比较器异常java.lang.ClassCastException。
   * /
public class Student implements Comparable<Student>{

    public String sname;

    public Integer sage;

    public String getSname() {
        return sname;
    }

    public void setSname(String sname) {
        this.sname = sname;
    }

    public Integer getSage() {
        return sage;
    }

    public void setSage(Integer sage) {
        this.sage = sage;
    }

    public Student(String sname, Integer sage) {
        this.sname = sname;
        this.sage = sage;
    }


    @Override
    public int compareTo(Student o) {

        if(this.sage > o.sage){
            return 1;
        }else if (this.sage < o.sage){
            return -1;
        }else {
            return 0;
        }
        
    }
}

public static void main(String[] args) {

        Set<Student> set = new TreeSet<>();


        set.add(new Student("张三",15));
        set.add(new Student("李四",18));
        set.add(new Student("王五",5));
        set.add(new Student("赵六",2));

        for (Student student : set) {
            System.out.println(student.sname + " : " + student.sage);
        }
    }

Output:

赵六 : 2
王五 : 5
张三 : 15
李四 : 18

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

• 无序性不等于随机性 无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 而是根据数据的哈希值决定的。

• 不可重复性是指添加的元素按照 equals() 判断时 返回 false需要同时重写 equals() 方法和 hashCode() 方法。

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

• HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类都能保证元素唯一并且都不是线程安全的。

• HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表基于 HashMap 实现。
  LinkedHashSet 的底层数据结构是链表和哈希表元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树元素是有序的排序的方式有自然排序和定制排序。

• 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景TreeSet 用于支持对元素自定义排序规则的场景。

Collection 子接口之 Queue

Queue 与 Deque 的区别

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

• 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 作为构造参数从而来自定义元素优先级的先后。

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

示例代码

 PriorityQueue<Integer> queue = new PriorityQueue<>((x1,x2) -> x2-x1);

        queue.add(1);
        queue.add(5);
        queue.add(4);
        queue.add(2);

        System.out.println(queue.poll());
        System.out.println(queue.poll());

Output:

5
4