跳至主要內容

Collection系列概述

God约 2557 字大约 9 分钟

本节主要介绍继承自Collection的3大接口：List、Set、Queue。

1、List

Arraylist 和 Vector 的区别?

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

Arraylist 与 LinkedList 的区别?

  • 底层数据结构：ArrayList的实现是基于数组，LinkedList的实现是基于双向链表
  • 随机访问：ArrayList优于LinkedList，ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问；而LinkedList的每个元素都依靠地址指针和前后元素连接，在这种情况下，查找某个元素的时间复杂度是O(n)
  • 插入和删除：LinkedList优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引
  • 空间占用：LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素

RandomAccess 接口

public interface RandomAccess {
}

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

在 Collections.binarySearch（) 方法中，它要判断传入的 list 是否 RamdomAccess 的实例，如果是，调用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 接口才具有快速随机访问功能的！

2、Set

HashSet、LinkedHashSet、TreeSet 三者的异同

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

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

无序性： 是指数据在底层数组中的存储顺序（存储位置）并非按照插入顺序排列 ，而是根据数据的哈希值决定的

不可重复性： 是指添加的元素按照 equals()判断时 ，必须返回 false，即相同元素不会重复插入（对象类型最好同时重写 equals()方法和 HashCode()方法）

Comparable 和 Comparator 的区别

  • comparable 接口出自java.lang包，它有一个 compareTo(Object obj)方法用来排序

  • comparator 接口出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序

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

System.out.println("自然排序：");
Collections.sort(arrayList);
System.out.println(arrayList);

System.out.println("定制排序：");
Collections.sort(arrayList, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});
System.out.println(arrayList);

Output:

原始数组：
[-1, 3, 3, -5, 7, 4, -9, -7]
自然排序：
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序：
[7, 4, 3, 3, -1, -5, -7, -9]

Comparable 定制排序

// 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-张三

3、Queue

Queue 与 Deque 的区别？

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 的区别？

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大的数、带权图的遍历等，所需要会熟练使用！

4、Collections 集合工具类

Collections 工具类常用方法：

  1. 排序
  2. 查找、替换
  3. 同步控制

排序

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

查找、替换

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

同步控制

Collections 提供了多个synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合！

方法如下：

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。
MIT Licensed | Copyright © 2024-present God