• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

Java集合大全

开发技术 开发技术 2周前 (09-13) 20次浏览

集合也是一种容器,在开发过程中的应用数不胜数,除了常见的HashMap、ArrayList、LinkedList和HashSet等等,了解这些集合API的同时,也应该了解这些集合内部发生了什么事情,这样就不再是集合提供了什么功能给我们用,而是我们选择了它的什么功能。

一、Java集合架构图

Java集合大全

1.集合框架提供两个遍历接口:Iterator和ListIterator,后者是前者的优化版,支持在集合任意一个位置进行前后双向遍历;
2.整个集合框架分为两个类型:Collection和Map,前者是一个容器,存储一系列的对象;后者是键值对<key, value>,存储一系列的键值对;
3.在现有的集合框架体系下,衍生出四种具体集合类型:Map、Set、List、Queue;
4.Map存储<key,value>键值对,查找元素时通过key查找value;
5.Set内部存储一系列不可重复的对象,且是一个无序集合,对象排列顺序不一;
6.List内部存储一系列可重复的对象,是一个有序集合,对象按插入顺序排列;
7.Queue是一个队列容器,其特性与List相同,但只能从队头和队尾操作元素;
8.JDK 为集合的各种操作提供了两个工具类Collections和Arrays;

9.四种具体类型的集合,内部会再衍生许多不同特性的集合子类,根据不通的应用场景选择使用的集合;

二、集合的迭代器

目前Java里有三个迭代器:Iterator Iterable ListIterator。

1. 首先看Iterator接口:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

提供的API接口含义如下:
hasNext():判断集合中是否还有下一个对象。
next():返回集合中的下一个对象,并将访问指针移动一位。
remove():删除集合中调用next()方法返回的对象。
在JDK早期版本里,遍历集合的方式只有一种,那就是通过Iterator迭代器操作,具体实例如下:

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
Iterator iter = list.iterator();
while (iter.hasNext()) {
    Integer next = iter.next();
    System.out.println(next);
    if (next == 20) {
      iter.remove(); 
    }
}

2. Iterable接口

public interface Iterable<T> {
    Iterator<T> iterator();
    // since JDK 1.8
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    // since JDK 1.8
    default Spliterator<T> spliterator() {
       return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

 Iterable接口里面提供了一个Iterator()方法返回迭代器,因此实现了Iterable接口的集合依旧可以使用迭代器遍历和操作集合中的对象。在 JDK 1.8中,Iterable接口新增了一个方法forEach(),它允许使用增强 for 循环遍历对象。

    为什么要设计两个接口Iterable和Iterator?Iterator接口的保留可以让子类去实现自己的迭代器,而Iterable接口更加关注于for-each的增强语法。

3. ListIterator

  ListIterator继承 Iterator 接口,仅存在于 List 集合之中,通过调用方法可以返回起始下标为 index的迭代器。ListIterator 中有几个重要方法,大多数方法与 Iterator 中定义的含义相同,此外根据返回的迭代器,且可以实现双向遍历

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    // 替换当前下标的元素,即访问过的最后一个元素
    void set(E e);
    void add(E e);
}

三、Map和Collection接口

  Map接口和Collection接口是Java的集合框架中的两个重要门派,Collection存储的是集合元素本身,Map存储的是<key,value>键值对,但是部分Collection子类使用了Map来实现的。例如:HashSet底层使用了HashMap,TreeSet底层使用了TreeMap,LinkedHashSet底层使用了LinkedHashMap

Java集合大全

Map接口的数据结构是<key, value>形式,key 映射value,一个key对应一个value,key不可重复,value可重复。Map接口细分为不同的种类:

    SortedMap接口:该类映射可以对<key, value>按照自己的规则进行排序,具体实现有 TreeMap
    AbsractMap抽象类:它为子类提供好一些通用的API实现,所有的具体Map如HashMap都会继承它

Collection接口提供了所有集合的通用方法(注意这里不包括Map):
    添加方法:add(E e) / addAll(Collection<? extends E> var1)/ addAll(int index, Collection<? extends E> var1)  
    查找方法:contains(Object var1) / containsAll(Collection<?> var1)/
    查询集合自身信息:size() / isEmpty()
    删除方法:remove(O o)/removeAll(Collection<?> var1)/求交集:retainAll(Collection c)

    … …

Collection接口将集合细分为不同的种类:

    Set接口:一个不允许存储重复元素的无序集合,具体实现有HashSet / TreeSet···
    List接口:一个可存储重复元素的有序集合,具体实现有ArrayList / LinkedList···
    Queue接口:一个可存储重复元素的队列,具体实现有PriorityQueue / ArrayDeque···

1. Map接口详解

Map 体系下主要分为 AbstractMap 和 SortedMap两类集合
        AbstractMap是对Map接口的扩展,定义了普通Map集合具有的通用方法,可避免子类重复编写大量相同代码,子类继承 AbstractMap 后可重写它的方法,并实现额外逻辑,对外可提供更多的功能。
        SortedMap接口定义了Map具有排序行为,当子类实现它时,必须重写所有方法,对外提供排序功能。

1.1 HashMap

        HashMap 是一个最通用的利用哈希表存储元素的集合,有元素加入HashMap时,会将key的哈希值转换为数组的索引下标确定存放位置,在查找元素时,根据key的哈希地址转换成数组的索引下标确定查找位置。
    HashMap 底层是用数组 + 链表 + 红黑树这三种数据结构实现,是非线程安全的集合。

Java集合大全

加入元素发生哈希冲突时,HashMap会将相同地址的元素连成一条链表,若链表长度大于8,且数组长度大于64会转换成红黑树数据结构。

关于 HashMap 的简要总结:
    1. 它是集合中最常用的Map集合类型,底层由数组 + 链表 + 红黑树组成;
    2. HashMap不是线程安全的;
    3. 插入元素时,通过计算元素哈希值,通过哈希映射函数转换为数组下标;查找元素时,通过哈希映射函数得到数组下标定位元素的位置。

1.2 LinkedHashMap

LinkedHashMap可以看作是 HashMap 和 LinkedList 的结合:它是在 HashMap 的基础上添加了一条双向链表,默认存储各个元素的插入顺序,但由于这条双向链表,使得 LinkedHashMap 可以实现 LRU缓存淘汰策略,因为我们可以设置这条双向链表按照元素的访问次序进行排序

// 头节点
transient LinkedHashMap.Entry<K, V> head;
// 尾结点
transient LinkedHashMap.Entry<K, V> tail;

利用 LinkedHashMap 可以实现 LRU 缓存淘汰策略,因为它提供了一个方法:

protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
    return false;
}

该方法可以移除最靠近链表头部的一个节点,而在get(key)方法源代码如下,其作用是挪动结点的位置:

public V get(Object key) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
      return null;
   if (accessOrder)
      afterNodeAccess(e);
   return e.value;
}

只要调用了get(key)且accessOrder = true,则会将该节点更新到链表尾部,具体的逻辑在afterNodeAccess()中,源码如下:

void afterNodeAccess(Node<K,V> e) { // move node to last
  LinkedHashMap.Entry<K,V> last;
  if (accessOrder && (last = tail) != e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.after = null;
    if (b == null) head = a;
      else b.after = a;
    if (a != null) a.before = b;
    else last = b;
    if (last == null) head = p;
    else {
      p.before = last;
      last.after = p;
     }
    tail = p;
    ++modCount;
  }
}

指定accessOrder = true,可以设定链表按照访问顺序排列,通过提供的构造器可以设定accessOrder。

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

重写removeEldestEntry()方法,内部定义逻辑,通常是判断容量是否达到上限,若是则执行淘汰。

关于 LinkedHashMap 总结两点:
    1. 底层维护了一条双向链表,继承了 HashMap,所以不是线程安全的
    2. LinkedHashMap 可实现LRU缓存淘汰策略,其原理是通过设置accessOrder为true并重写removeEldestEntry方法定义淘汰元素时需满足的条件。

1.3 TreeMap

TreeMap 是 SortedMap 的子类,所以它具有排序功能,是基于红黑树数据实现的,每个键值对<key, value>都是一个结点,默认情况下按照key自然排序,另一种是可以通过传入定制的Comparator进行自定义规则排序。

// 按照 key 自然排序,Integer 的自然排序是升序
TreeMap<Integer, Object> naturalSort = new TreeMap<>();
// 定制排序,按照 key 降序排序
TreeMap<Integer, Object> customSort = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));

Java集合大全

图中红黑树的每一个节点都是一个Entry,在这里不标明 key 和 value 了,这些元素都是已按照key排好序了,整个数据结构都是保持着有序状态!
关于自然排序与定制排序:
自然排序:要求key必须实现Comparable接口。
由于Integer类实现了Comparable 接口,按照自然排序规则是按照key从小到大排序。

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(2, "贰");
treeMap.put(1, "壹");
System.out.print(treeMap);
// {1=壹, 2=贰}

定制排序:在初始化 TreeMap 时传入新的Comparator,不要求key实现 Comparable 接口

TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));
treeMap.put(1, "壹");
treeMap.put(2, "贰");
treeMap.put(4, "肆");
treeMap.put(3, "叁");
System.out.println(treeMap);
// {4=肆, 3=叁, 2=贰, 1=壹}

关于 TreeMap 主要介绍了三点:
        1. 它底层是由红黑树实现的,操作的时间复杂度为O(logN);
        2. TreeMap 可以对key进行自然排序或者自定义排序,自定义排序时需要传入Comparator,而自然排序要求key实现了Comparable接口;
        3. TreeMap 不是线程安全的。

1.4 WeakHashMap

        WeakHashMap底层存储的元素的数据结构是数组 + 链表,没有红黑树。日常开发中用的很少,是基于Map实现,Entry中键在每一次垃圾回收都会被清除,适合用于短暂访问或访问一次的元素,缓存在WeakHashMap中,并尽早地把它回收掉。

public class WeakHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
}

  当Entry被GC时,WeakHashMap 是如何感知到某个元素被回收的呢?

        在 WeakHashMap 内部维护了一个引用队列queue:

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

queue里包含了所有被GC掉的key,当JVM开启GC后,如果回收掉WeakHashMap中的key,会将key放入queue 中,在expungeStaleEntries()中遍历 queue,把queue中的所有key拿出来,并在WeakHashMap中删除掉,以达到同步。

Java集合大全

图中被虚线标识的元素将会在下一次访问 WeakHashMap 时被删除,WeakHashMap 内部会做好一系列的调整工作,所以队列的作用是标志已经被GC掉的元素。
关于 WeakHashMap 需要注意三点:
        1. 它的键是一种弱键,放入 WeakHashMap 时,随时会被回收掉,所以不能确保某次访问元素一定存在;
        2. 它依赖普通的Map进行实现,是一个非线程安全的集合;
        3. WeakHashMap 通常作为缓存使用,适合存储那些只需访问一次、或只需保存短暂时间的键值对。

1.5 HashTable

Hashtable底层存储结构是数组+链表,是一个线程安全的集合。当链表过长时,查询效率过低,会长时间锁住Hashtable,所以在并发环境下,性能很差,现在基本上被淘汰了,也很少用了。线程安全,它所有的方法都被加上了 synchronized 关键字。HashTable 默认长度为 11,负载因子为 0.75F,即元素个数达到数组长度的 75% 时,会进行一次扩容,每次扩容为原来数组长度的 2 倍

2. Collection 集合体系详解

Collection 集合体系的顶层接口就是Collection,它规定了该集合下的一系列方法。
该集合下可以分为三大类集合:List,Set和Queue
    Set接口:不可存储重复的元素,且任何操作均需要通过哈希函数映射到集合内部定位元素,集合内部元素默认无序。
    List接口:可存储重复的元素,且集合内部的元素按照元素插入的顺序有序排列,可以通过索引访问元素。
    Queue接口:是以队列作为存储结构,集合内部的元素有序排列,仅可以操作头结点元素,无法访问队列中间的元素。
上面三个接口是最普通,最抽象的实现,而在各个集合接口内部,还会有更加具体的表现,衍生出各种不同的额外功能,使开发者能够对比各个集合的优势,择优使用。

Java集合大全

2.1 Set接口

Set接口继承了Collection接口,是一个不包括重复元素的集合,更确切地说,Set 中任意两个元素不会出现 o1.equals(o2),而且 Set 至多只能存储一个 NULL 值元素。

Java集合大全

在Set集合体系中,我们需要着重关注两点:
    存入可变元素时,必须非常小心,因为任意时候元素状态的改变都有不可能使得 Set 内部出现两个相等的元素,即 o1.equals(o2) = true,所以一般不要更改存入 Set 中的元素,否则将会破坏了 equals() 的作用!
    Set 的最大作用就是判重,在项目中最大的作用也是判重!

HashSet

HashSet 底层借助 HashMap 实现,我们可以观察它的多个构造方法,本质上都是 new 一个 HashMap

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    public HashSet() {
        this.map = new HashMap();
    }
    public HashSet(int initialCapacity, float loadFactor) {
        this.map = new HashMap(initialCapacity, loadFactor);
    }
    public HashSet(int initialCapacity) {
        this.map = new HashMap(initialCapacity);
    }
}

我们可以观察add()方法和remove()方法是如何将 HashSet 的操作嫁接到 HashMap 的。

private static final Object PRESENT = new Object(); 
public boolean add(E e) { 
   return this.map.put(e, PRESENT) == null; 
} 
public boolean remove(Object o) { 
   return this.map.remove(o) == PRESENT; 
}

HashMap 的 value 值,使用HashSet的开发者只需关注于需要插入的 key,屏蔽了 HashMap 的 value

HashSet 在 HashMap 基础上实现,所以很多地方可以联系到 HashMap:
    底层数据结构:HashSet 也是采用数组 + 链表 + 红黑树实现
    线程安全性:由于采用 HashMap 实现,而 HashMap 本身线程不安全,在HashSet 中没有添加额外的同步策略,所以 HashSet 也线程不安全
    存入 HashSet 的对象的状态最好不要发生变化,因为有可能改变状态后,在集合内部出现两个元素o1.equals(o2),破坏了 equals()的语义。

LinkedHashSet

LinkedHashSet 的代码少的可怜,如下:  

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    public LinkedHashSet() {
        super(16, .75f, true);
    }
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

关于 LinkedHashSet 需要注意几个地方:
        它继承了 HashSet,而 HashSet 默认是采用 HashMap 存储数据的,但是 LinkedHashSet 调用父类构造方法初始化 map 时是 LinkedHashMap 而不是 HashMap,这个要额外注意一下;
        由于 LinkedHashMap 不是线程安全的,且在 LinkedHashSet 中没有添加额外的同步策略,所以 LinkedHashSet 集合也不是线程安全的。

TreeMap

TreeSet 是基于 TreeMap 的实现,所以存储的元素是有序的,底层的数据结构是数组 + 红黑树。

Java集合大全

而元素的排列顺序有2种,和 TreeMap 相同:自然排序和定制排序,常用的构造方法已经在下面展示出来了,TreeSet 默认按照自然排序,如果需要定制排序,需要传入Comparator。

public TreeSet() { 
    this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

对 TreeSet 介绍了它的主要实现方式和应用场景,有几个值得注意的点。
    TreeSet 的所有操作都会转换为对 TreeMap 的操作,TreeMap 采用红黑树实现,任意操作的平均时间复杂度为 O(logN);
    TreeSet 是一个线程不安全的集合;
    TreeSet 常应用于对不重复的元素定制排序,例如玩家战力排行榜。

2.2 List

List 接口直接继承 Collection 接口,它定义为可以存储重复元素的集合,并且元素按照插入顺序有序排列,且可以通过索引访问指定位置的元素。常见的实现有:ArrayList、LinkedList、Vector和Stack。

AbstractList 和 AbstractSequentialList

AbstractList 抽象类实现了 List 接口,其内部实现了所有的 List 都需具备的功能,子类可以专注于实现自己具体的操作逻辑。

AbstractSequentialList 抽象类继承了 AbstractList,在原基础上限制了访问元素的顺序只能够按照顺序访问,而不支持随机访问,如果需要满足随机访问的特性,则继承 AbstractList。子类 LinkedList 使用链表实现,所以仅能支持顺序访问,顾继承了 AbstractSequentialList而不是 AbstractList。

// 查找元素 o 第一次出现的索引位置
public int indexOf(Object o)
// 查找元素 o 最后一次出现的索引位置
public int lastIndexOf(Object o)
//···

Vector 和 Stack

Vector 在现在已经是一种过时的集合了,包括继承它的 Stack 集合也如此,它们被淘汰的原因都是因为性能低下。

JDK 1.0 时代,ArrayList 还没诞生,大家都是使用 Vector 集合,但由于 Vector 的每个操作都被 synchronized 关键字修饰,即使在线程安全的情况下,仍然进行无意义的加锁与释放锁,造成额外的性能开销,做了无用功。

在 JDK 1.2 时,Collection 家族出现了,它提供了大量高性能、适用於不同场合的集合,而 Vector 也是其中一员,但由于 Vector 在每个方法上都加了锁,由于需要兼容许多老的项目,很难在此基础上优化Vector了,所以渐渐地也就被历史淘汰了。
现在,在线程安全的情况下,不需要选用 Vector 集合,取而代之的是 ArrayList 集合;在并发环境下,出现了 CopyOnWriteArrayList,Vector 完全被弃用了。

Stack是一种后入先出(LIFO)型的集合容器,如图中所示,大雄是最后一个进入容器的,top指针指向大雄,那么弹出元素时,大雄也是第一个被弹出去的。
Stack 继承了 Vector 类,提供了栈顶的压入元素操作(push)和弹出元素操作(pop),以及查看栈顶元素的方法(peek)等等,但由于继承了 Vector,正所谓跟错老大没福报,Stack 也渐渐被淘汰了。
取而代之的是后起之秀 Deque接口,其实现有 ArrayDeque,该数据结构更加完善、可靠性更好,依靠队列也可以实现LIFO的栈操作,所以优先选择 ArrayDeque 实现栈。

ArrayList

ArrayList 以数组作为存储结构,它是线程不安全的集合;具有查询快、在数组中间或头部增删慢的特点,所以它除了线程不安全这一点,其余可以替代Vector,而且线程安全的 ArrayList 可以使用 CopyOnWriteArrayList代替 Vector。

Java集合大全

关于 ArrayList 有几个重要的点需要注意的:
    具备随机访问特点,访问元素的效率较高,ArrayList 在频繁插入、删除集合元素的场景下效率较低。
    底层数据结构:ArrayList 底层使用数组作为存储结构,具备查找快、增删慢的特点
    线程安全性:ArrayList 是线程不安全的集合
    ArrayList 首次扩容后的长度为 10,调用 add() 时需要计算容器的最小容量。可以看到如果数组elementData为空数组,会将最小容量设置为10,之后会将数组长度完成首次扩容到 10。

// new ArrayList 时的默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 计算该容器应该满足的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

集合从第二次扩容开始,数组长度将扩容为原来的 1.5 倍,即:newLength = oldLength * 1.5

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList

LinkedList 底层采用双向链表数据结构存储元素,由于链表的内存地址非连续,所以它不具备随机访问的特点,但由于它利用指针连接各个元素,所以插入、删除元素只需要操作指针,不需要移动元素,故具有增删快、查询慢的特点。它也是一个非线程安全的集合。

Java集合大全

由于以双向链表作为数据结构,它是线程不安全的集合;存储的每个节点称为一个Node,下图可以看到 Node 中保存了next和prev指针,item是该节点的值。在插入和删除时,时间复杂度都保持为 O(1)

关于 LinkedList,除了它是以链表实现的集合外,还有一些特殊的特性需要注意的。
    优势:LinkedList 底层没有扩容机制,使用双向链表存储元素,所以插入和删除元素效率较高,适用于频繁操作元素的场景
    劣势:LinkedList 不具备随机访问的特点,查找某个元素只能从 head 或 tail 指针一个一个比较,所以查找中间的元素时效率很低
    查找优化:LinkedList 查找某个下标 index 的元素时做了优化,若 index > (size / 2),则从 head 往后查找,否则从 tail 开始往前查找,代码如下所示:

LinkedList.Node<E> node(int index) {
    LinkedList.Node x;
    int i;
    if (index < this.size >> 1) { // 查找的下标处于链表前半部分则从头找
        x = this.first;
        for(i = 0; i < index; ++i) { x = x.next; }
        return x;
    } else { // 查找的下标处于数组的后半部分则从尾开始找
        x = this.last;
        for(i = this.size - 1; i > index; --i) { x = x.prev; }
        return x;
    }
}

双端队列:使用双端链表实现,并且实现了 Deque 接口,使得 LinkedList 可以用作双端队列。下图可以看到 Node 是集合中的元素,提供了前驱指针和后继指针,还提供了一系列操作头结点和尾结点的方法,具有双端队列的特性。

LinkedList 集合最让人树枝的是它的链表结构,但是我们同时也要注意它是一个双端队列型的集合。

Deque<Object> deque = new LinkedList<>();

Queue

Queue队列,在 JDK 中有两种不同类型的集合实现:单向队列(AbstractQueue) 和 双端队列(Deque)。

Java集合大全

Queue 中提供了两套增加、删除元素的 API,当插入或删除元素失败时,会有两种不同的失败处理策略。

方法及失败策略  插入方法  删除方法   查找方法
 抛出异常  add()  remove()  get()
 返回默认值  offer()  poll()  peek()

选取哪种方法的决定因素:插入和删除元素失败时,希望抛出异常还是返回布尔值,

add() 和 offer() 对比:
在队列长度大小确定的场景下,队列放满元素后,添加下一个元素时,add() 会抛出 IllegalStateException异常,而 offer() 会返回 false 。
remove() 和 poll() 对比:
在队列为空的场景下, remove() 会抛出 NoSuchElementException异常,而 poll() 则返回 null 。
get()和peek()对比:
在队列为空的情况下,get()会抛出NoSuchElementException异常,而peek()则返回null。

Deque

Deque 接口的实现非常好理解:从单向队列演变为双向队列,内部额外提供双向队列的操作方法即可:

Deque接口额外提供了针对队列的头结点和尾结点操作的方法,而插入、删除方法同样也提供了两套不同的失败策略。除了add()和offer(),remove()和poll()以外,还有get()和peek()出现了不同的策略

ArrayDeque

使用数组实现的双端队列,它是无界的双端队列,最小的容量是8(JDK 1.8)。在 JDK 11 看到它默认容量已经是 16了。ArrayDeque 在日常使用得不多,值得注意的是它与 LinkedList 的对比:LinkedList 采用链表实现双端队列,而 ArrayDeque 使用数组实现双端队列。

/**
 * The minimum capacity that we'll use for a newly created deque.
 * Must be a power of 2.
 */
private static final int MIN_INITIAL_CAPACITY = 8;

由于双端队列只能在头部和尾部操作元素,所以删除元素和插入元素的时间复杂度大部分都稳定在 O(1) ,除非在扩容时会涉及到元素的批量复制操作。但是在大多数情况下,使用它时应该指定一个大概的数组长度,避免频繁的扩容。

个人观点:链表的插入、删除操作涉及到指针的操作,我个人认为作者是觉得数组下标的移动要比指针的操作要廉价,而且数组采用连续的内存地址空间,而链表元素的内存地址是不连续的,所以数组操作元素的效率在寻址上会比链表要快。请批判看待观点。

PriorityQueue

PriorityQueue 基于优先级堆实现的优先级队列,而堆是采用数组实现:

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

文档中的描述告诉我们:该数组中的元素通过传入 Comparator 进行定制排序,如果不传入Comparator时,则按照元素本身自然排序,但要求元素实现了Comparable接口,所以 PriorityQueue 不允许存储 NULL 元素。
PriorityQueue 应用场景:元素本身具有优先级,需要按照优先级处理元素

        例如VIP玩家与普通玩家,VIP 等级越高的玩家越优先安排玩耍,减少VIP玩家流失。

public static void main(String[] args) {
    Player vip1 = new Player("范仲淹", 1);
    Player vip3 = new Player("窦宪", 2);
    Player vip4 = new Player("弘历", 4);
    Player vip2 = new Player("苏定方", 1);
    Player p1 = new Player("王阳明", 0);
    Player p2 = new Player("赵孟頫", 0);
    // 根据VIP等级降序
    PriorityQueue<Player> queue = new PriorityQueue<>((o1, o2) ->  o2.getScore().compareTo(o1.getScore()));
    queue.add(vip1);queue.add(vip4);queue.add(vip3);
    queue.add(p1);queue.add(p2);queue.add(vip2);
    while (!queue.isEmpty()) {
        Player s1 = queue.poll();
        System.out.println(s1.getName() + "进入游戏; " + "VIP等级: " + s1.getScore());
    }
}
 public static class Player implements Comparable<Player> {
     private String name;
     private Integer score;
     public Player(String name, Integer score) {
         this.name = name;
         this.score = score;
     }
     @Override
     public int compareTo(Player o) {
         return this.score.compareTo(o.getScore());
     }
 }

结果如下:

弘历进入游戏; VIP等级: 4
窦宪进入游戏; VIP等级: 2
范仲淹进入游戏; VIP等级: 1
苏定方进入游戏; VIP等级: 1
王阳明进入游戏; VIP等级: 0
赵孟頫进入游戏; VIP等级: 0

VIP 等级越高(优先级越高)就越优先安排玩(优先处理),类似这种有优先级的场景还有非常多,各位可以发挥自己的想象力。

PriorityQueue 总结:
       PriorityQueue 是基于优先级堆实现的优先级队列,而堆是用数组维护的
       PriorityQueue 适用于元素按优先级处理的业务场景,例如用户在请求人工客服需要排队时,根据用户的VIP等级进行 插队 处理,等级越高,越先安排客服。

四、下面来个大总结:

数据类型  插入删除的时间复杂度  查询时间复杂度  底层数据结构  是否线程安全 
 Vector  O(N)  O(1)  数组  是
 ArrayList  O(N)  O(1)  数组  否
 LinkedList  O(1)    O(N)  双向链表  否
 HashSet  O(1)    O(1)  数组+链表+红黑树  否
 TreeSet  O(LogN)  O(LogN)  红黑树  否
 LingkedHashSet  O(1)  O(1)~ O(N)  数组+链表+红黑树  否
 ArrayDeque  O(N)  O(1)  数组  否
 PriorityQueue  O(LogN)  O(LogN)  堆(数组)  否
 HashMap  O(1)~ O(N)  O(1)~ O(N)  数组+链表+红黑树  否
 TreeMap  O(LogN)  O(LogN)   数组+红黑树  否
 HashTable  O(1) / O(N)  O(1) / O(N)    数组+链表  是

 

 

 

 

  

 


程序员灯塔 , 版权所有
转载请注明原文链接:https://www.wangt.cc/2020/09/java%e9%9b%86%e5%90%88%e5%a4%a7%e5%85%a8/
喜欢 (0)