通过迭代器删除

通过Iterator删除是 Java 中最古老的方法。主要地，Iterator允许我们迭代（或遍历）集合并删除某些元素。最古老的方法也有一些缺点。首先，根据集合类型的不同，如果多个线程修改集合，那么通过一个Iterator删除很容易发生ConcurrentModificationException。此外，移除并不是所有集合的行为都相同（例如，从LinkedList移除要比从ArrayList移除快，因为前者只是将指针移动到下一个元素，而后者则需要移动元素）。不过，解决方案在捆绑代码中是可用的。

如果您所需要的只是Iterable的大小，那么请考虑以下方法之一：

// for any Iterable
StreamSupport.stream(iterable.spliterator(), false).count();
// for collections
((Collection<?>) iterable).size()

移除通孔集合.removeIf()

从 JDK8 开始，我们可以通过Collection.removeIf()方法将前面的代码缩减为一行代码。此方法依赖于Predicate，如下例所示：

melons.removeIf(t -> t.getWeight() < 3000);

这一次，ArrayList迭代列表并标记为删除那些满足我们的Predicate的元素。此外，ArrayList再次迭代以移除标记的元素并移动剩余的元素。

使用这种方法，LinkedList和ArrayList以几乎相同的方式执行。

通过流删除

从 JDK8 开始，我们可以从集合（Collection.stream()中创建一个Stream，并通过filter(Predicate p)过滤它的元素。过滤器将只保留满足给定Predicate的元件。

最后，我们通过合适的收集器收集这些元素：

List<Melon> filteredMelons = melons.stream()
  .filter(t -> t.getWeight() >= 3000)
  .collect(Collectors.toList());

与其他两个解决方案不同，这个解决方案不会改变原始集合，但它可能会更慢，占用更多内存。

通过`Collectors.partitioningBy()`

有时，我们不想删除与谓词不匹配的元素。我们实际上想要的是基于谓词来分离元素。好吧，这是可以通过Collectors.partitioningBy(Predicate p)实现的。

基本上，Collectors.partitioningBy()将把元素分成两个列表。这两个列表作为值添加到Map。此Map的两个键是true和false：

Map<Boolean, List<Melon>> separatedMelons = melons.stream()
  .collect(Collectors.partitioningBy(
    (Melon t) -> t.getWeight() >= 3000));
List<Melon> weightLessThan3000 = separatedMelons.get(false);
List<Melon> weightGreaterThan3000 = separatedMelons.get(true);

因此，true键用于检索包含与谓词匹配的元素的List，而false键用于检索包含与谓词不匹配的元素的List。

作为奖励，如果我们想检查List的所有元素是否相同，那么我们可以依赖Collections.frequency(Collection c, Object obj)。此方法返回指定集合中等于指定对象的元素数：

boolean allTheSame = Collections.frequency(
  melons, melons.get(0)) == melons.size());

如果allTheSame是true，那么所有元素都是相同的。注意，List中的对象的equals()和hashCode()必须相应地实现。

119 将集合转换为数组

为了将集合转换为数组，我们可以依赖于Collection.toArray()方法。如果没有参数，此方法会将给定集合转换为一个Object[]，如下例所示：

List<String> names = Arrays.asList("ana", "mario", "vio");
Object[] namesArrayAsObjects = names.toArray();

显然，这并不完全有用，因为我们期望的是一个String[]而不是Object[]。这可以通过Collection.toArray(T[] a)实现，如下所示：

String[] namesArraysAsStrings = names.toArray(new String[names.size()]);
String[] namesArraysAsStrings = names.toArray(new String[0]);

从这两种解决方案中，第二种方案更可取，因为我们避免计算集合大小。

但从 JDK11 开始，还有一种方法专门用于此任务，Collection.toArray(IntFunction<T[]> generator)。此方法返回一个包含此集合中所有元素的数组，使用提供的生成器函数分配返回的数组：

String[] namesArraysAsStrings = names.toArray(String[]::new);

除了固定大小可修改的Arrays.asList()之外，我们可以通过of()方法从数组中构建一个不可修改的List/Set：

String[] namesArray = {"ana", "mario", "vio"};
List<String> namesArrayAsList = List.of(namesArray);
Set<String> namesArrayAsSet = Set.of(namesArray);

120 按列表过滤集合

我们在应用中遇到的一个常见问题是用一个List来过滤一个Collection。主要是从一个巨大的Collection开始，我们想从中提取与List元素匹配的元素。

在下面的例子中，让我们考虑一下Melon类：

public class Melon {
  private final String type;
  private final int weight;
  // constructor, getters, equals(), hashCode(),
  // toString() omitted for brevity
}

这里，我们有一个巨大的Collection（在本例中，是一个ArrayList Melon：

List<Melon> melons = new ArrayList<>();
melons.add(new Melon("Apollo", 3000));
melons.add(new Melon("Jade Dew", 3500));
melons.add(new Melon("Cantaloupe", 1500));
melons.add(new Melon("Gac", 1600));
melons.add(new Melon("Hami", 1400));
...

我们还有一个List，包含我们想从前面ArrayList中提取的瓜的类型：

List<String> melonsByType 
  = Arrays.asList("Apollo", "Gac", "Crenshaw", "Hami");

这个问题的一个解决方案可能涉及循环收集和比较瓜的类型，但是生成的代码会非常慢。这个问题的另一个解决方案可能涉及到List.contains()方法和 Lambda 表达式：

List<Melon> results = melons.stream()
  .filter(t -> melonsByType.contains(t.getType()))
  .collect(Collectors.toList());

代码紧凑，速度快。在幕后，List.contains()依赖于以下检查：

// size - the size of melonsByType
// o - the current element to search from melons
// elementData - melonsByType
for (int i = 0; i < size; i++)
  if (o.equals(elementData[i])) {
    return i;
  }
}

然而，我们可以通过依赖于HashSet.contains()而不是List.contains()的解决方案来提高性能。当List.contains()使用前面的for语句来匹配元素时，HashSet.contains()使用Map.containsKey()。Set主要是基于Map实现的，每个增加的元素映射为element－PRESENT类型的键值。所以，element是这个Map中的一个键，PRESENT只是一个伪值。

当我们调用HashSet.contains(element)时，实际上我们调用Map.containsKey(element)。该方法基于给定元素的hashCode()，将给定元素与映射中的适当键进行匹配，比equals()快得多。

一旦我们将初始的ArrayList转换成HashSet，我们就可以开始了：

Set<String> melonsSetByType = melonsByType.stream()
  .collect(Collectors.toSet());
List<Melon> results = melons.stream()
  .filter(t -> melonsSetByType.contains(t.getType()))
  .collect(Collectors.toList());

嗯，这个解决方案比上一个快。它的运行时间应该是上一个解决方案所需时间的一半。

121 替换列表的元素

我们在应用中遇到的另一个常见问题是替换符合特定条件的List元素。

在下面的示例中，让我们考虑一下Melon类：

public class Melon {
  private final String type;
  private final int weight;
  // constructor, getters, equals(), hashCode(),
  // toString() omitted for brevity
}

然后，让我们考虑一下Melon的List：

List<Melon> melons = new ArrayList<>();
melons.add(new Melon("Apollo", 3000));
melons.add(new Melon("Jade Dew", 3500));
melons.add(new Melon("Cantaloupe", 1500));
melons.add(new Melon("Gac", 1600));
melons.add(new Melon("Hami", 1400));

让我们假设我们想把所有重量在 3000 克以下的西瓜换成其他同类型、重 3000 克的西瓜。

解决这个问题的方法是迭代List，然后使用List.set(int index, E element)相应地替换瓜。

下面是一段意大利面代码：

for (int i = 0; i < melons.size(); i++) {
  if (melons.get(i).getWeight() < 3000) {
    melons.set(i, new Melon(melons.get(i).getType(), 3000));
  }
}

另一种解决方案依赖于 Java8 函数式风格，或者更准确地说，依赖于UnaryOperator函数式接口。

基于此函数式接口，我们可以编写以下运算符：

UnaryOperator<Melon> operator = t 
  -> (t.getWeight() < 3000) ? new Melon(t.getType(), 3000) : t;

现在，我们可以使用 JDK8，List.replaceAll(UnaryOperator<E> operator)，如下所示：

melons.replaceAll(operator);

两种方法的性能应该几乎相同。

122 线程安全的集合、栈和队列

每当集合/栈/队列容易被多个线程访问时，它也容易出现特定于并发的异常（例如，java.util.ConcurrentModificationException。现在，让我们简要地概述一下 Java 内置的并发集合，并对其进行介绍。

并行集合

幸运的是，Java 为非线程安全集合（包括栈和队列）提供了线程安全（并发）的替代方案，如下所示。

线程安全列表

ArrayList的线程安全版本是CopyOnWriteArrayList。下表列出了 Java 内置的单线程和多线程列表：

单线程	多线程
`ArrayList LinkedList`	`CopyOnWriteArrayList`（经常读取，很少更新）`Vector`

CopyOnWriteArrayList实现保存数组中的元素。每次我们调用一个改变列表的方法（例如，add()、set()和remove()，Java 都会对这个数组的一个副本进行操作。

此集合上的Iterator将对集合的不可变副本进行操作。因此，可以修改原始集合而不会出现问题。在Iterator中看不到原始集合的潜在修改：

List<Integer> list = new CopyOnWriteArrayList<>();

当读取频繁而更改很少时，请使用此集合。

线程安全集合

Set的线程安全版本是CopyOnWriteArraySet。下表列举了 Java 内置的单线程和多线程集：

单线程	多线程
`HashSet TreeSet`（排序集）`LinkedHashSet`（维护插入顺序）`BitSet EnumSet`	`ConcurrentSkipListSet`（排序集）`CopyOnWriteArraySet`（经常读取，很少更新）

这是一个Set，它的所有操作都使用一个内部CopyOnWriteArrayList。创建这样一个Set可以如下所示：

Set<Integer> set = new CopyOnWriteArraySet<>();

当读取频繁而更改很少时，请使用此集合。

NavigableSet的线程安全版本是ConcurrentSkipListSet（并发SortedSet实现，最基本的操作在O(log n)中）。

线程安全映射

Map的线程安全版本是ConcurrentHashMap。

下表列举了 Java 内置的单线程和多线程映射：

单线程	多线程

HashMap TreeMap（排序键）LinkedHashMap（维护插入顺序）IdentityHashMap（通过==比较按键）WeakHashMap EnumMap ConcurrentHashMap ConcurrentSkipListMap（排序图）Hashtable

ConcurrentHashMap允许无阻塞的检索操作（例如，get()）。这意味着检索操作可能与更新操作重叠（包括put()和remove()。

创建ConcurrentHashMap的步骤如下：

ConcurrentMap<Integer, Integer> map = new ConcurrentHashMap<>();

当需要线程安全和高性能时，您可以依赖线程安全版本的Map，即ConcurrentHashMap。

避免Hashtable和Collections.synchronizedMap()，因为它们的性能较差。

对于支持NavigableMap的ConcurrentMap，操作依赖ConcurrentSkipListMap：

ConcurrentNavigableMap<Integer, Integer> map 
  = new ConcurrentSkipListMap<>();

由数组支持的线程安全队列

Java 提供了一个先进先出（FIFO）的线程安全队列，由一个数组通过ArrayBlockingQueue支持。下表列出了由数组支持的单线程和多线程 Java 内置队列：

单线程	多线程

ArrayDeque PriorityQueue（排序检索）ArrayBlockingQueue（有界）ConcurrentLinkedQueue （无界）ConcurrentLinkedDeque（无界）LinkedBlockingQueue（可选有界） LinkedBlockingDeque（可选有界）LinkedTransferQueue PriorityBlockingQueue

SynchronousQueue DelayQueue Stack

ArrayBlockingQueue的容量在创建后不能更改。尝试将一个元素放入一个完整的队列将导致操作阻塞；尝试从一个空队列中获取一个元素也将导致类似的阻塞。

创建ArrayBlockingQueue很容易，如下所示：

BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(QUEUE_MAX_SIZE);

Java 还提供了两个线程安全的、可选的有界阻塞队列，它们基于通过LinkedBlockingQueue和LinkedBlockingDeque链接的节点（双向队列是一个线性集合，支持在两端插入和删除元素）。

基于链接节点的线程安全队列

Java 通过ConcurrentLinkedDeque/ConcurrentLinkedQueue提供了一个由链接节点支持的无边界线程安全队列/队列。这里是ConcurrentLinkedDeque：

Deque<Integer> queue = new ConcurrentLinkedDeque<>();

线程安全优先级队列

Java 通过PriorityBlockingQueue提供了一个基于优先级堆的无边界线程安全优先级阻塞队列。

创建PriorityBlockingQueue很容易，如下所示：

BlockingQueue<Integer> queue = new PriorityBlockingQueue<>();

非线程安全版本名为PriorityQueue。

线程安全延迟队列

Java 提供了一个线程安全的无界阻塞队列，在该队列中，只有当元素的延迟通过DelayQueue过期时，才能获取该元素。创建一个DelayQueue如下所示：

BlockingQueue<TrainDelay> queue = new DelayQueue<>();

线程安全传输队列

Java 通过LinkedTransferQueue提供了基于链接节点的线程安全的无界传输队列。

这是一个 FIFO 队列，头是某个生产者在队列中停留时间最长的元素。队列的尾是某个生产者在队列中停留时间最短的元素。

创建此类队列的一种方法如下：

TransferQueue<String> queue = new LinkedTransferQueue<>();

线程安全同步队列

Java 提供了一个阻塞队列，其中每个插入操作必须等待另一个线程执行相应的移除操作，反之亦然，通过SynchronousQueue：

BlockingQueue<String> queue = new SynchronousQueue<>();

线程安全栈

栈的线程安全实现是Stack和ConcurrentLinkedDeque。

Stack类表示对象的后进先出（LIFO）栈。它通过几个操作扩展了Vector类，这些操作允许将向量视为栈。Stack的每一种方法都是同步的。创建一个Stack如下所示：

Stack<Integer> stack = new Stack<>();

ConcurrentLinkedDeque实现可以通过其push()和pop()方法用作Stack（后进先出）：

Deque<Integer> stack = new ConcurrentLinkedDeque<>();

为了获得更好的性能，请选择ConcurrentLinkedDeque而不是Stack。

绑定到本书中的代码为前面的每个集合提供了一个应用，用于跨越多个线程，以显示它们的线程安全特性。

同步的集合

除了并行集合，我们还有synchronized集合。Java 提供了一套包装器，将集合公开为线程安全的集合。这些包装在Collections中提供。最常见的有：

synchronizedCollection(Collection<T> c)：返回由指定集合支持的同步（线程安全）集合
synchronizedList(List<T> list)：返回指定列表支持的同步（线程安全）列表：

List<Integer> syncList 
  = Collections.synchronizedList(new ArrayList<>());

synchronizedMap(Map<K,V> m)：返回指定映射支持的同步（线程安全）映射：

Map<Integer, Integer> syncMap 
  = Collections.synchronizedMap(new HashMap<>());

synchronizedSet(Set<T> s)：返回指定集支持的同步（线程安全）集：

Set<Integer> syncSet 
  = Collections.synchronizedSet(new HashSet<>());

并发集合与同步集合

显而易见的问题是“并发集合和同步集合的区别是什么？”好吧，主要区别在于它们实现线程安全的方式。并发集合通过将数据划分为段来实现线程安全。线程可以并发地访问这些段，并且只能在所使用的段上获得锁。另一方面，同步集合通过内部锁定锁定整个集合（调用同步方法的线程将自动获取该方法对象的内在锁，并在方法返回时释放它）。

迭代同步的集合需要手动同步，如下所示：

List syncList = Collections.synchronizedList(new ArrayList());
...
synchronized(syncList) {
  Iterator i = syncList.iterator();
  while (i.hasNext()) {
    // do_something_with i.next();
  }
}

由于并发集合允许线程的并发访问，因此它们的性能比同步集合高得多。

123 广度优先搜索

BFS 是遍历（访问）图或树的所有节点的经典算法。

理解这个算法最简单的方法是通过伪代码和一个例子。BFS 的伪码如下：

创建队列Q

将v标记为已访问，并将v放入Q

当Q为非空

取下Q的头部h

标记h的所有（未访问的）邻居并入队

假设下图中的图，步骤 0：

在第一步（步骤 1），我们访问顶点0。我们把它放在visited列表中，它的所有相邻顶点放在queue（3，1）中。此外，在步骤 2 中，我们访问queue、3前面的元素。顶点3在步骤 2 中有一个未访问的相邻顶点，所以我们将其添加到queue的后面。接下来，在步骤 3 中，我们访问queue 1前面的元素。

该顶点有一个相邻的顶点（0），但该顶点已被访问。最后，我们访问顶点2，最后一个来自queue。

这个有一个已经访问过的相邻顶点（3）。

在代码行中，BFS 算法可以实现如下：

public class Graph {
  private final int v;
  private final LinkedList<Integer>[] adjacents;
  public Graph(int v) {
    this.v = v;
    adjacents = new LinkedList[v];
    for (int i = 0; i < v; ++i) {
      adjacents[i] = new LinkedList();
    }
  }
  public void addEdge(int v, int e) {
    adjacents[v].add(e);
  }
  public void BFS(int start) {
    boolean visited[] = new boolean[v];
    LinkedList<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
      start = queue.poll();
      System.out.print(start + " ");
      Iterator<Integer> i = adjacents[start].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }
}

并且，如果我们引入以下图表（从前面的图表），我们有如下：

Graph graph = new Graph(4);
graph.addEdge(0, 3);
graph.addEdge(0, 1);
graph.addEdge(1, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(3, 2);
graph.addEdge(3, 3);

输出将为0 3 1 2。

124 Trie

Trie（也称为数字树）是一种有序的树结构，通常用于存储字符串。它的名字来源于 Trie 是 reTrieval数据结构。它的性能优于二叉树。

除 Trie 的根外，Trie 的每个节点都包含一个字符（例如，单词hey将有三个节点）。Trie 的每个节点主要包含以下内容：

值（字符或数字）

指向子节点的指针

如果当前节点完成一个字，则为true的标志

用于分支节点的单个根

下图表示构建包含单词cat、caret和bye的 Trie 的步骤顺序：

因此，在代码行中，Trie 节点的形状可以如下所示：

public class Node {
  private final Map<Character, Node> children = new HashMap<>();
  private boolean word;
  Map<Character, Node> getChildren() {
    return children;
  }
  public boolean isWord() {
    return word;
  }
  public void setWord(boolean word) {
    this.word = word;
  }
}

基于这个类，我们可以定义一个 Trie 基本结构如下：

class Trie {
  private final Node root;
  public Trie() {
    root = new Node();
  }
  public void insert(String word) {
    ...
  }
  public boolean contains(String word) {
    ...
  }
  public boolean delete(String word) {
    ...
  }
}

Java 编程问题：五、数组、集合和数据结构5

通过迭代器删除

移除通孔集合.removeIf()

通过流删除

通过`Collectors.partitioningBy()`

119 将集合转换为数组

120 按列表过滤集合

121 替换列表的元素

122 线程安全的集合、栈和队列

并行集合

线程安全列表

线程安全集合

线程安全映射

由数组支持的线程安全队列

基于链接节点的线程安全队列

线程安全优先级队列

线程安全延迟队列

线程安全传输队列

线程安全同步队列

线程安全栈

同步的集合

并发集合与同步集合

123 广度优先搜索

124 Trie

热门文章

最新文章

相关课程

相关电子书

相关实验场景

Java 编程问题：五、数组、集合和数据结构5

通过迭代器删除

移除通孔集合.removeIf()

通过流删除

通过Collectors.partitioningBy()

119 将集合转换为数组

120 按列表过滤集合

121 替换列表的元素

122 线程安全的集合、栈和队列

并行集合

线程安全列表

线程安全集合

线程安全映射

由数组支持的线程安全队列

基于链接节点的线程安全队列

线程安全优先级队列

线程安全延迟队列

线程安全传输队列

线程安全同步队列

线程安全栈

同步的集合

并发集合与同步集合

123 广度优先搜索

124 Trie

热门文章

最新文章

相关课程

相关电子书

相关实验场景

通过`Collectors.partitioningBy()`