Java集合简介⁍

Java的java.util包主要提供了以下三种类型的集合：

  • List：一种有序列表的集合，例如，按索引排列的Student的List；
  • Set：一种保证没有重复元素的集合，例如，所有无重复名称的Student的Set；
  • Map：一种通过键值（key-value）查找的映射表集合，例如，根据Student的name查找对应Student的Map。

几个特点：

  1. 实现了接口和实现类相分离，例如，有序表的接口是List，具体的实现类有ArrayList，LinkedList等
  2. 支持泛型，我们可以限制在一个集合中只能放入同一种数据类型的元素

Java集合使用统一的Iterator遍历，尽量不要使用遗留接口。

java集合框架[1]⁍

img

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

  • **接口：**是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象
  • **实现（类）：**是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
  • **算法：**是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。

集合框架体系如图所示⁍

img

Java 集合框架提供了一套性能优良，使用方便的接口和类，java集合框架位于java.util包中， 所以当使用集合框架的时候需要进行导包。

集合接口⁍

集合框架定义了一些接口。本节提供了每个接口的概述：

序号 接口描述
1 Collection 接口
Collection 是最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 的元素, Java不提供直接继承自Collection的类，只提供继承于的子接口(如List和set)。Collection 接口存储一组不唯一，无序的对象。
2 List 接口
List接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。List 接口存储一组不唯一，有序（插入顺序）的对象。
3 Set
Set 具有与 Collection 完全一样的接口，只是行为上不同，**Set 不保存重复的元素。**Set 接口存储一组唯一，无序的对象。
4 SortedSet
继承于Set保存有序的集合。
5 Map
Map 接口存储一组键值对象，提供key（键）到value（值）的映射。
6 Map.Entry
描述在一个Map中的一个元素（键/值对）。是一个 Map 的内部接口。
7 SortedMap
继承于 Map，使 Key 保持在升序排列。
8 Enumeration
这是一个传统的接口和定义的方法，通过它可以枚举（一次获得一个）对象集合中的元素。这个传统接口已被迭代器取代。

Set和List的区别⁍

  1. Set 接口实例存储的是无序的，不重复的数据。List 接口实例存储的是有序的，可以重复的元素。
  2. Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>
  3. List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变 <实现类有ArrayList,LinkedList,Vector> 。

集合实现类（集合类）⁍

Java提供了一套实现了Collection接口的标准集合类。其中一些是具体类，这些类可以直接拿来使用，而另外一些是抽象类，提供了接口的部分实现。

标准集合类汇总于下表：

序号 类描述
1 AbstractCollection 实现了大部分的集合接口。
2 AbstractList 继承于AbstractCollection 并且实现了大部分List接口。
3 AbstractSequentialList 继承于 AbstractList ，提供了对数据元素的链式访问而不是随机访问。
4 LinkedList 该类实现了List接口，允许有null（空）元素。主要用于创建链表数据结构，该类没有同步方法，如果多个线程同时访问一个List，则必须自己实现访问同步，解决方法就是在创建List时候构造一个同步的List。例如：List list=Collections.synchronizedList(newLinkedList(...));LinkedList 查找效率低。
5 ArrayList 该类也是实现了List的接口，实现了可变大小的数组，随机访问和遍历元素时，提供更好的性能。该类也是非同步的,在多线程的情况下不要使用。ArrayList 增长当前长度的50%，插入删除效率低。
6 AbstractSet 继承于AbstractCollection 并且实现了大部分Set接口。
7 HashSet 该类实现了Set接口，不允许出现重复元素，不保证集合中元素的顺序，允许包含值为null的元素，但最多只能一个。
8 LinkedHashSet 具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。
9 TreeSet 该类实现了Set接口，可以实现排序等功能。
10 AbstractMap 实现了大部分的Map接口。
11 HashMap HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。 该类实现了Map接口，根据键的HashCode值存储数据，具有很快的访问速度，最多允许一条记录的键为null，不支持线程同步。
12 TreeMap 继承了AbstractMap，并且使用一颗树。
13 WeakHashMap 继承AbstractMap类，使用弱密钥的哈希表。
14 LinkedHashMap 继承于HashMap，使用元素的自然顺序对元素进行排序.
15 IdentityHashMap 继承AbstractMap类，比较文档时使用引用相等。

在前面的教程中已经讨论通过java.util包中定义的类，如下所示：

序号 类描述
1 Vector 该类和ArrayList非常相似，但是该类是同步的，可以用在多线程的情况，该类允许设置默认的增长长度，默认扩容方式为原来的2倍。
2 Stack 栈是Vector的一个子类，它实现了一个标准的后进先出的栈。
3 Dictionary Dictionary 类是一个抽象类，用来存储键/值对，作用和Map类相似。
4 Hashtable Hashtable 是 Dictionary(字典) 类的子类，位于 java.util 包中。
5 Properties Properties 继承于 Hashtable，表示一个持久的属性集，属性列表中每个键及其对应值都是一个字符串。
6 BitSet 一个Bitset类创建一种特殊类型的数组来保存位值。BitSet中数组大小会随需要增加。

集合算法⁍

集合框架定义了几种算法，可用于集合和映射。这些算法被定义为集合类的静态方法。

在尝试比较不兼容的类型时，一些方法能够抛出 ClassCastException异常。当试图修改一个不可修改的集合时，抛出UnsupportedOperationException异常。

集合定义三个静态的变量：EMPTY_SET，EMPTY_LIST，EMPTY_MAP的。这些变量都不可改变。

序号 算法描述
1 Collection Algorithms 这里是一个列表中的所有算法实现。

List⁍

List<E>接口，可以看到几个主要的接口方法：

  • 在末尾添加一个元素：boolean add(E e)
  • 在指定索引添加一个元素：boolean add(int index, E e)
  • 删除指定索引的元素：E remove(int index)
  • 删除某个元素：boolean remove(Object e)
  • 获取指定索引的元素：E get(int index)
  • 返回某个元素索引（不存在则返回-1）：int indexOf(Objext o)
  • 获取链表大小（包含元素的个数）：int size()
  • 判断List是否包含某个指定元素：boolean contains(Object o)
  • 修改元素：E set(int index, E e)

List (Java SE 11 & JDK 11 ) (runoob.com)

ArrayList (Java SE 11 & JDK 11 ) (runoob.com)

LinkedList (Java SE 11 & JDK 11 ) (runoob.com)

ArrayList是List的数组实现，LinkedList则是List的链表实现

ArrayList LinkedList
获取指定元素 速度很快 需要从头开始查找元素
添加元素到末尾 速度很快 速度很快
在指定位置添加/删除 需要移动元素 不需要移动元素
内存占用 少 较大

通常情况下，我们总是优先使用ArrayList。

import java.util.List;

import java.util.ArrayList;

1
List<String> list = new ArrayList<>();

List的特点⁍

  • 允许添加重复元素
  • 允许添加null

创建List⁍

通过给定元素快速创建List：List.of(...)（不接受null）

1
List<Integer> list = List.of(1, 2, 5);

遍历List⁍

  • （不推荐）用for循环根据索引配合get(int)方法遍历

    get(int)方法只有ArrayList的实现是高效的，换成LinkedList后，索引越大，访问速度越慢

  • 坚持使用迭代器Iterator来访问List。

    • Iterator对象有两个方法：boolean hasNext()判断是否有下一个元素，E next()返回下一个元素。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      import java.util.Iterator;
      import java.util.List;

      public class Main {
          public static void main(String[] args) {
              List<String> list = List.of("apple", "pear", "banana");
              for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
                  String s = it.next();
                  System.out.println(s);
              }
          }
      }

    • 常用Java的for each循环本身就可以帮我们使用Iterator遍历。

List和Array转换⁍

1
List<Integer> list = List.of(12, 34, 56);

把List变为Array有三种方法：

  1. (很少用)调用toArray()方法直接返回一个Object[]数组（会丢失类型信息）

    1
    Object[] array = list.toArray();

  2. 给toArray(T[])传入一个类型相同的Array，List内部自动把元素复制到传入的Array中

    1
    2
    Integer[] array = list.toArray(new Integer[3]);
    Integer[] array = list.toArray(new Integer[list.size()]);

  3. 函数式写法，通过List接口定义的T[] toArray(IntFunction<T[]> generator)方法：

    1
    Integer[] array = list.toArray(Integer[]::new);

把Array变为List

  1. 通过List.of(T...)方法：

    1
    List<Integer> list = List.of(array);

  2. 对于JDK 11之前的版本，可以使用Arrays.asList(T...)方法把数组转换成List

返回的List不一定就是ArrayList或者LinkedList，因为List只是一个接口，如果我们调用List.of()，它返回的是一个只读List（对只读List调用add()、remove()方法会抛出UnsupportedOperationException。）

问题：⁍

怎么初始化ArrayList

Array变回List怎么才能写

直接打印List(调试用)System.out.println(list.toString());

编写equals方法⁍

List内部并不是通过==判断两个元素是否相等，而是使用equals()方法判断两个元素是否相等。

要正确使用List的contains()、indexOf()这些方法，放入的实例必须正确覆写equals()方法，否则，放进去的实例，查找不到。

例子：Person类没有覆写equals()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Person> list = List.of(
            new Person("Xiao Ming"),
            new Person("Xiao Hong"),
            new Person("Bob")
        );
        System.out.println(list.contains(new Person("Bob"))); // false
    }
}

class Person {
    String name;
    public Person(String name) {
        this.name = name;
    }
}

编写equals⁍

如果不在List中查找元素，就不必覆写equals()方法。

equals()方法要求我们必须满足以下条件：

  • **自反性（Reflexive）：**对于非null的x来说，x.equals(x)必须返回true；
  • **对称性（Symmetric）：**对于非null的x和y来说，如果x.equals(y)为true，则y.equals(x)也必须为true；
  • **传递性（Transitive）：**对于非null的x、y和z来说，如果x.equals(y)为true，y.equals(z)也为true，那么x.equals(z)也必须为true；
  • **一致性（Consistent）：**对于非null的x和y来说，只要x和y状态不变，则x.equals(y)总是一致地返回true或者false；
  • **对null的比较：**即x.equals(null)永远返回false。

equals()方法的正确编写方法：

  1. 先确定实例“相等”的逻辑，即哪些字段相等，就认为实例相等；
  2. 用instanceof判断传入的待比较的Object是不是当前类型，如果是，转型继续比较，否则，返回false；
  3. 对引用类型用Objects.equals()比较，对基本类型直接用==比较。import java.util.Objects
1
2
3
4
5
6
7
8
9
10
import java.util.Objects

@Override
public boolean equals(Object o) {
    if (o instanceof Person) {
        Person p = (Person) o;
        return Objects.equals(this.name, p.name) && this.age == p.age;
    }
    return false;
}

使用Objects.equals()比较两个引用类型是否相等的目的是省去了判断null的麻烦。两个引用类型都是null时它们也是相等的。

如果不调用List的contains()、indexOf()这些方法，那么放入的元素就不需要实现equals()方法。

问题

模式变量？

用IDEA编写的时候，提示可以把p换成模式变量，即写为

1
o instanceof Person p

Map⁍

import java.util.HashMap;

import java.util.Map;

Map (Java SE 11 & JDK 11 ) (runoob.com)

初始化(Map也是一个接口，最常用的实现类是HashMap。)

1
Map<String, Integer> map = new HashMap<>();
变量和类型 方法 描述
int size() 返回此映射中键 - 值映射的数量。
V put(K key, V value) 将指定的值与此映射中的指定键相关联（可选操作）。
void putAll(Map<? extends K,? extends V> m) 将指定映射中的所有映射复制到此映射（可选操作）。
V get(Object key) 返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
Collection<V> values() 返回此映射中包含的值的Collection视图。
Set<K> keySet() 返回此映射中包含的键的Set视图。
V get(Object key) 返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射的Set视图。
boolean isEmpty() 如果此映射不包含键 - 值映射，则返回 true 。
default V replace(K key, V value) 仅当指定键当前映射到某个值时，才替换该条目的条目。
default boolean replace(K key, V oldValue, V newValue) 仅当前映射到指定值时，才替换指定键的条目。
V remove(Object key) 如果存在，则从该映射中移除键的映射（可选操作）。
default boolean remove(Object key, Object value) 仅当指定键当前映射到指定值时才删除该条目的条目。
boolean containsKey(Object key) 如果此映射包含指定键的映射，则返回 true 。
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true 。

Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉。？

嵌套类？Map.Entry⁍

1
public static interface Map.Entry<K,V>

Map.Entry (Java SE 11 & JDK 11 ) (runoob.com)

映射条目（键值对）。 Map.entrySet方法返回地图的集合视图，其元素属于此类。这些Map.Entry对象仅在迭代期间有效; 更正式地说，如果在迭代器返回条目后修改了支持映射，则映射条目的行为是未定义的，除非通过映射条目上的setValue操作。

变量和类型 方法 描述
boolean equals(Object o) 将指定对象与此条目进行比较以获得相等性。
K getKey() 返回与此条目对应的键。
V getValue() 返回与此条目对应的值。
V setValue(V value) 用指定的值替换此条目对应的值（可选操作）。

遍历Map⁍

  • 使用for each循环遍历Map实例的keySet()方法返回的Set集合

  • 使用for each循环遍历Map对象的entrySet()集合，它包含每一个key-value映射

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    import java.util.HashMap;
    import java.util.Map;

    public class Main {
        public static void main(String[] args) {
            Map<String, Integer> map = new HashMap<>();
            map.put("apple", 123);
            map.put("pear", 456);
            map.put("banana", 789);
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                String key = entry.getKey();
                Integer value = entry.getValue();
                System.out.println(key + " = " + value);
            }
        }
    }

遍历Map时，不可假设输出的key是有序的！

运用实例⁍

根据name查找score，并利用Map充当缓存。

先在Map中找，没有再去List中找，找到了添加到Map中，相当于实现了cache，提高之后的查找效率

编写equals和hashCode⁍

正确使用Map必须保证：

  1. 作为key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
  2. 作为key的对象还必须正确覆写hashCode()方法，且hashCode()方法要严格遵循以下规范：
  • 如果两个对象相等，则两个对象的hashCode()必须相等；
  • 如果两个对象不相等，则两个对象的hashCode()尽量不要相等。

即对应两个实例a和b：

  • 如果a和b相等，那么a.equals(b)一定为true，则a.hashCode()必须等于b.hashCode()；
  • 如果a和b不相等，那么a.equals(b)一定为false，则a.hashCode()和b.hashCode()尽量不要相等。

上述第一条规范是正确性，必须保证实现，否则HashMap不能正常工作。

而第二条如果尽量满足，则可以保证查询效率，因为不同的对象，如果返回相同的hashCode()，会造成Map内部存储冲突，使存取的效率下降。

⭐借助Objects.hash()来计算：

1
2
3
int hashCode() {
    return Objects.hash(firstName, lastName, age);
}

所以，编写equals()和hashCode()遵循的原则是：

  • equals()用到的用于比较的每一个字段，都必须在hashCode()中用于计算；
  • equals()中没有使用到的字段，绝不可放在hashCode()中计算。

另外注意，对于放入HashMap的value对象，没有任何要求。

  • HashMap初始化时默认的数组大小只有16，任何key，无论它的hashCode()有多大，都可以简单地通过：

    1
    int index = key.hashCode() & 0xf; // 0xf = 15

    把索引确定在0～15，即永远不会超出数组范围，上述算法只是一种最简单的实现。

  • 添加超过一定数量的key-value时，HashMap会在内部自动扩容，每次扩容一倍，即长度为16的数组扩展为长度32，相应地，需要重新确定hashCode()计算的索引位置。

  • （哈希冲突）使用Map的时候，只要key不相同，它们映射的value就互不干扰。存在不同的key，映射到相同的hashCode()的时候，在HashMap的数组中，实际存储的不是一个Person实例，而是一个List，它包含两个Entry，分别对应两个key的映射

    JDK中源码:

    1
    2
    3
    4
    5
    6
    if(e.hash == hash && 
       (
           (k = e.key) == key || 
           (key != null && key.equals(k))
       )
      ){ops;}

    重写equals方法，是为了解决hash冲突，如果两个key的hash值相同，就会调用equals方法，比较key值是否相同，在存储时：如果equals结果相同就覆盖更新value值，如果不同就用List他们都存储起来。在取出来是：如果equals结果相同就返回当前value值，如果不同就遍历List中下一个元素。即要key与hash同时匹配才会认为是同一个key。

使用EnumMap⁍

如果Map的key是enum类型，推荐使用EnumMap，既保证速度，也不浪费空间。

使用EnumMap的时候，根据面向抽象编程的原则，应持有Map接口。

使用TreeMap⁍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
       ┌───┐
       │Map│
       └───┘
         ▲
    ┌────┴─────┐
    │          │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘
               ▲
               │
          ┌─────────┐
          │ TreeMap │
          └─────────┘

SortedMap接口在内部会对Key进行排序，在遍历时严格按照Key的顺序（String类型就是默认按字母排序）在遍历，最常用的实现类是TreeMap；

出于“排序”的要求，放入的Key必须实现Comparable接口。

如果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个自定义排序算法

1
2
3
4
5
Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
    public int compare(Person p1, Person p2) {
        return p1.name.compareTo(p2.name);
    }
});

Comparator接口要求实现一个比较方法，它负责比较传入的两个元素a和b，如果a<b，则返回负数，通常是-1，如果a==b，则返回0，如果a>b，则返回正数，通常是1。

可以自定义compare方法，但是在两个Key相等时，必须返回0。

使用Properties配置文件⁍

Java默认配置文件以.properties为扩展名，每行以key=value表示，以#课开头的是注释。

读取配置文件⁍

用Properties读取配置文件，一共有三步：

  1. 创建Properties实例；
  2. 调用load()读取文件；
  3. 调用getProperty()获取配置。

如果key不存在，将返回null。我们还可以提供一个默认值，这样，当key不存在的时候，就返回默认值。

可以从文件系统中读也可以从classpath中读字节流

如果有多个.properties文件，可以反复调用load()读取，后读取的key-value会覆盖已读取的key-value：

1
2
3
Properties props = new Properties();
props.load(getClass().getResourceAsStream("/common/setting.properties"));
props.load(new FileInputStream("C:\\conf\\setting.properties"));

上面的代码演示了Properties的一个常用用法：可以把默认配置文件放到classpath中，然后，根据机器的环境编写另一个配置文件，覆盖某些默认的配置。

写入配置文件⁍

用setProperty()修改Properties实例

用store()方法写入配置文件

1
2
3
4
Properties props = new Properties();
props.setProperty("url", "http://www.liaoxuefeng.com");
props.setProperty("language", "Java");
props.store(new FileOutputStream("C:\\conf\\setting.properties"), "这是写入的properties注释");

编码⁍

由于load(InputStream)默认总是以ASCII编码读取字节流，所以会导致读到乱码。我们需要用另一个重载方法load(Reader)读取：

1
2
Properties props = new Properties();
props.load(new FileReader("settings.properties", StandardCharsets.UTF_8));

就可以正常读取中文。InputStream和Reader的区别是一个是字节流，一个是字符流。字符流在内存中已经以char类型表示了，不涉及编码问题。

Set⁍

import java.util.*;

Set (Java SE 11 & JDK 11 ) (runoob.com)

Set用于存储不重复的元素集合，它主要提供以下几个方法：

  • 将元素添加进Set<E>：boolean add(E e)
  • 将元素从Set<E>删除：boolean remove(Object e)
  • 判断是否包含元素：boolean contains(Object e)
变量和类型 方法 描述
boolean add(E e) 如果指定的元素尚不存在，则将其添加到此集合（可选操作）。
boolean addAll(Collection<? extends E> c) 如果指定集合中的所有元素尚未存在（可选操作），则将其添加到此集合中。
boolean contains(Object o) 如果此set包含指定的元素，则返回 true 。
boolean remove(Object o) 如果存在，则从该集合中移除指定的元素（可选操作）。
int size() 返回此集合中的元素数（基数）。
Object[] toArray() 返回包含此set中所有元素的数组。
<T> T[] toArray(T[] a) 返回一个包含此set中所有元素的数组; 返回数组的运行时类型是指定数组的运行时类型。

经常用Set用于去除重复元素。

因为放入Set的元素和Map的key类似，都要正确实现equals()和hashCode()方法，否则该元素无法正确地放入Set。

实现类⁍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
       ┌───┐
       │Set│
       └───┘
         ▲
    ┌────┴─────┐
    │          │
┌───────┐ ┌─────────┐
│HashSet│ │SortedSet│
└───────┘ └─────────┘
               ▲
               │
          ┌─────────┐
          │ TreeSet │
          └─────────┘

HashSet仅仅是对HashMap的一个简单封装

SortedSet接口则保证元素是有序的

  • HashSet是无序的，因为它实现了Set接口，并没有实现SortedSet接口；
  • TreeSet是有序的，因为它实现了SortedSet接口。

Queue⁍

也是一个接口，可以用LinkedList实现

import java.util.LinkedList

import java.util.Queue

Queue (Java SE 11 & JDK 11 ) (runoob.com)

变量和类型 方法 描述
boolean add(E e) 如果可以在不违反容量限制的情况下立即执行此操作，则将指定的元素插入此队列，成功时返回 true ，如果当前没有空间，则抛出 IllegalStateException 。
E element() 检索但不删除此队列的头部。
boolean offer(E e) 如果可以在不违反容量限制的情况下立即执行此操作，则将指定的元素插入此队列。
E peek() 检索但不删除此队列的头部，如果此队列为空，则返回 null 。
E poll() 检索并删除此队列的头部，如果此队列为空，则返回 null 。
E remove() 检索并删除此队列的头部。

注意到添加、删除和获取队列元素总是有两个方法，这是因为在添加或获取元素失败时，这两个方法的行为是不同的。我们用一个表格总结如下：

throw Exception 返回false或null
添加元素到队尾 add(E e) boolean offer(E e)
取队首元素并删除 E remove() E poll()
取队首元素但不删除 E element() E peek()

要避免把null添加到队列。

PriorityQueue⁍

PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。

根据Comparable接口的实现，根据元素的排序顺序决定“优先级”。

对于没有实现Comparable接口的元素，可以提供一个Comparator对象来自定义排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Queue<User> q = new PriorityQueue<>(new UserComparator());
		// 添加3个元素到队列:
		q.offer(new User("Bob", "A1"));
		q.offer(new User("Alice", "A3"));
		q.offer(new User("Alice", "A2"));
		q.offer(new User("Alice", "A112"));
		q.offer(new User("Boss", "V1"));
		q.offer(new User("Boss", "A10"));
		q.offer(new User("Boss", "A999"));
		q.offer(new User("Boss", "A88"));
		System.out.println(q.poll()); // Boss/V1
		System.out.println(q.poll()); // Bob/A1
		System.out.println(q.poll()); // Alice/A2
		System.out.println(q.poll()); // Alice/A2
		System.out.println(q.poll()); // Alice/A2
		System.out.println(q.poll()); // Alice/A2
		System.out.println(q.poll()); // Alice/A2
		System.out.println(q.poll()); // Alice/A2
		System.out.println(q.poll()); // null,因为队列为空
	}
}

class UserComparator implements Comparator<User> {
	public int compare(User u1, User u2) {
		// 如果两人的号都是A开头或者都是V开头,比较号的大小:
		if (u1.number.charAt(0) == u2.number.charAt(0)) {
			// 相同的字母开头，截取后面的值
			int v1 = u1.number.length();
			int v2 = u2.number.length();
			String n1 = u1.number.substring(1, v1);
			String n2 = u2.number.substring(1, v2);
			// 负值，n1排前面
			return Integer.parseInt(n1) - Integer.parseInt(n2);
		}
		if (u1.number.charAt(0) == 'V') {
			// u1的号码是V开头,优先级高:
			return -1;
		} else {
			return 1;
		}
	}
}

class User {
	public final String name;
	public final String number;

	public User(String name, String number) {
		this.name = name;
		this.number = number;
	}

	public String toString() {
		return name + "/" + number;
	}
}

Deque⁍

Java集合提供了接口Deque来实现一个双端队列，它的功能是：

  • 既可以添加到队尾，也可以添加到队首；
  • 既可以从队首获取，又可以从队尾获取。
Queue Deque
添加元素到队尾 add(E e) / offer(E e) addLast(E e) / offerLast(E e)
取队首元素并删除 E remove() / E poll() E removeFirst() / E pollFirst()
取队首元素但不删除 E element() / E peek() E getFirst() / E peekFirst()
添加元素到队首 无 addFirst(E e) / offerFirst(E e)
取队尾元素并删除 无 E removeLast() / E pollLast()
取队尾元素但不删除 无 E getLast() / E peekLast()

Deque接口实际上扩展自Queue，但总是调用xxxFirst()/xxxLast()以便与Queue的方法区分开

Stack⁍

用Deque可以实现Stack的功能：

  • 把元素压栈：push(E)/addFirst(E)；
  • 把栈顶的元素“弹出”：pop()/removeFirst()；
  • 取栈顶元素但不弹出：peek()/peekFirst()。

有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口

计算中缀表达式 把带变量的中缀表达式编译为后缀表达式，再进行计算

JAVA用栈计算中缀表达式（详解）_爱前端的小菜的博客-CSDN博客_java计算中缀表达式

用的笨方法，不太通用 (liaoxuefeng.com)

Iterator⁍

使用Iterator - 廖雪峰的官方网站 (liaoxuefeng.com)

如果我们自己编写了一个集合类，想要使用for each循环，只需满足以下条件：

  • 集合类实现Iterable接口，该接口要求返回一个Iterator对象；
  • 用Iterator对象迭代集合内部数据。

Collections⁍

Collection (Java SE 11 & JDK 11 ) (runoob.com)

变量和类型 方法 描述
boolean add(E e) 确保此集合包含指定的元素（可选操作）。
boolean addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到此集合中（可选操作）。
void clear() 从此集合中删除所有元素（可选操作）。
boolean contains(Object o) 如果此collection包含指定的元素，则返回 true 。
boolean containsAll(Collection<?> c) 如果此集合包含指定集合中的所有元素，则返回 true 。
boolean equals(Object o) 将指定对象与此集合进行比较以获得相等性。
int hashCode() 返回此集合的哈希码值。
boolean isEmpty() 如果此集合不包含任何元素，则返回 true 。
Iterator<E> iterator() 返回此集合中元素的迭代器。
default Stream<E> parallelStream() 以此集合为源返回可能并行的 Stream 。
boolean remove(Object o) 从此集合中移除指定元素的单个实例（如果存在）（可选操作）。
boolean removeAll(Collection<?> c) 删除此集合的所有元素，这些元素也包含在指定的集合中（可选操作）。
default boolean removeIf(Predicate<? super E> filter) 删除此集合中满足给定谓词的所有元素。
boolean retainAll(Collection<?> c) 仅保留此集合中包含在指定集合中的元素（可选操作）。
int size() 返回此集合中的元素数。
default Spliterator<E> spliterator() 在此集合中的元素上创建Spliterator 。
default Stream<E> stream() 返回以此集合为源的顺序 Stream 。
Object[] toArray() 返回包含此集合中所有元素的数组。
default <T> T[] toArray(IntFunction<T[]> generator) 返回包含此集合中所有元素的数组，使用提供的 generator函数分配返回的数组。
<T> T[] toArray(T[] a) 返回一个包含此collection中所有元素的数组; 返回数组的运行时类型是指定数组的运行时类型。

Collections类提供了一组工具方法来方便使用集合类：

  • 创建空集合；
    • 创建空List：List<T> emptyList()
    • 创建空Map：Map<K, V> emptyMap()
    • 创建空Set：Set<T> emptySet()
  • 创建单元素集合；
    • 创建一个元素的List：List<T> singletonList(T o)
    • 创建一个元素的Map：Map<K, V> singletonMap(K key, V value)
    • 创建一个元素的Set：Set<T> singleton(T o)
    • （实际上，使用List.of(T...)更方便，因为它既可以创建空集合，也可以创建单元素集合，还可以创建任意个元素的集合）
  • 创建不可变集合；
    • 封装成不可变List：List<T> unmodifiableList(List<? extends T> list)
    • 封装成不可变Set：Set<T> unmodifiableSet(Set<? extends T> set)
    • 封装成不可变Map：Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m)
  • 排序／洗牌等操作。
    • Collections.sort(list)
    • Collections.shuffle(list)

  1. Java 集合框架 | 菜鸟教程 (runoob.com) ↩︎