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

ApacheCN_飞龙

发布于 2022-07-11 14:17:28

1.4K0

发布于 2022-07-11 14:17:28

原文：Java Coding Problems 协议：CC BY-NC-SA 4.0 贡献者：飞龙本文来自【ApacheCN Java 译文集】，自豪地采用谷歌翻译。

本章包括 30 个问题，涉及数组、集合和几个数据结构。其目的是为在广泛的应用中遇到的一类问题提供解决方案，包括排序、查找、比较、排序、反转、填充、合并、复制和替换。提供的解决方案是用 Java8-12 实现的，它们也可以作为解决其他相关问题的基础。在本章的最后，您将掌握广泛的知识，这些知识对于解决涉及数组、集合和数据结构的各种问题非常有用。

问题

使用以下问题测试基于数组、集合和数据结构的编程能力。我强烈建议您在使用解决方案和下载示例程序之前，先尝试一下每个问题：

数组排序：编写几个程序，举例说明数组的不同排序算法。另外，编写一个数组洗牌程序。
寻找数组中的元素：编写几个程序，举例说明如何在给定的数组中找到给定的元素（原始类型和对象）。查找索引和/或简单地检查值是否在数组中。
检查两个数组是否相等或不匹配：编写一个程序，检查给定的两个数组是否相等或不匹配。
按字典比较两个数组：编写一个程序，按字典法比较给定的数组。
从数组创建流：编写从给定数组创建流的程序。
数组的最小值、最大值和平均值：编写一个程序，计算给定数组的最大值、最小值和平均值。
反转数组：写一个程序反转给定的数组。
填充和设置数组：写几个填充数组和基于生成函数设置所有元素的例子来计算每个元素。
下一个较大的元素（NGE）：编写一个程序，返回数组中每个元素的 NGE。
改变数组大小：编写一个程序，通过将数组的大小增加一个元素来增加数组的大小。另外，编写一个程序，用给定的长度增加数组的大小。
创建不可修改/不可变集合：编写几个创建不可修改和不可变集合的示例。
映射的默认值：编写一个程序，从Map获取一个值或一个默认值。
计算Map中的键是否缺失/存在：编写一个程序，计算缺失键的值或当前键的新值。
从Map中删除条目：编写一个程序，用给定的键从Map删除。
替换Map中的条目：编写一个程序来替换Map中给定的条目。
比较两个映射：编写一个比较两幅映射的程序。
合并两个映射：编写一个程序，合并两个给定的映射。
复制HashMap：编写一个程序，执行HashMap的浅复制和深复制。
排序Map：编写一个程序对Map进行排序。
删除集合中与谓词匹配的所有元素：编写一个程序，删除集合中与给定谓词匹配的所有元素。
将集合转换成数组：编写一个程序，将集合转换成数组。
过滤List集合：写几个List过滤集合的方案。揭示最好的方法。
替换List的元素：编写一个程序，将List的每个元素替换为对其应用给定运算符的结果。
线程安全集合、栈和队列：编写几个程序来举例说明 Java 线程安全集合的用法。
广度优先搜索（BFS）：编写实现 BFS 算法的程序。
Trie：编写一个实现 Trie 数据结构的程序。
元组：编写实现元组数据结构的程序。
并查：编写实现并查算法的程序。
Fenwick 树或二叉索引树：编写一个实现 Fenwick 树算法的程序。
布隆过滤器：编写实现布隆过滤器算法的程序。

**# 解决方案

以下各节介绍上述问题的解决方案。记住，通常没有一个正确的方法来解决一个特定的问题。另外，请记住，这里显示的解释仅包括解决问题所需的最有趣和最重要的细节。下载示例解决方案以查看更多详细信息，并在这个页面中试用程序。

99 排序数组

排序数组是许多域/应用中遇到的常见任务。Java 提供了一个内置的解决方案，使用比较器对原始类型和对象的数组进行排序，这一点非常常见。这种解决方案效果很好，在大多数情况下都是比较可取的方法。让我们在下一节中看看不同的解决方案。

JDK 内置解决方案

内置的解决方案名为sort()，它在java.util.Arrays类中有许多不同的风格（15 种以上的风格）。

在sort()方法的背后，有一个性能良好的快速排序类型的排序算法，称为双轴快速排序。

假设我们需要按自然顺序对整数数组进行排序（原始类型int。为此，我们可以依赖于Arrays.sort(int[] a)，如下例所示：

int[] integers = new int[]{...};
Arrays.sort(integers);

有时，我们需要对一个对象数组进行排序。假设我们有一个类Melon：

public class Melon {

  private final String type;
  private final int weight;

  public Melon(String type, int weight) {
    this.type = type;
    this.weight = weight;
  }

  // getters omitted for brevity
}

Melon的数组可以通过适当的Comparator按升序权重排序：

Melon[] melons = new Melon[] { ... };

Arrays.sort(melons, new Comparator<Melon>() {
  @Override
  public int compare(Melon melon1, Melon melon2) {
    return Integer.compare(melon1.getWeight(), melon2.getWeight());
  }
});

通过 Lambda 表达式重写前面的代码可以获得相同的结果：

Arrays.sort(melons, (Melon melon1, Melon melon2) 
  -> Integer.compare(melon1.getWeight(), melon2.getWeight()));

此外，数组提供了一种并行排序元素的方法parallelSort()。幕后使用的排序算法是一种基于ForkJoinPool的并行排序合并，它将数组分解为子数组，子数组本身进行排序，然后进行合并。举个例子：

Arrays.parallelSort(melons, new Comparator<Melon>() {
  @Override
  public int compare(Melon melon1, Melon melon2) {
    return Integer.compare(melon1.getWeight(), melon2.getWeight());
  }
});

或者，通过 Lambda 表达式，我们有以下示例：

Arrays.parallelSort(melons, (Melon melon1, Melon melon2) 
  -> Integer.compare(melon1.getWeight(), melon2.getWeight()));

前面的示例按升序对数组排序，但有时需要按降序对其排序。当我们对一个Object数组进行排序并依赖于一个Comparator时，我们可以简单地将返回的结果乘以Integer.compare()再乘以 -1：

Arrays.sort(melons, new Comparator<Melon>() {
  @Override
  public int compare(Melon melon1, Melon melon2) {
    return (-1) * Integer.compare(melon1.getWeight(), 
      melon2.getWeight());
  }
});

或者，我们可以简单地在compare()方法中切换参数。

对于装箱原始类型的数组，解决方案可以依赖于Collections.reverse()方法，如下例所示：

Integer[] integers = new Integer[] {3, 1, 5};

// 1, 3, 5
Arrays.sort(integers);

// 5, 3, 1
Arrays.sort(integers, Collections.reverseOrder());

不幸的是，没有内置的解决方案来按降序排列原始类型数组。最常见的情况是，如果我们仍然要依赖于Arrays.sort()，那么这个问题的解决方案是在数组按升序排序后反转数组（O(n)）：

// sort ascending
Arrays.sort(integers);

// reverse array to obtain it in descending order
for (int leftHead = 0, rightHead = integers.length - 1;
       leftHead < rightHead; leftHead++, rightHead--) {

  int elem = integers[leftHead];
  integers[leftHead] = integers[rightHead];
  integers[rightHead] = elem;
}

另一个解决方案可以依赖于 Java8 函数式风格和装箱（请注意装箱是一个非常耗时的操作）：

int[] descIntegers = Arrays.stream(integers)
  .boxed() //or .mapToObj(i -> i)
  .sorted((i1, i2) -> Integer.compare(i2, i1))
  .mapToInt(Integer::intValue)
  .toArray();

其他排序算法

嗯，还有很多其他的排序算法。每种方法都有优缺点，最好的选择方法是对应用特定的情况进行基准测试。

让我们研究其中的一些，如下一节中强调的，从一个非常慢的算法开始。

冒泡排序

冒泡排序是一个简单的算法，基本上气泡数组的元素。这意味着它会多次遍历数组，并在相邻元素顺序错误时交换它们，如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P0aGDppN-1657077783912)(img/55223d63-21de-4e89-a1df-06ad4e1c72fc.png)]

时间复杂度情况如下：最佳情况O(n)、平均情况O(n2)、最坏情况O(n2)

空间复杂度情况如下：最坏情况O(1)

实现冒泡排序的实用方法如下：

public static void bubbleSort(int[] arr) {

  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {

      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

还有一个依赖于while循环的优化版本。你可以在捆绑到这本书的代码中找到它，名字是bubbleSortOptimized()。

作为时间执行的性能比较，对于 100000 个整数的随机数组，优化后的版本将快 2 秒左右。

前面的实现可以很好地对原始类型数组进行排序，但是，要对Object数组进行排序，我们需要在代码中引入Comparator，如下所示：

public static <T> void bubbleSortWithComparator(
    T arr[], Comparator<? super T> c) {

  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {

      if (c.compare(arr[j], arr[j + 1]) > 0) {
        T temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

还记得以前的类吗？好吧，我们可以通过实现Comparator接口为它写一个Comparator：

public class MelonComparator implements Comparator<Melon> {

  @Override
  public int compare(Melon o1, Melon o2) {
    return o1.getType().compareTo(o2.getType());
  }
}

或者，在 Java8 函数式风格中，我们有以下内容：

// Ascending
Comparator<Melon> byType = Comparator.comparing(Melon::getType);

// Descending
Comparator<Melon> byType 
  = Comparator.comparing(Melon::getType).reversed();

在一个名为ArraySorts的工具类中，有一个Melon数组、前面的Comparator数组和bubbleSortWithComparator()方法，我们可以按照下面的思路编写一些东西：

Melon[] melons = {...};
ArraySorts.bubbleSortWithComparator(melons, byType);

为简洁起见，跳过了带有Comparator的冒泡排序优化版本，但它在绑定到本书的代码中可用。

当数组几乎已排序时，冒泡排序速度很快。此外，它还非常适合对兔子（接近数组开头的大元素）和海龟（接近数组结尾的小元素）进行排序。但总的来说，这是一个缓慢的算法。

插入排序

插入排序算法依赖于一个简单的流。它从第二个元素开始，并将其与前面的元素进行比较。如果前面的元素大于当前元素，则算法将交换这些元素。此过程将继续，直到前面的元素小于当前元素。

在这种情况下，算法将传递到数组中的下一个元素并重复该流，如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qNiRpg2t-1657077783913)(img/e0b8ebdf-04b3-43c1-9796-8197146c17ab.png)]

时间复杂度情况如下：最佳情况O(n)、平均情况O(n2)、最坏情况O(n2)

空间复杂度情况如下：最坏情况O(1)

基于此流程，原始类型的实现如下所示：

public static void insertionSort(int arr[]) {

  int n = arr.length;

  for (int i = 1; i < n; ++i) {

    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = key;
  }
}

为了比较一个Melon数组，我们需要在实现中引入一个Comparator，如下所示：

public static <T> void insertionSortWithComparator(
  T arr[], Comparator<? super T> c) {

  int n = arr.length;

  for (int i = 1; i < n; ++i) {

    T key = arr[i];
    int j = i - 1;

    while (j >= 0 && c.compare(arr[j], key) > 0) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = key;
  }
}

在这里，我们有一个Comparator，它使用thenComparing()方法，按照 Java8 函数式编写的类型和重量对西瓜进行排序：

Comparator<Melon> byType = Comparator.comparing(Melon::getType)
  .thenComparing(Melon::getWeight);

在一个名为ArraySorts的实用类中，有一个Melon数组、前面的Comparator数组和insertionSortWithComparator()方法，我们可以编写如下内容：

Melon[] melons = {...};
ArraySorts.insertionSortWithComparator(melons, byType);

对于较小且大部分排序的数组，这可能会很快。此外，在向数组中添加新元素时，它的性能也很好。它也是非常有效的内存，因为一个单一的元素是移动。

计数排序

计数排序流从计算数组中的最小和最大元素开始。该算法根据计算出的最小值和最大值定义一个新的数组，该数组将使用元素作为索引对未排序的元素进行计数。此外，以这样的方式修改这个新数组，使得每个索引处的每个元素存储先前计数的总和。最后，从这个新的数组中得到排序后的数组。

时间复杂度情况如下：最佳情况O(n + k)、平均情况O(n + k)、最坏情况O(n + k)

空间复杂度情况如下：最坏情况O(k)

k is the number of possible values in the range. n is the number of elements to be sorted.

让我们考虑一个简单的例子。初始数组包含以下元素，arr：4、2、6、2、6、8、5：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NsKNdJW7-1657077783914)(img/570e8015-a037-48d9-b4f9-459a694b73ee.png)]

最小元件为2，最大元件为8。新数组counts的大小等于最大值减去最小值+1=8-2+1=7。

对每个元素进行计数将产生以下数组（counts[arr[i] - min]++）：

counts[2] = 1 (4); counts[0] = 2 (2); counts[4] = 2 (6);
counts[6] = 1 (8); counts[3] = 1 (5);

现在，我们必须循环此数组，并使用它重建排序后的数组，如下所示：

public static void countingSort(int[] arr) {

  int min = arr[0];
  int max = arr[0];

  for (int i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
    } else if (arr[i] > max) {
      max = arr[i];
    }
  }

  int[] counts = new int[max - min + 1];

  for (int i = 0; i < arr.length; i++) {
    counts[arr[i] - min]++;
  }

  int sortedIndex = 0;

  for (int i = 0; i < counts.length; i++) {
    while (counts[i] > 0) {
      arr[sortedIndex++] = i + min;
      counts[i]--;
    }
  }
}

这是一个非常快速的算法。

堆排序

堆排序是一种依赖于二进制堆（完全二叉树）的算法。

时间复杂度情况如下：最佳情况O(n log n)、平均情况O(n log n)、最坏情况O(n log n)

空间复杂度情况如下：最坏情况O(1)

可以通过最大堆（父节点总是大于或等于子节点）按升序排序元素，通过最小堆（父节点总是小于或等于子节点）按降序排序元素。

在第一步，该算法使用提供的数组来构建这个堆，并将其转换为一个最大堆（该堆由另一个数组表示）。因为这是一个最大堆，所以最大的元素是堆的根。在下一步中，根与堆中的最后一个元素交换，堆大小减少 1（从堆中删除最后一个节点）。堆顶部的元素按顺序排列。最后一步由建堆（以自顶向下的方式构建堆的递归过程）和堆的根（重构最大堆）组成。重复这三个步骤，直到堆大小大于 1：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uaBkX8Zd-1657077783914)(img/d3f60043-6301-496d-b298-97ace7eb01dc.png)]

例如，假设上图中的数组-4、5、2、7、1：

因此，在第一步，我们构建堆：4、5、2、7、1。
我们构建了最大堆：7、5、2、4、1（我们将5与4、4与7、5与7进行了交换）。
接下来，我们将根（7）与最后一个元素（1）交换并删除7。结果：1、5、2、4、7。
进一步，我们再次构建最大堆：5、4、2、1（我们将5与1进行了交换，将1与4进行了交换）。
我们将根（5）与最后一个元素（1）交换，并删除5。结果：1、4、2、5、7。
接下来，我们再次构建最大堆：4、1、2（我们将1与4进行了交换）。
我们将根（4）与最后一个元素（2）交换，并删除4。结果：2、1。
这是一个最大堆，因此将根（2）与最后一个元素（1）交换并移除2：1、2、4、5、7。
完成！堆中只剩下一个元素（1）。

在代码行中，前面的示例可以概括如下：

public static void heapSort(int[] arr) {
  int n = arr.length;

  buildHeap(arr, n);

  while (n > 1) {
    swap(arr, 0, n - 1);
    n--;
    heapify(arr, n, 0);
  }
}

private static void buildHeap(int[] arr, int n) {
  for (int i = arr.length / 2; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

private static void heapify(int[] arr, int n, int i) {
  int left = i * 2 + 1;
  int right = i * 2 + 2;
  int greater;

  if (left < n && arr[left] > arr[i]) {
    greater = left;
  } else {
    greater = i;
  }

  if (right < n && arr[right] > arr[greater]) {
    greater = right;
  }

  if (greater != i) {
    swap(arr, i, greater);
    heapify(arr, n, greater);
  }
}

private static void swap(int[] arr, int x, int y) {
  int temp = arr[x];
  arr[x] = arr[y];
  arr[y] = temp;
}

如果我们想要比较对象，那么我们必须在实现中引入一个Comparator。此解决方案在捆绑到本书的代码中以heapSortWithComparator()的名称提供。

这里是一个用 Java8 函数式编写的Comparator，它使用thenComparing()和reversed()方法按类型和重量降序排列瓜类：

Comparator<Melon> byType = Comparator.comparing(Melon::getType)
  .thenComparing(Melon::getWeight).reversed();

在一个名为ArraySorts的实用类中，有一个Melon数组、前面的Comparator数组和heapSortWithComparator()方法，我们可以编写如下内容：

Melon[] melons = {...};
ArraySorts.heapSortWithComparator(melons, byType);

堆排序相当快，但不稳定。例如，对已排序的数组进行排序可能会使其保持不同的顺序。

我们将在这里停止关于排序数组的论文，但是，在本书附带的代码中，还有一些排序算法可用：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KawXiNbo-1657077783915)(img/56dcf8c1-a04d-4541-aa1d-402d74d053a2.png)]

还有许多其他算法专门用于排序数组。其中一些是建立在这里介绍的基础上的（例如，梳排序、鸡尾酒排序和奇偶排序是冒泡排序的风格，桶排序是通常依赖于插入排序的分布排序，基数排序（LSD）是类似于桶排序的稳定分布，Gnome 排序是插入排序的变体）。

其他则是不同的方法（例如，Arrays.sort()方法实现的快速排序，Arrays.parallelSort()方法实现的合并排序）。

作为对本节的奖励，让我们看看如何洗牌一个数组。实现这一点的有效方法依赖于 Fisher-Yates 洗牌（称为 Knuth 洗牌）。基本上，我们以相反的顺序循环数组，然后随机交换元素。对于原始类型（例如，int），实现如下：

public static void shuffleInt(int[] arr) {

  int index;

  Random random = new Random();

  for (int i = arr.length - 1; i > 0; i--) {

    index = random.nextInt(i + 1);
    swap(arr, index, i);
  }
}

在绑定到本书的代码中，还有一个实现，用于对Object的数组进行洗牌。

通过Collections.shuffle(List<?> list)洗牌列表非常简单。

100 在数组中查找元素

当我们在数组中搜索一个元素时，我们可能感兴趣的是找出这个元素出现的索引，或者只找出它是否存在于数组中。本节介绍的解决方案具体化为以下屏幕截图中的方法：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KSNz7Uxj-1657077783915)(img/e232122f-eaab-4f40-8188-71fbe14419ac.png)]

让我们在下一节中看看不同的解决方案。

只检查是否存在

假设以下整数数组：

int[] numbers = {4, 5, 1, 3, 7, 4, 1};

由于这是一个原始类型数组，解决方案可以简单地循环数组并返回给定整数的第一个匹配项，如下所示：

public static boolean containsElement(int[] arr, int toContain) {

  for (int elem: arr) {
    if (elem == toContain) {
      return true;
    }
  }

  return false;
}

这个问题的另一个解决方法可以依赖于Arrays.binarySearch()方法。这种方法有几种风格，但在这种情况下，我们需要这个：int binarySearch(int[] a, int key)。该方法将搜索给定数组中的给定键，并返回相应的索引或负值。唯一的问题是，此方法仅适用于已排序的数组；因此，我们需要事先对数组排序：

public static boolean containsElement(int[] arr, int toContain) {

  Arrays.sort(arr);
  int index = Arrays.binarySearch(arr, toContain);

  return (index >= 0);
}

如果数组已经排序，那么可以通过删除排序步骤来优化前面的方法。此外，如果数组被排序，前面的方法可以返回数组中元素出现的索引，而不是一个boolean。但是，如果数组没有排序，请记住返回的索引对应于排序的数组，而不是未排序的（初始）数组。如果不想对初始数组进行排序，则建议将数组的克隆传递给此方法。另一种方法是在这个辅助方法中克隆数组。

在 Java8 中，解决方案可以依赖于函数式方法。这里一个很好的候选者是anyMatch()方法。此方法返回流中是否有元素与提供的谓词匹配。因此，我们需要做的就是将数组转换为流，如下所示：

public static boolean containsElement(int[] arr, int toContain) {

  return Arrays.stream(arr)
    .anyMatch(e -> e == toContain);
}

对于任何其他原始类型，改编或概括前面的示例都非常简单。

现在，让我们集中精力在数组中寻找Object。让我们考虑一下Melon类：

public class Melon {

  private final String type;
  private final int weight;

  // constructor, getters, equals() and hashCode() skipped for brevity
}

接下来，让我们考虑一个Melon数组：

Melon[] melons = new Melon[] {new Melon("Crenshaw", 2000),
  new Melon("Gac", 1200), new Melon("Bitter", 2200)
};

现在，假设我们要在这个数组中找到 1200 克的木瓜。一个解决方案可以依赖于equals()方法，该方法用于确定两个对象的相等性：

public static <T> boolean 
    containsElementObject(T[] arr, T toContain) {

  for (T elem: arr) {
    if (elem.equals(toContain)) {
      return true;
    }
  }

  return false;
}

同样，我们可以依赖于Arrays.asList(arr).contains(find)。基本上，将数组转换为一个List并调用contains()方法。在幕后，这种方法使用的是equals()合同。

如果此方法存在于名为ArraySearch的工具类中，则以下调用将返回true：

// true
boolean found = ArraySearch.containsElementObject(
  melons, new Melon("Gac", 1200));

只要我们想依赖equals()合同，这个解决方案就行。但是我们可以认为，如果甜瓜的名字出现（Gac），或者它的重量出现（1200），那么我们的甜瓜就存在于数组中。对于这种情况，更实际的做法是依赖于Comparator：

public static <T> boolean containsElementObject(
    T[] arr, T toContain, Comparator<? super T> c) {

  for (T elem: arr) {
    if (c.compare(elem, toContain) == 0) {
      return true;
    }
  }

  return false;
}

现在，一个只考虑瓜的类型的Comparator可以写为：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);

由于Comparator忽略了瓜的重量（没有 1205 克的瓜），下面的调用将返回true：

// true
boolean found = ArraySearch.containsElementObject(
  melons, new Melon("Gac", 1205), byType);

另一种方法依赖于binarySearch()的另一种风格。Arrays类提供了一个binarySearch()方法，该方法获取一个Comparator、<T> int binarySearch(T[] a, T key, Comparator<? super T> c)。这意味着我们可以如下使用它：

public static <T> boolean containsElementObject(
    T[] arr, T toContain, Comparator<? super T> c) {

  Arrays.sort(arr, c);
  int index = Arrays.binarySearch(arr, toContain, c);

  return (index >= 0);
}

如果初始数组状态应保持不变，则建议将数组的克隆传递给此方法。另一种方法是在这个辅助方法中克隆数组。

现在，一个只考虑瓜重的Comparator可以写为：

Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight);

由于Comparator忽略了甜瓜的类型（没有蜜瓜类型的甜瓜），下面的调用将返回true：

// true
boolean found = ArraySearch.containsElementObject(
  melons, new Melon("Honeydew", 1200), byWeight);

只检查第一个索引

对于一组原始类型，最简单的实现就说明了这一点：

public static int findIndexOfElement(int[] arr, int toFind) {

  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == toFind) {
      return i;
    }
  }

  return -1;
}

依靠 Java8 函数风格，我们可以尝试循环数组并过滤与给定元素匹配的元素。最后，只需返回找到的第一个元素：

public static int findIndexOfElement(int[] arr, int toFind) {

  return IntStream.range(0, arr.length)
    .filter(i -> toFind == arr[i])
    .findFirst()
    .orElse(-1);
}

对于Object数组，至少有三种方法。首先，我们可以依据equals()合同：

public static <T> int findIndexOfElementObject(T[] arr, T toFind) {

  for (int i = 0; i < arr.length; i++) {
    if (arr[i].equals(toFind)) {
      return i;
    }
  }

  return -1;
}

同样，我们可以依赖于Arrays.asList(arr).indexOf(find)。基本上，将数组转换为一个List并调用indexOf()方法。在幕后，这种方法使用的是equals()合同。

其次，我们可以依赖于Comparator：

public static <T> int findIndexOfElementObject(
    T[] arr, T toFind, Comparator<? super T> c) {

  for (int i = 0; i < arr.length; i++) {
    if (c.compare(arr[i], toFind) == 0) {
      return i;
    }
  }

  return -1;
}

第三，我们可以依赖 Java8 函数式风格和一个Comparator：

public static <T> int findIndexOfElementObject(
    T[] arr, T toFind, Comparator<? super T> c) {

  return IntStream.range(0, arr.length)
    .filter(i -> c.compare(toFind, arr[i]) == 0)
    .findFirst()
    .orElse(-1);
}

101 检查两个数组是否相等或不匹配

如果两个原始数组包含相同数量的元素，则它们相等，并且两个数组中所有对应的元素对都相等

这两个问题的解决依赖于Arrays实用类。下面几节给出了解决这些问题的方法。

检查两个数组是否相等

通过Arrays.equals()方法可以很容易地检查两个数组是否相等。对于基本类型、Object和泛型，这个标志方法有很多种风格。它还支持比较器。

让我们考虑以下三个整数数组：

int[] integers1 = {3, 4, 5, 6, 1, 5};
int[] integers2 = {3, 4, 5, 6, 1, 5};
int[] integers3 = {3, 4, 5, 6, 1, 3};

现在，让我们检查一下integers1是否等于integers2，以及integers1是否等于integers3。这很简单：

boolean i12 = Arrays.equals(integers1, integers2); // true
boolean i13 = Arrays.equals(integers1, integers3); // false

前面的例子检查两个数组是否相等，但是我们也可以通过boolean equals(int[] a, int aFromIndex, int aToIndex, int[] b, int bFromIndex, int bToIndex)方法检查数组的两个段（或范围）是否相等。因此，我们通过范围[aFromIndex, aToIndex)来划分第一个数组的段，通过范围[bFromIndex, bToIndex)来划分第二个数组的段：

// true
boolean is13 = Arrays.equals(integers1, 1, 4, integers3, 1, 4);

现在，让我们假设Melon的三个数组：

public class Melon {

  private final String type;
  private final int weight;

  public Melon(String type, int weight) {
    this.type = type;
    this.weight = weight;
  }

  // getters, equals() and hashCode() omitted for brevity
}

Melon[] melons1 = {
  new Melon("Horned", 1500), new Melon("Gac", 1000)
};

Melon[] melons2 = {
  new Melon("Horned", 1500), new Melon("Gac", 1000)
};

Melon[] melons3 = {
  new Melon("Hami", 1500), new Melon("Gac", 1000)
};

基于equals()合同或基于指定的Comparator，两个Object数组被视为相等。我们可以很容易地检查melons1是否等于melons2，以及melons1是否等于melons3，如下所示：

boolean m12 = Arrays.equals(melons1, melons2); // true
boolean m13 = Arrays.equals(melons1, melons3); // false

在明确的范围内，使用boolean equals(Object[] a, int aFromIndex, int aToIndex, Object[] b, int bFromIndex, int bToIndex)：

boolean ms13 = Arrays.equals(melons1, 1, 2, melons3, 1, 2); // false

虽然这些示例依赖于Melon.equals()实现，但以下两个示例依赖于以下两个Comparator：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);
Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight);

使用布尔值equals(T[] a, T[] a2, Comparator<? super T> cmp)，我们得到以下结果：

boolean mw13 = Arrays.equals(melons1, melons3, byWeight); // true
boolean mt13 = Arrays.equals(melons1, melons3, byType);   // false

并且，在显式范围内，使用Comparator、<T> boolean equals(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex, Comparator<? super T> cmp)，我们得到：

// true
boolean mrt13 = Arrays.equals(melons1, 1, 2, melons3, 1, 2, byType);

检查两个数组是否包含不匹配项

如果两个数组相等，则不匹配应返回 -1。但是如果两个数组不相等，那么不匹配应该返回两个给定数组之间第一个不匹配的索引。为了解决这个问题，我们可以依赖 JDK9Arrays.mismatch()方法。

例如，我们可以检查integers1和integers2之间的不匹配，如下所示：

int mi12 = Arrays.mismatch(integers1, integers2); // -1

结果是 -1，因为integers1和integers2相等。但是如果我们检查integers1和integers3，我们会得到值 5，这是这两个值之间第一个不匹配的索引：

int mi13 = Arrays.mismatch(integers1, integers3); // 5

如果给定的数组有不同的长度，而较小的数组是较大数组的前缀，那么返回的不匹配就是较小数组的长度。

对于Object的数组，也有专用的mismatch()方法。这些方法依赖于equals()合同或给定的Comparator。我们可以检查melons1和melons2之间是否存在不匹配，如下所示：

int mm12 = Arrays.mismatch(melons1, melons2); // -1

如果第一个索引发生不匹配，则返回值为 0。这在melons1和melons3的情况下发生：

int mm13 = Arrays.mismatch(melons1, melons3); // 0

在Arrays.equals()的情况下，我们可以使用Comparator检查显式范围内的不匹配：

// range [1, 2), return -1
int mms13 = Arrays.mismatch(melons1, 1, 2, melons3, 1, 2);

// Comparator by melon's weights, return -1
int mmw13 = Arrays.mismatch(melons1, melons3, byWeight);

// Comparator by melon's types, return 0
int mmt13 = Arrays.mismatch(melons1, melons3, byType);

// range [1,2) and Comparator by melon's types, return -1
int mmrt13 = Arrays.mismatch(melons1, 1, 2, melons3, 1, 2, byType);

102 按字典顺序比较两个数组

从 JDK9 开始，我们可以通过Arrays.compare()方法按字典顺序比较两个数组。既然不需要重新发明轮子，那么就升级到 JDK9，让我们深入研究一下。

两个数组的词典比较可能返回以下结果：

0，如果给定数组相等并且包含相同顺序的相同元素
如果第一个数组按字典顺序小于第二个数组，则值小于 0
如果第一个数组按字典顺序大于第二个数组，则该值大于 0

如果第一个数组的长度小于第二个数组的长度，则第一个数组在词典上小于第二个数组。如果数组具有相同的长度，包含原始类型，并且共享一个共同的前缀，那么字典比较就是比较两个元素的结果，精确地说就是Integer.compare(int, int)、Boolean.compare(boolean, boolean)、Byte.compare(byte, byte)等等。如果数组包含Object，那么字典比较依赖于给定的Comparator或Comparable实现。

首先，让我们考虑以下原始类型数组：

int[] integers1 = {3, 4, 5, 6, 1, 5};
int[] integers2 = {3, 4, 5, 6, 1, 5};
int[] integers3 = {3, 4, 5, 6, 1, 3};

现在，integers1在词典上等于integers2，因为它们相等并且包含相同顺序的相同元素，int compare(int[] a, int[] b)：

int i12 = Arrays.compare(integers1, integers2); // 0

但是，integers1在字典上大于integers3，因为它们共享相同的前缀（3，4，5，6，1），但是对于最后一个元素，Integer.compare(5,3)返回一个大于 0 的值，因为 5 大于 3：

int i13 = Arrays.compare(integers1, integers3); // 1

可以在不同的数组范围内进行词典比较。例如，下面的示例通过int compare(int[] a, int aFromIndex, int aToIndex, int[] b, int bFromIndex, int bToIndex)方法比较范围[3, 6]中的integers1和integers3：

int is13 = Arrays.compare(integers1, 3, 6, integers3, 3, 6); // 1

对于Object的数组，Arrays类还提供了一组专用的compare()方法。还记得Melon类吗？好吧，为了比较两个没有显式Comparator的Melon数组，我们需要实现Comparable接口和compareTo()方法。假设我们依赖于瓜的重量，如下所示：

public class Melon implements Comparable {

  private final String type;
  private final int weight;

  @Override
  public int compareTo(Object o) {
    Melon m = (Melon) o;

    return Integer.compare(this.getWeight(), m.getWeight());
  }

  // constructor, getters, equals() and hashCode() omitted for brevity
}

注意，Object数组的词典比较不依赖于equals()。它需要显式的Comparator或Comparable元素。

假设Melon的以下数组：

Melon[] melons1 = {new Melon("Horned", 1500), new Melon("Gac", 1000)};
Melon[] melons2 = {new Melon("Horned", 1500), new Melon("Gac", 1000)};
Melon[] melons3 = {new Melon("Hami", 1600), new Melon("Gac", 800)};

让我们通过<T extends Comparable<? super T>> int compare(T[] a, T[] b)将melons1与melons2进行词汇对比：

int m12 = Arrays.compare(melons1, melons2); // 0

因为melons1和melons2是相同的，所以结果是 0。

现在，让我们对melons1和melons3做同样的事情。这一次，结果将是否定的，这意味着在词典中，melons1小于melons3。这是真的，因为在指数 0 时，角瓜的重量是 1500 克，比哈密瓜的重量要轻，哈密瓜的重量是 1600 克：

int m13 = Arrays.compare(melons1, melons3); // -1

我们可以通过<T extends Comparable<? super T>> int compare(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex)方法在数组的不同范围内进行比较。例如，在公共范围[1, 2]中，melons1在字典上大于melons2，因为 Gac 的重量在melons1中为 1000g，在melons3中为 800g：

int ms13 = Arrays.compare(melons1, 1, 2, melons3, 1, 2); // 1

如果我们不想依赖Comparable元素（实现Comparable，我们可以通过<T> int compare(T[] a, T[] b, Comparator<? super T> cmp)方法传入一个Comparator：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);
int mt13 = Arrays.compare(melons1, melons3, byType); // 14

也可以通过<T> int compare(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex, Comparator<? super T> cmp)使用范围：

int mrt13 = Arrays.compare(melons1, 1, 2, melons3, 1, 2, byType); // 0

如果数字数组应该被无符号处理，那么依赖于一堆Arrays.compareUnsigned()方法，这些方法可用于byte、short、int和long。

根据String.compareTo()和int compareTo(String anotherString)按字典顺序比较两个字符串。

103 从数组创建流

一旦我们从一个数组中创建了一个Stream，我们就可以访问所有流 API。因此，这是一个方便的操作，这是很重要的，在我们的工具带。

让我们从字符串数组开始（也可以是其他对象）：

String[] arr = {"One", "Two", "Three", "Four", "Five"};

从这个String[]数组创建Stream最简单的方法是依赖于从 JDK8 开始的Arrays.stream()方法：

Stream<String> stream = Arrays.stream(arr);

或者，如果我们需要来自子数组的流，那么只需添加范围作为参数。例如，让我们从(0, 2)之间的元素创建一个Stream，即 1 到 2：

Stream<String> stream = Arrays.stream(arr, 0, 2);

同样的情况，但通过一个List可以写为：

Stream<String> stream = Arrays.asList(arr).stream();
Stream<String> stream = Arrays.asList(arr).subList(0, 2).stream();

另一种解决方案依赖于Stream.of()方法，如以下简单示例所示：

Stream<String> stream = Stream.of(arr);
Stream<String> stream = Stream.of("One", "Two", "Three");

从Stream创建数组可以通过Stream.toArray()方法完成。例如，一个简单的方法如下所示：

String[] array = stream.toArray(String[]::new);

另外，让我们考虑一个原始数组：

int[] integers = {2, 3, 4, 1};

在这种情况下，Arrays.stream()方法可以再次提供帮助，唯一的区别是返回的结果是IntStream类型（这是Stream的int原始类型特化）：

IntStream intStream = Arrays.stream(integers);

但是IntStream类还提供了一个of()方法，可以如下使用：

IntStream intStream = IntStream.of(integers);

有时，我们需要定义一个增量步长为 1 的有序整数的Stream。此外，Stream的大小应该等于数组的大小。特别是对于这种情况，IntStream方法提供了两种方法range(int inclusive, int exclusive)和rangeClosed(int startInclusive, int endInclusive)：

IntStream intStream = IntStream.range(0, integers.length);
IntStream intStream = IntStream.rangeClosed(0, integers.length);

从整数的Stream创建数组可以通过Stream.toArray()方法完成。例如，一个简单的方法如下所示：

int[] intArray = intStream.toArray();

// for boxed integers
int[] intArray = intStream.mapToInt(i -> i).toArray();

除了流的IntStream特化之外，JDK8 还提供long（LongStream）和double（DoubleStream）的特化。

104 数组的最小值、最大值和平均值

计算数组的最小值、最大值和平均值是一项常见的任务。让我们看看在函数式和命令式编程中解决这个问题的几种方法。

计算最大值和最小值

计算数字数组的最大值可以通过循环数组并通过与数组的每个元素进行比较来跟踪最大值来实现。就代码行而言，可以编写如下：

public static int max(int[] arr) {

  int max = arr[0];

  for (int elem: arr) {
    if (elem > max) {
      max = elem;
    }
  }

  return max;
}

在可读性方面，可能需要使用Math.max()方法而不是if语句：

...
max = Math.max(max, elem);
...

假设我们有以下整数数组和一个名为MathArrays的工具类，其中包含前面的方法：

int[] integers = {2, 3, 4, 1, -4, 6, 2};

该数组的最大值可以容易地获得如下：

int maxInt = MathArrays.max(integers); // 6

在 Java8 函数式风格中，此问题的解决方案需要一行代码：

int maxInt = Arrays.stream(integers).max().getAsInt();

在函数式方法中，max()方法返回一个OptionalInt。同样，我们有OptionalLong和OptionalDouble。

此外，我们假设一个对象数组，在本例中是一个Melon数组：

Melon[] melons = {
  new Melon("Horned", 1500), new Melon("Gac", 2200),
  new Melon("Hami", 1600), new Melon("Gac", 2100)
};

public class Melon implements Comparable {

  private final String type;
  private final int weight;

  @Override
  public int compareTo(Object o) {
    Melon m = (Melon) o;

    return Integer.compare(this.getWeight(), m.getWeight());
  }

  // constructor, getters, equals() and hashCode() omitted for brevity
}

很明显，我们前面定义的max()方法不能用于这种情况，但逻辑原理保持不变。这一次，实现应该依赖于Comparable或Comparator。基于Comparable的实现可以如下：

public static <T extends Comparable<T>> T max(T[] arr) {

  T max = arr[0];

  for (T elem : arr) {
    if (elem.compareTo(max) > 0) {
      max = elem;
   }
  }

  return max;
}

检查Melon.compareTo()方法，注意我们的实现将比较瓜的重量。因此，我们可以很容易地从我们的数组中找到最重的瓜，如下所示：

Melon maxMelon = MathArrays.max(melons); // Gac(2200g)

依赖于Comparator的实现可以写为：

public static <T> T max(T[] arr, Comparator<? super T> c) {

  T max = arr[0];

  for (T elem: arr) {
    if (c.compare(elem, max) > 0) {
      max = elem;
    }
  }

  return max;
}

并且，如果我们根据甜瓜的类型定义一个Comparator，我们有以下结果：

Comparator<Melon> byType = Comparator.comparing(Melon::getType);

然后，我们得到与字符串的词典比较相一致的最大值：

Melon maxMelon = MathArrays.max(melons, byType); // Horned(1500g)

在 Java8 函数式风格中，此问题的解决方案需要一行代码：

Melon maxMelon = Arrays.stream(melons).max(byType).orElseThrow();

计算平均值

计算一组数字（在本例中为整数）的平均值可以通过两个简单的步骤实现：

计算数组中元素的和。
将此总和除以数组的长度。

在代码行中，我们有以下内容：

public static double average(int[] arr) {

  return sum(arr) / arr.length;
}

public static double sum(int[] arr) {

  double sum = 0;

  for (int elem: arr) {
    sum += elem;
  }

  return sum;
}

整数数组的平均值为 2.0：

double avg = MathArrays.average(integers);

在 Java8 函数式风格中，此问题的解决方案需要一行代码：

double avg = Arrays.stream(integers).average().getAsDouble();

对于第三方库支持，请考虑 Apache Common Lang（ArrayUtil）和 Guava 的Chars、Ints、Longs以及其他类。

105 反转数组

这个问题有几种解决办法。它们中的一些改变了初始数组，而另一些只是返回一个新数组

假设以下整数数组：

int[] integers = {-1, 2, 3, 1, 4, 5, 3, 2, 22};

让我们从一个简单的实现开始，它将数组的第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，依此类推：

public static void reverse(int[] arr) {

  for (int leftHead = 0, rightHead = arr.length - 1; 
      leftHead < rightHead; leftHead++, rightHead--) {

    int elem = arr[leftHead];
    arr[leftHead] = arr[rightHead];
    arr[rightHead] = elem;
  }
}

前面的解决方案改变了给定的数组，这并不总是期望的行为。当然，我们可以修改它以返回一个新的数组，也可以依赖 Java8 函数样式，如下所示：

// 22, 2, 3, 5, 4, 1, 3, 2, -1
int[] reversed = IntStream.rangeClosed(1, integers.length)
  .map(i -> integers[integers.length - i]).toArray();

现在，让我们反转一个对象数组。为此，让我们考虑一下Melon类：

public class Melon {

  private final String type;
  private final int weight;

  // constructor, getters, equals(), hashCode() omitted for brevity
}

另外，让我们考虑一个Melon数组：

Melon[] melons = {
  new Melon("Crenshaw", 2000), 
  new Melon("Gac", 1200),
  new Melon("Bitter", 2200)
};

第一种解决方案需要使用泛型来塑造实现，该实现将数组的第一个元素与最后一个元素交换，将第二个元素与最后一个元素交换，依此类推：

public static <T> void reverse(T[] arr) {

  for (int leftHead = 0, rightHead = arr.length - 1; 
      leftHead < rightHead; leftHead++, rightHead--) {

    T elem = arr[leftHead];
    arr[leftHead] = arr[rightHead];
    arr[rightHead] = elem;
  }
}

因为我们的数组包含对象，所以我们也可以依赖于Collections.reverse()。我们只需要通过Arrays.asList()方法将数组转换成List：

// Bitter(2200g), Gac(1200g), Crenshaw(2000g)
Collections.reverse(Arrays.asList(melons));

前面的两个解决方案改变了数组的元素。Java8 函数式风格可以帮助我们避免这种变异：

// Bitter(2200g), Gac(1200g), Crenshaw(2000g)
Melon[] reversed = IntStream.rangeClosed(1, melons.length)
  .mapToObj(i -> melons[melons.length - i])
  .toArray(Melon[]:new);

对于第三方库支持，请考虑 Apache Common Lang（ArrayUtils.reverse()和 Guava 的Lists类。

106 填充和设置数组

有时，我们需要用一个固定值填充数组。例如，我们可能希望用值1填充整数数组。实现这一点的最简单方法依赖于一个for语句，如下所示：

int[] arr = new int[10];

// 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
for (int i = 0; i < arr.length; i++) {
  arr[i] = 1;
}

但我们可以通过Arrays.fill()方法将此代码简化为一行代码。对于基本体和对象，此方法有不同的风格。前面的代码可以通过Arrays.fill(int[] a, int val)重写如下：

// 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
Arrays.fill(arr, 1);

Arrays.fill() also come with flavors for filling up just a segment/range of an array. For integers, this method is fill(int[] a, int fromIndexInclusive, int toIndexExclusive, int val).

现在，应用一个生成函数来计算数组的每个元素怎么样？例如，假设我们要将每个元素计算为前一个元素加 1。最简单的方法将再次依赖于for语句，如下所示：

// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
for (int i = 1; i < arr.length; i++) {
  arr[i] = arr[i - 1] + 1;
}

根据需要应用于每个元素的计算，必须相应地修改前面的代码。

对于这样的任务，JDK8 附带了一系列的Arrays.setAll()和Arrays.parallelSetAll()方法。例如，前面的代码片段可以通过setAll(int[] array, IntUnaryOperator generator)重写如下：

// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Arrays.setAll(arr, t -> {
  if (t == 0) {
    return arr[t];
  } else {
    return arr[t - 1] + 1;
  }
});

除此之外，我们还有setAll(double[] array, IntToDoubleFunction generator)、setAll(long[] array, IntToLongFunction generator)和setAll(T[] array, IntFunction<? extends T> generator)。

根据生成器的功能，此任务可以并行完成，也可以不并行完成。例如，前面的生成器函数不能并行应用，因为每个元素都依赖于前面元素的值。尝试并行应用此生成器函数将导致不正确和不稳定的结果。

但是假设我们要取前面的数组（1，2，3，4，5，6，7，8，9，10），然后将每个偶数值乘以它本身，将每个奇数值减去 1。因为每个元素都可以单独计算，所以在这种情况下我们可以授权一个并行进程。这是Arrays.parallelSetAll()方法的完美工作。基本上，这些方法是用来并行化Arrays.setAll()方法的。

现在我们将parallelSetAll(int[] array, IntUnaryOperator generator)应用于这个数组：

// 0, 4, 2, 16, 4, 36, 6, 64, 8, 100
Arrays.parallelSetAll(arr, t -> {
  if (arr[t] % 2 == 0) {
    return arr[t] * arr[t];
  } else {
    return arr[t] - 1;
  }
});

对于每个Arrays.setAll()方法，都有一个Arrays.parallelSetAll()方法。

作为奖励，Arrays附带了一组名为parallelPrefix()的方法。这些方法对于将数学函数应用于数组的元素（累积和并发）非常有用。

例如，如果我们要将数组中的每个元素计算为前面元素的和，那么我们可以如下所示：

// 0, 4, 6, 22, 26, 62, 68, 132, 140, 240
Arrays.parallelPrefix(arr, (t, q) -> t + q);

107 下一个更大的元素

NGE 是一个涉及数组的经典问题。

基本上，有一个数组和它的一个元素e，我们要获取下一个（右侧）大于e的元素。例如，假设以下数组：

int[] integers = {1, 2, 3, 4, 12, 2, 1, 4};

获取每个元素的 NGE 将产生以下对（-1 被解释为右侧的元素不大于当前元素）：

1 : 2   2 : 3   3 : 4   4 : 12   12 : -1   2 : 4   1 : 4   4 : -1

这个问题的一个简单解决方案是循环每个元素的数组，直到找到一个更大的元素或者没有更多的元素要检查。如果我们只想在屏幕上打印对，那么我们可以编写一个简单的代码，如下所示：

public static void println(int[] arr) {

  int nge;
  int n = arr.length;

  for (int i = 0; i < n; i++) {
    nge = -1;
    for (int j = i + 1; j < n; j++) {
      if (arr[i] < arr[j]) {
        nge = arr[j];
        break;
      }
    }

    System.out.println(arr[i] + " : " + nge);
  }
}

另一个解决方案依赖于栈。主要是，我们在栈中推送元素，直到当前处理的元素大于栈中的顶部元素。当这种情况发生时，我们弹出那个元素。本书附带的代码中提供了解决方案。

108 更改数组大小

增加数组的大小并不简单。这是因为 Java 数组的大小是固定的，我们不能修改它们的大小。这个问题的解决方案需要创建一个具有所需大小的新数组，并将所有值从原始数组复制到这个数组中。这可以通过Arrays.copyOf()方法或System.arraycopy()（由Arrays.copyOf()内部使用）完成。

对于一个原始数组（例如，int），我们可以将数组的大小增加 1 后将值添加到数组中，如下所示：

public static int[] add(int[] arr, int item) {

  int[] newArr = Arrays.copyOf(arr, arr.length + 1);
  newArr[newArr.length - 1] = item;

  return newArr;
}

或者，我们可以删除最后一个值，如下所示：

public static int[] remove(int[] arr) {

  int[] newArr = Arrays.copyOf(arr, arr.length - 1);

  return newArr;
}

或者，我们可以按如下所示调整给定长度数组的大小：

public static int[] resize(int[] arr, int length) {

  int[] newArr = Arrays.copyOf(arr, arr.length + length);

  return newArr;
}

捆绑到本书中的代码还包含了System.arraycopy()备选方案。此外，它还包含泛型数组的实现。签名如下：

public static <T> T[] addObject(T[] arr, T item);
public static <T> T[] removeObject(T[] arr);
public static <T> T[] resize(T[] arr, int length);

在有利的背景下，让我们将一个相关的主题引入讨论：如何在 Java 中创建泛型数组。以下操作无效：

T[] arr = new T[arr_size]; // causes generic array creation error

有几种方法，但 Java 在copyOf(T[] original, int newLength)中使用以下代码：

// newType is original.getClass()
T[] copy = ((Object) newType == (Object) Object[].class) ?
  (T[]) new Object[newLength] :
  (T[]) Array.newInstance(newType.getComponentType(), newLength);

109 创建不可修改/不可变的集合

在 Java 中创建不可修改/不可变的集合可以很容易地通过Collections.unmodifiableFoo()方法（例如，unmodifiableList()）完成，并且从 JDK9 开始，通过来自List、Set、Map和其他接口的一组of()方法完成。

此外，我们将在一组示例中使用这些方法来获得不可修改/不可变的集合。主要目标是确定每个定义的集合是不可修改的还是不可变的。

在阅读本节之前，建议先阅读第 2 章、“对象、不变性和switch表达式”中有关不变性的问题。

好吧。对于原始类型来说，这非常简单。例如，我们可以创建一个不可变的整数List，如下所示：

private static final List<Integer> LIST 
  = Collections.unmodifiableList(Arrays.asList(1, 2, 3, 4, 5));

private static final List<Integer> LIST = List.of(1, 2, 3, 4, 5);

对于下一个示例，让我们考虑以下可变类：

public class MutableMelon {

  private String type;
  private int weight;

  // constructor omitted for brevity

  public void setType(String type) {
    this.type = type;
  }

  public void setWeight(int weight) {
    this.weight = weight;
  }

  // getters, equals() and hashCode() omitted for brevity
}

问题 1 (`Collections.unmodifiableList()`)

让我们通过Collections.unmodifiableList()方法创建MutableMelon列表：

// Crenshaw(2000g), Gac(1200g)
private final MutableMelon melon1 
  = new MutableMelon("Crenshaw", 2000);
private final MutableMelon melon2 
  = new MutableMelon("Gac", 1200);

private final List<MutableMelon> list 
  = Collections.unmodifiableList(Arrays.asList(melon1, melon2));

那么，list是不可修改的还是不变的？答案是不可更改的。虽然增变器方法会抛出UnsupportedOperationException，但底层的melon1和melon2是可变的。例如，我们把西瓜的重量设为0：

melon1.setWeight(0);
melon2.setWeight(0);

现在，列表将显示以下西瓜（因此列表发生了变异）：

Crenshaw(0g), Gac(0g)

问题 2 (`Arrays.asList()`)

我们直接在Arrays.asList()中硬编码实例，创建MutableMelon列表：

private final List<MutableMelon> list 
  = Collections.unmodifiableList(Arrays.asList(
    new MutableMelon("Crenshaw", 2000), 
    new MutableMelon("Gac", 1200)));

那么，这个列表是不可修改的还是不变的？答案是不可更改的。当增变器方法抛出UnsupportedOperationException时，硬编码实例可以通过List.get()方法访问。一旦可以访问它们，它们就可以变异：

MutableMelon melon1 = list.get(0);
MutableMelon melon2 = list.get(1);

melon1.setWeight(0);
melon2.setWeight(0);

现在，列表将显示以下西瓜（因此列表发生了变异）：

Crenshaw(0g), Gac(0g)

问题 3 (`Collections.unmodifiableList()`和静态块）

让我们通过Collections.unmodifiableList()方法和static块创建MutableMelon列表：

private static final List<MutableMelon> list;
static {
  final MutableMelon melon1 = new MutableMelon("Crenshaw", 2000);
  final MutableMelon melon2 = new MutableMelon("Gac", 1200);

  list = Collections.unmodifiableList(Arrays.asList(melon1, melon2));
}

那么，这个列表是不可修改的还是不变的？答案是不可更改的。虽然增变器方法会抛出UnsupportedOperationException，但是硬编码的实例仍然可以通过List.get()方法访问。一旦可以访问它们，它们就可以变异：

MutableMelon melon1l = list.get(0);
MutableMelon melon2l = list.get(1);

melon1l.setWeight(0);
melon2l.setWeight(0);

现在，列表将显示以下西瓜（因此列表发生了变异）：

Crenshaw(0g), Gac(0g)

问题 4 (`List.of()`)

让我们通过List.of()创建MutableMelon的列表：

private final MutableMelon melon1 
  = new MutableMelon("Crenshaw", 2000);
private final MutableMelon melon2 
  = new MutableMelon("Gac", 1200);

private final List<MutableMelon> list = List.of(melon1, melon2);

MutableMelon melon1l = list.get(0);
MutableMelon melon2l = list.get(1);

melon1l.setWeight(0);
melon2l.setWeight(0);

现在，列表将显示以下西瓜（因此列表发生了变异）：

Crenshaw(0g), Gac(0g)

对于下一个示例，让我们考虑以下不可变类：

public final class ImmutableMelon {

  private final String type;
  private final int weight;

  // constructor, getters, equals() and hashCode() omitted for brevity
}

问题 5（不可变）

现在我们通过Collections.unmodifiableList()和List.of()方法创建ImmutableMelon列表：

private static final ImmutableMelon MELON_1 
  = new ImmutableMelon("Crenshaw", 2000);
private static final ImmutableMelon MELON_2 
  = new ImmutableMelon("Gac", 1200);

private static final List<ImmutableMelon> LIST 
  = Collections.unmodifiableList(Arrays.asList(MELON_1, MELON_2));
private static final List<ImmutableMelon> LIST 
  = List.of(MELON_1, MELON_2);

那么，这个列表是不可修改的还是不变的？答案是不变的。增变器方法会抛出UnsupportedOperationException，我们不能对ImmutableMelon的实例进行变异。

根据经验，如果集合是通过unmodifiableFoo()或of()方法定义的，并且包含可变数据，则集合是不可修改的；如果集合是不可修改的，并且包含可变数据（包括原始类型），则集合是不可修改的。

需要注意的是，不可穿透的不变性应该考虑 Java 反射 API 和类似的 API，它们在操作代码时具有辅助功能。

对于第三方库支持，请考虑 Apache Common Collection、UnmodifiableList（和同伴）和 Guava 的ImmutableList（和同伴）。

在Map的情况下，我们可以通过unmodifiableMap()或Map.of()方法创建一个不可修改/不可修改的Map。

但我们也可以通过Collections.emptyMap()创建一个不可变的空Map：

Map<Integer, MutableMelon> emptyMap = Collections.emptyMap();

与emptyMap()类似，我们有Collections.emptyList()和Collections.emptySet()。在返回一个Map、List或Set的方法中，这些方法作为返回非常方便，我们希望避免返回null。

或者，我们可以通过Collections.singletonMap(K key, V value)用单个元素创建一个不可修改/不可变的Map：

// unmodifiable
Map<Integer, MutableMelon> mapOfSingleMelon 
  = Collections.singletonMap(1, new MutableMelon("Gac", 1200));

// immutable
Map<Integer, ImmutableMelon> mapOfSingleMelon 
  = Collections.singletonMap(1, new ImmutableMelon("Gac", 1200));

类似于singletonMap()，我们有singletonList()和singleton()。后者用于Set。

此外，从 JDK9 开始，我们可以通过一个名为ofEntries()的方法创建一个不可修改的Map。此方法以Map.Entry为参数，如下例所示：

// unmodifiable Map.Entry containing the given key and value
import static java.util.Map.entry;
...
Map<Integer, MutableMelon> mapOfMelon = Map.ofEntries(
  entry(1, new MutableMelon("Apollo", 3000)),
  entry(2, new MutableMelon("Jade Dew", 3500)),
  entry(3, new MutableMelon("Cantaloupe", 1500))
);

或者，不可变的Map是另一种选择：

Map<Integer, ImmutableMelon> mapOfMelon = Map.ofEntries(
  entry(1, new ImmutableMelon("Apollo", 3000)),
  entry(2, new ImmutableMelon("Jade Dew", 3500)),
  entry(3, new ImmutableMelon("Cantaloupe", 1500))
);

另外，可以通过 JDK10 从可修改/可变的Map中获得不可修改/不可变的Map，Map.copyOf(Map<? extends K,? extends V> map)方法：

Map<Integer, ImmutableMelon> mapOfMelon = new HashMap<>();
mapOfMelon.put(1, new ImmutableMelon("Apollo", 3000));
mapOfMelon.put(2, new ImmutableMelon("Jade Dew", 3500));
mapOfMelon.put(3, new ImmutableMelon("Cantaloupe", 1500));

Map<Integer, ImmutableMelon> immutableMapOfMelon 
  = Map.copyOf(mapOfMelon);

作为这一节的奖励，让我们来讨论一个不可变数组。

问题：我能用 Java 创建一个不可变数组吗？

答案：不可以。或者。。。有一种方法可以在 Java 中生成不可变数组：

static final String[] immutable = new String[0];

因此，Java 中所有有用的数组都是可变的。但是我们可以在Arrays.copyOf()的基础上创建一个辅助类来创建不可变数组，它复制元素并创建一个新数组（在幕后，这个方法依赖于System.arraycopy()。

因此，我们的辅助类如下所示：

import java.util.Arrays;

public final class ImmutableArray<T> {

  private final T[] array;

  private ImmutableArray(T[] a) {
    array = Arrays.copyOf(a, a.length);
  }

  public static <T> ImmutableArray<T> from(T[] a) {
    return new ImmutableArray<>(a);
  }

  public T get(int index) {
    return array[index];
  }

  // equals(), hashCode() and toString() omitted for brevity
}

用法示例如下：

ImmutableArray<String> sample =
  ImmutableArray.from(new String[] {
    "a", "b", "c"
  });

110 映射的默认值

在 JDK8 之前，这个问题的解决方案依赖于辅助方法，它基本上检查Map中给定键的存在，并返回相应的值或默认值。这种方法可以在工具类中编写，也可以通过扩展Map接口来编写。通过返回默认值，我们可以避免在Map中找不到给定键时返回null。此外，这是依赖默认设置或配置的方便方法。

从 JDK8 开始，这个问题的解决方案包括简单地调用Map.getOrDefault()方法。此方法获取两个参数，分别表示要在Map方法中查找的键和默认值。当找不到给定的键时，默认值充当应该返回的备份值。

例如，假设下面的Map封装了多个数据库及其默认的host:port：

Map<String, String> map = new HashMap<>();
map.put("postgresql", "127.0.0.1:5432");
map.put("mysql", "192.168.0.50:3306");
map.put("cassandra", "192.168.1.5:9042");

我们来看看这个Map是否也包含 Derby DB 的默认host:port：

map.get("derby"); // null

由于映射中没有 Derby DB，因此结果将是null。这不是我们想要的。实际上，当搜索到的数据库不在映射上时，我们可以在69:89.31.226:27017上使用 MongoDB，它总是可用的。现在，我们可以很容易地将此行为塑造为：

// 69:89.31.226:27017
String hp1 = map.getOrDefault("derby", "69:89.31.226:27017");

// 192.168.0.50:3306
String hp2 = map.getOrDefault("mysql", "69:89.31.226:27017");

这种方法可以方便地建立流利的表达式，避免中断代码进行null检查。请注意，返回默认值并不意味着该值将被添加到Map。Map保持不变。

111 计算映射中是否不存在/存在

有时，Map并不包含我们需要的准确的开箱即用条目。此外，当条目不存在时，返回默认条目也不是一个选项。基本上，有些情况下我们需要计算我们的入口。

对于这种情况，JDK8 提供了一系列方法：compute()、computeIfAbsent()、computeIfPresent()和merge()。在这些方法之间进行选择是一个非常了解每种方法的问题。

现在让我们通过示例来看看这些方法的实现。

示例 1（`computeIfPresent()`）

假设我们有以下Map：

Map<String, String> map = new HashMap<>();
map.put("postgresql", "127.0.0.1");
map.put("mysql", "192.168.0.50");

我们使用这个映射为不同的数据库类型构建 JDBC URL。

假设我们要为 MySQL 构建 JDBC URL。如果映射中存在mysql键，则应根据相应的值jdbc:mysql://192.168.0.50/customers_db计算 JDBC URL。但是如果不存在mysql键，那么 JDBC URL 应该是null。除此之外，如果我们的计算结果是null（无法计算 JDBC URL），那么我们希望从映射中删除这个条目。

这是V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)的工作。

在我们的例子中，用于计算新值的BiFunction如下所示（k是映射中的键，v是与键关联的值）：

BiFunction<String, String, String> jdbcUrl 
  = (k, v) -> "jdbc:" + k + "://" + v + "/customers_db";

一旦我们有了这个函数，我们就可以计算出mysql键的新值，如下所示：

// jdbc:mysql://192.168.0.50/customers_db
String mySqlJdbcUrl = map.computeIfPresent("mysql", jdbcUrl);

由于映射中存在mysql键，结果将是jdbc:mysql://192.168.0.50/customers_db，新映射包含以下条目：

postgresql=127.0.0.1, mysql=jdbc:mysql://192.168.0.50/customers_db

再次调用computeIfPresent()将重新计算值，这意味着它将导致类似mysql= jdbc:mysql://jdbc:mysql://....的结果。显然，这是不可以的，所以请注意这方面。

另一方面，如果我们对一个不存在的条目进行相同的计算（例如，voltdb），那么返回的值将是null，映射保持不变：

// null
String voldDbJdbcUrl = map.computeIfPresent("voltdb", jdbcUrl);

示例 2（`computeIfAbsent()`）

假设我们有以下Map：

Map<String, String> map = new HashMap<>();
map.put("postgresql", "jdbc:postgresql://127.0.0.1/customers_db");
map.put("mysql", "jdbc:mysql://192.168.0.50/customers_db");

我们使用这个映射为不同的数据库构建 JDBC URL。

假设我们要为 MongoDB 构建 JDBC URL。这一次，如果映射中存在mongodb键，则应返回相应的值，而无需进一步计算。但是如果这个键不存在（或者与一个null值相关联），那么它应该基于这个键和当前 IP 进行计算并添加到映射中。如果计算值为null，则返回结果为null，映射保持不变。

嗯，这是V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)的工作。

在我们的例子中，用于计算值的Function将如下所示（第一个String是映射中的键（k），而第二个String是为该键计算的值）：

String address = InetAddress.getLocalHost().getHostAddress();

Function<String, String> jdbcUrl 
  = k -> k + "://" + address + "/customers_db";

基于此函数，我们可以尝试通过mongodb键获取 MongoDB 的 JDBC URL，如下所示：

// mongodb://192.168.100.10/customers_db
String mongodbJdbcUrl = map.computeIfAbsent("mongodb", jdbcUrl);

因为我们的映射不包含mongodb键，它将被计算并添加到映射中。

如果我们的Function被求值为null，那么映射保持不变，返回值为null。

再次调用computeIfAbsent()不会重新计算值。这次，由于mongodb在映射中（在上一次调用中添加），所以返回的值将是mongodb://192.168.100.10/customers_db。这与尝试获取mysql的 JDBC URL 是一样的，它将返回jdbc:mysql://192.168.0.50/customers_db，而无需进一步计算。

示例 3（`compute()`）

假设我们有以下Map：

Map<String, String> map = new HashMap<>();
map.put("postgresql", "127.0.0.1");
map.put("mysql", "192.168.0.50");

我们使用这个映射为不同的数据库类型构建 JDBC URL。

假设我们要为 MySQL 和 Derby DB 构建 JDBC URL。在这种情况下，不管键（mysql还是derby存在于映射中，JDBC URL 都应该基于相应的键和值（可以是null）来计算。另外，如果键存在于映射中，并且我们的计算结果是null（无法计算 JDBC URL），那么我们希望从映射中删除这个条目。基本上，这是computeIfPresent()和computeIfAbsent()的组合。

这是V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)的工作。

此时，应写入BiFunction以覆盖搜索键的值为null时的情况：

String address = InetAddress.getLocalHost().getHostAddress();
BiFunction<String, String, String> jdbcUrl = (k, v) 
  -> "jdbc:" + k + "://" + ((v == null) ? address : v) 
    + "/customers_db";

现在，让我们计算 MySQL 的 JDBC URL。因为mysql键存在于映射中，所以计算将依赖于相应的值192.168.0.50。结果将更新映射中mysql键的值：

// jdbc:mysql://192.168.0.50/customers_db
String mysqlJdbcUrl = map.compute("mysql", jdbcUrl);

另外，让我们计算 Derby DB 的 JDBC URL。由于映射中不存在derby键，因此计算将依赖于当前 IP。结果将被添加到映射的derby键下：

// jdbc:derby://192.168.100.10/customers_db
String derbyJdbcUrl = map.compute("derby", jdbcUrl);

在这两次计算之后，映射将包含以下三个条目：

postgresql=127.0.0.1
derby=jdbc:derby://192.168.100.10/customers_db
mysql=jdbc:mysql://192.168.0.50/customers_db

请注意，再次调用compute()将重新计算值。这可能导致不需要的结果，如jdbc:derby://jdbc:derby://...。如果计算的结果是null（例如 JDBC URL 无法计算），并且映射中存在键（例如mysql），那么这个条目将从映射中删除，返回的结果是null。

示例 4（`merge()`）

假设我们有以下Map：

Map<String, String> map = new HashMap<>();
map.put("postgresql", "9.6.1 ");
map.put("mysql", "5.1 5.2 5.6 ");

我们使用这个映射来存储每个数据库类型的版本，这些版本之间用空格隔开。

现在，假设每次发布数据库类型的新版本时，我们都希望将其添加到对应键下的映射中。如果键（例如，mysql）存在于映射中，那么我们只需将新版本连接到当前值的末尾。如果键（例如，derby）不在映射中，那么我们现在只想添加它。

这是V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)的完美工作。

如果给定的键（K与某个值没有关联或与null关联，那么新的值将是V。如果给定键（K与非null值相关联，则基于给定的BiFunction计算新值。如果此BiFunction的结果是null，并且该键存在于映射中，则此条目将从映射中删除。

在我们的例子中，我们希望将当前值与新版本连接起来，因此我们的BiFunction可以写为：

BiFunction<String, String, String> jdbcUrl = String::concat;

我们在以下方面也有类似的情况：

BiFunction<String, String, String> jdbcUrl 
  = (vold, vnew) -> vold.concat(vnew);

例如，假设我们希望在 MySQL 的映射版本 8.0 中连接。这可以通过以下方式实现：

// 5.1 5.2 5.6 8.0
String mySqlVersion = map.merge("mysql", "8.0 ", jdbcUrl);

稍后，我们还将连接 9.0 版：

// 5.1 5.2 5.6 8.0 9.0
String mySqlVersion = map.merge("mysql", "9.0 ", jdbcUrl);

或者，我们添加 Derby DB 的版本10.11.1.1。这将导致映射中出现一个新条目，因为不存在derby键：

// 10.11.1.1
String derbyVersion = map.merge("derby", "10.11.1.1 ", jdbcUrl);

在这三个操作结束时，映射条目如下所示：

postgresql=9.6.1, derby=10.11.1.1, mysql=5.1 5.2 5.6 8.0 9.0

示例 5（`putIfAbsent()`）

假设我们有以下Map：

Map<Integer, String> map = new HashMap<>();
map.put(1, "postgresql");
map.put(2, "mysql");
map.put(3, null);

我们使用这个映射来存储一些数据库类型的名称。

现在，假设我们希望基于以下约束在该映射中包含更多数据库类型：

如果给定的键存在于映射中，那么只需返回相应的值并保持映射不变。
如果给定的键不在映射中（或者与一个null值相关联），则将给定的值放入映射并返回null。

嗯，这是putIfAbsent(K key, V value)的工作。

以下三种尝试不言自明：

String v1 = map.putIfAbsent(1, "derby");     // postgresql
String v2 = map.putIfAbsent(3, "derby");     // null
String v3 = map.putIfAbsent(4, "cassandra"); // null

映射内容如下：

1=postgresql, 2=mysql, 3=derby, 4=cassandra

112 从映射中删除

从Map中删除可以通过一个键或者一个键和值来完成。

例如，假设我们有以下Map：

Map<Integer, String> map = new HashMap<>();
map.put(1, "postgresql");
map.put(2, "mysql");
map.put(3, "derby");

通过键删除就像调用V Map.remove(Object key)方法一样简单。如果给定键对应的条目删除成功，则返回关联值，否则返回null。

检查以下示例：

String r1 = map.remove(1); // postgresql
String r2 = map.remove(4); // null

现在，映射包含以下条目（已删除键 1 中的条目）：

2=mysql, 3=derby

从 JDK8 开始，Map接口被一个新的remove()标志方法所丰富，该方法具有以下签名：boolean remove(Object key, Object value)。使用这种方法，只有在给定的键和值之间存在完美匹配时，才能从映射中删除条目。基本上，这种方法是以下复合条件的捷径：map.containsKey(key) && Objects.equals(map.get(key), value)。

让我们举两个简单的例子：

// true
boolean r1 = map.remove(2, "mysql");

// false (the key is present, but the values don't match)
boolean r2 = map.remove(3, "mysql");

结果映射包含一个剩余条目3=derby。

迭代和从Map中移除至少可以通过两种方式来完成：第一，通过Iterator（捆绑代码中存在的解决方案），第二，从 JDK8 开始，我们可以通过removeIf(Predicate<? super E> filter)来完成：

map.entrySet().removeIf(e -> e.getValue().equals("mysql"));

有关从集合中删除的更多详细信息，请参见“删除集合中与谓词匹配的所有元素”。

113 替换映射中的条目

从Map替换条目是一个在很多情况下都会遇到的问题。要实现这一点并避免在辅助方法中编写一段意大利面条代码，方便的解决方案依赖于 JDK8replace()方法。

假设我们有下面的Melon类和Melon的映射：

public class Melon {

  private final String type;
  private final int weight;

  // constructor, getters, equals(), hashCode(),
  // toString() omitted for brevity
}

Map<Integer, Melon> mapOfMelon = new HashMap<>();
mapOfMelon.put(1, new Melon("Apollo", 3000));
mapOfMelon.put(2, new Melon("Jade Dew", 3500));
mapOfMelon.put(3, new Melon("Cantaloupe", 1500));

通过V replace(K key, V value)可以完成按键 2 对应的甜瓜的更换。如果替换成功，则此方法将返回初始的Melon：

// Jade Dew(3500g) was replaced
Melon melon = mapOfMelon.replace(2, new Melon("Gac", 1000));

现在，映射包含以下条目：

1=Apollo(3000g), 2=Gac(1000g), 3=Cantaloupe(1500g)

此外，假设我们想用键 1 和阿波罗甜瓜（3000g）替换条目。所以，甜瓜应该是同一个，才能获得成功的替代品。这可以通过布尔值replace(K key, V oldValue, V newValue)实现。此方法依赖于equals()合同来比较给定的值，因此Melon需要执行equals()方法，否则结果不可预知：

// true
boolean melon = mapOfMelon.replace(
  1, new Melon("Apollo", 3000), new Melon("Bitter", 4300));

现在，映射包含以下条目：

1=Bitter(4300g), 2=Gac(1000g), 3=Cantaloupe(1500g)

最后，假设我们要根据给定的函数替换Map中的所有条目。这可以通过void replaceAll(BiFunction<? super K,? super V,? extends V> function)完成。

例如，将所有重量超过 1000g 的瓜替换为重量等于 1000g 的瓜，下面的BiFunction形成了这个函数（k是键，v是Map中每个条目的值）：

BiFunction<Integer, Melon, Melon> function = (k, v) 
  -> v.getWeight() > 1000 ? new Melon(v.getType(), 1000) : v;

接下来，replaceAll()出现在现场：

mapOfMelon.replaceAll(function);

现在，映射包含以下条目：

1=Bitter(1000g), 2=Gac(1000g), 3=Cantaloupe(1000g)

114 比较两个映射

只要我们依赖于Map.equals()方法，比较两个映射是很简单的。在比较两个映射时，该方法使用Object.equals()方法比较它们的键和值。

例如，让我们考虑两个具有相同条目的瓜映射（在Melon类中必须存在equals()和hashCode()：

public class Melon {

  private final String type;
  private final int weight;

  // constructor, getters, equals(), hashCode(),
  // toString() omitted for brevity
}

Map<Integer, Melon> melons1Map = new HashMap<>();
Map<Integer, Melon> melons2Map = new HashMap<>();
melons1Map.put(1, new Melon("Apollo", 3000));
melons1Map.put(2, new Melon("Jade Dew", 3500));
melons1Map.put(3, new Melon("Cantaloupe", 1500));
melons2Map.put(1, new Melon("Apollo", 3000));
melons2Map.put(2, new Melon("Jade Dew", 3500));
melons2Map.put(3, new Melon("Cantaloupe", 1500));

现在，如果我们测试melons1Map和melons2Map是否相等，那么我们得到true：

boolean equals12Map = melons1Map.equals(melons2Map); // true

但如果我们使用数组，这将不起作用。例如，考虑下面两个映射：

Melon[] melons1Array = {
  new Melon("Apollo", 3000),
  new Melon("Jade Dew", 3500), new Melon("Cantaloupe", 1500)
};
Melon[] melons2Array = {
  new Melon("Apollo", 3000),
  new Melon("Jade Dew", 3500), new Melon("Cantaloupe", 1500)
};

Map<Integer, Melon[]> melons1ArrayMap = new HashMap<>();
melons1ArrayMap.put(1, melons1Array);
Map<Integer, Melon[]> melons2ArrayMap = new HashMap<>();
melons2ArrayMap.put(1, melons2Array);

即使melons1ArrayMap和melons2ArrayMap相等，Map.equals()也会返回false：

boolean equals12ArrayMap = melons1ArrayMap.equals(melons2ArrayMap);

这个问题源于这样一个事实：数组的equals()方法比较的是标识，而不是数组的内容。为了解决这个问题，我们可以编写一个辅助方法如下（这次依赖于Arrays.equals()，它比较数组的内容）：

public static <A, B> boolean equalsWithArrays(
    Map<A, B[]> first, Map<A, B[]> second) {

  if (first.size() != second.size()) {
    return false;
  }

  return first.entrySet().stream()
    .allMatch(e -> Arrays.equals(e.getValue(), 
      second.get(e.getKey())));
}

115 对映射排序

排序一个Map有几种解决方案。首先，假设Melon中的Map：

public class Melon implements Comparable {

  private final String type;
  private final int weight;

  @Override
  public int compareTo(Object o) {
    return Integer.compare(this.getWeight(), ((Melon) o).getWeight());
  }

  // constructor, getters, equals(), hashCode(),
  // toString() omitted for brevity
}

Map<String, Melon> melons = new HashMap<>();
melons.put("delicious", new Melon("Apollo", 3000));
melons.put("refreshing", new Melon("Jade Dew", 3500));
melons.put("famous", new Melon("Cantaloupe", 1500));

现在，让我们来研究几种排序这个Map的解决方案。基本上，我们的目标是通过一个名为Maps的工具类公开以下屏幕截图中的方法：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wWHuvVoj-1657077783917)(img/68fea7e5-dde3-48c3-af33-d0701244c43e.png)]

让我们在下一节中看看不同的解决方案。

通过`TreeMap`和自然排序按键排序

对Map进行排序的快速解决方案依赖于TreeMap。根据定义，TreeMap中的键按其自然顺序排序。此外，TreeMap还有一个TreeMap(Map<? extends K,? extends V> m)类型的构造器：

public static <K, V> TreeMap<K, V> sortByKeyTreeMap(Map<K, V> map) {

  return new TreeMap<>(map);
}

调用它将按键对映射进行排序：

// {delicious=Apollo(3000g), 
// famous=Cantaloupe(1500g), refreshing=Jade Dew(3500g)}
TreeMap<String, Melon> sortedMap = Maps.sortByKeyTreeMap(melons);

通过流和比较器按键和值排序

一旦我们为映射创建了一个Stream，我们就可以很容易地用Stream.sorted()方法对它进行排序，不管有没有Comparator。这一次，让我们使用一个Comparator：

public static <K, V> Map<K, V> sortByKeyStream(
    Map<K, V> map, Comparator<? super K> c) {

  return map.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey(c))
    .collect(toMap(Map.Entry::getKey, Map.Entry::getValue,
      (v1, v2) -> v1, LinkedHashMap::new));
}

public static <K, V> Map<K, V> sortByValueStream(
    Map<K, V> map, Comparator<? super V> c) {

  return map.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByValue(c))
    .collect(toMap(Map.Entry::getKey, Map.Entry::getValue,
      (v1, v2) -> v1, LinkedHashMap::new));
}

我们需要依赖LinkedHashMap而不是HashMap。否则，我们就不能保持迭代顺序。

让我们把映射分类如下：

// {delicious=Apollo(3000g), 
//  famous=Cantaloupe(1500g), 
//  refreshing=Jade Dew(3500g)}
Comparator<String> byInt = Comparator.naturalOrder();
Map<String, Melon> sortedMap = Maps.sortByKeyStream(melons, byInt);

// {famous=Cantaloupe(1500g), 
//  delicious=Apollo(3000g), 
//  refreshing=Jade Dew(3500g)}
Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight);
Map<String, Melon> sortedMap 
  = Maps.sortByValueStream(melons, byWeight);

通过列表按键和值排序

前面的示例对给定的映射进行排序，结果也是一个映射。如果我们只需要排序的键（我们不关心值），反之亦然，那么我们可以依赖于通过Map.keySet()创建的List作为键，通过Map.values()创建的List作为值：

public static <K extends Comparable, V> List<K>
    sortByKeyList(Map<K, V> map) {

  List<K> list = new ArrayList<>(map.keySet());
  Collections.sort(list);

  return list;
}

public static <K, V extends Comparable> List<V>
    sortByValueList(Map<K, V> map) {

  List<V> list = new ArrayList<>(map.values());
  Collections.sort(list);

  return list;
}

现在，让我们对映射进行排序：

// [delicious, famous, refreshing]
List<String> sortedKeys = Maps.sortByKeyList(melons);

// [Cantaloupe(1500g), Apollo(3000g), Jade Dew(3500g)]
List<Melon> sortedValues = Maps.sortByValueList(melons);

如果不允许重复值，则必须依赖于使用SortedSet的实现：

SortedSet<String> sortedKeys = new TreeSet<>(melons.keySet());
SortedSet<Melon> sortedValues = new TreeSet<>(melons.values());

116 复制哈希映射

执行HashMap的浅拷贝的简便解决方案依赖于HashMap构造器HashMap(Map<? extends K,? extends V> m)。以下代码是不言自明的：

Map<K, V> mapToCopy = new HashMap<>();
Map<K, V> shallowCopy = new HashMap<>(mapToCopy);

另一种解决方案可能依赖于putAll(Map<? extends K,? extends V> m)方法。此方法将指定映射中的所有映射复制到此映射，如以下助手方法所示：

@SuppressWarnings("unchecked")
public static <K, V> HashMap<K, V> shallowCopy(Map<K, V> map) {

  HashMap<K, V> copy = new HashMap<>();
  copy.putAll(map);

  return copy;
}

我们还可以用 Java8 函数式风格编写一个辅助方法，如下所示：

@SuppressWarnings("unchecked")
public static <K, V> HashMap<K, V> shallowCopy(Map<K, V> map) {

  Set<Entry<K, V>> entries = map.entrySet();
  HashMap<K, V> copy = (HashMap<K, V>) entries.stream()
    .collect(Collectors.toMap(
       Map.Entry::getKey, Map.Entry::getValue));

  return copy;
}

然而，这三种解决方案只提供了映射的浅显副本。获取深度拷贝的解决方案可以依赖于克隆库在第 2 章中介绍，“对象、不变性和switch表达式”。将使用克隆的助手方法可以编写如下：

@SuppressWarnings("unchecked") 
public static <K, V> HashMap<K, V> deepCopy(Map<K, V> map) {
  Cloner cloner = new Cloner();
  HashMap<K, V> copy = (HashMap<K, V>) cloner.deepClone(map);

  return copy;
}

117 合并两个映射

合并两个映射是将两个映射合并为一个包含两个映射的元素的映射的过程。此外，对于键碰撞，我们将属于第二个映射的值合并到最终映射中。但这是一个设计决定。

让我们考虑以下两个映射（我们特意为键 3 添加了一个冲突）：

public class Melon {

  private final String type;
  private final int weight;

  // constructor, getters, equals(), hashCode(),
  // toString() omitted for brevity
}

Map<Integer, Melon> melons1 = new HashMap<>();
Map<Integer, Melon> melons2 = new HashMap<>();
melons1.put(1, new Melon("Apollo", 3000));
melons1.put(2, new Melon("Jade Dew", 3500));
melons1.put(3, new Melon("Cantaloupe", 1500));
melons2.put(3, new Melon("Apollo", 3000));
melons2.put(4, new Melon("Jade Dew", 3500));
melons2.put(5, new Melon("Cantaloupe", 1500));

从 JDK8 开始，我们在Map: V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)中有以下方法。

如果给定的键（K与值没有关联，或者与null关联，那么新的值将是V。如果给定键（K与非null值相关联，则基于给定的BiFunction计算新值。如果此BiFunction的结果是null，并且该键存在于映射中，则此条目将从映射中删除。

基于这个定义，我们可以编写一个辅助方法来合并两个映射，如下所示：

public static <K, V> Map<K, V> mergeMaps(
    Map<K, V> map1, Map<K, V> map2) {  

  Map<K, V> map = new HashMap<>(map1);

  map2.forEach(
    (key, value) -> map.merge(key, value, (v1, v2) -> v2));

  return map;
}

请注意，我们不会修改原始映射。我们更希望返回一个包含第一个映射的元素与第二个映射的元素合并的新映射。在键冲突的情况下，我们用第二个映射（v2中的值替换现有值。

基于Stream.concat()可以编写另一个解决方案。基本上，这种方法将两个流连接成一个Stream。为了从一个Map创建一个Stream，我们称之为Map.entrySet().stream()。在连接从给定映射创建的两个流之后，我们只需通过toMap()收集器收集结果：

public static <K, V> Map<K, V> mergeMaps(
    Map<K, V> map1, Map<K, V> map2) {

  Stream<Map.Entry<K, V>> combined 
    = Stream.concat(map1.entrySet().stream(), 
      map2.entrySet().stream());

  Map<K, V> map = combined.collect(
    Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
      (v1, v2) -> v2));

  return map;
}

作为奖励，Set（例如，整数的Set可以按如下方式排序：

List<Integer> sortedList = someSetOfIntegers.stream()
  .sorted().collect(Collectors.toList());

对于对象，依赖于sorted(Comparator<? super T>。

118 删除集合中与谓词匹配的所有元素

我们的集合将收集一堆Melon：

public class Melon {

  private final String type;
  private final int weight;

  // constructor, getters, equals(), 
  // hashCode(), toString() omitted for brevity
}

让我们在整个示例中假设以下集合（ArrayList，以演示如何从集合中移除与给定谓词匹配的元素：

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

让我们看看下面几节给出的不同解决方案。

通过迭代器删除

通过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：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vkjf4fim-1657077783917)(img/da9ace7a-fd80-4dc8-905a-278b00375fa2.png)]

在第一步（步骤 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 的步骤顺序：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xOTb4X3N-1657077783918)(img/04ad9477-0450-4037-82eb-690f9696f63b.png)]

因此，在代码行中，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) {
    ...
  }
}

插入 Trie

现在，让我们关注在 Trie 中插入单词的算法：

将当前节点视为根节点。
从第一个字符开始，逐字符循环给定的单词。
如果当前节点（Map<Character, Node>）为当前字符映射一个值（Node），那么只需前进到该节点。否则，新建一个Node，将其字符设置为当前字符，并前进到此节点。
重复步骤 2（传递到下一个字符），直到单词的结尾。
将当前节点标记为完成单词的节点。

在代码行方面，我们有以下内容：

public void insert(String word) {

  Node node = root;

  for (int i = 0; i < word.length(); i++) {
    char ch = word.charAt(i);
    Function function = k -> new Node();

    node = node.getChildren().computeIfAbsent(ch, function);
  }

  node.setWord(true);
}

插入的复杂度为O(n)，其中n表示字长。

搜索 Trie

现在，让我们在 Trie 中搜索一个单词：

将当前节点视为根节点。
逐字符循环给定的单词（从第一个字符开始）。
对于每个字符，检查其在 Trie 中的存在性（在Map<Character, Node>中）。
如果字符不存在，则返回false。
从第 2 步开始重复，直到单词结束。
如果是单词，则在单词末尾返回true，如果只是前缀，则返回false。

在代码行方面，我们有以下内容：

public boolean contains(String word) {

  Node node = root;

  for (int i = 0; i < word.length(); i++) {
    char ch = word.charAt(i);
    node = node.getChildren().get(ch);

    if (node == null) {
      return false;
    }
  }

  return node.isWord();
}

查找的复杂度为O(n)，其中n表示字长。

从 Trie 中删除

最后，让我们尝试从 Trie 中删除：

验证给定的单词是否是 Trie 的一部分。
如果它是 Trie 的一部分，那么只需移除它。

使用递归并遵循以下规则，以自下而上的方式进行删除：

如果给定的单词不在 Trie 中，那么什么也不会发生（返回false）
如果给定的单词是唯一的（不是另一个单词的一部分），则删除所有相应的节点（返回true）
如果给定的单词是 Trie 中另一个长单词的前缀，则将叶节点标志设置为false（返回false）
如果给定的单词至少有另一个单词作为前缀，则从给定单词的末尾删除相应的节点，直到最长前缀单词的第一个叶节点（返回false）

在代码行方面，我们有以下内容：

public boolean delete(String word) {
  return delete(root, word, 0);
}

private boolean delete(Node node, String word, int position) {

  if (word.length() == position) {
    if (!node.isWord()) {
      return false;
    }

    node.setWord(false);

    return node.getChildren().isEmpty();
  }

  char ch = word.charAt(position);
  Node children = node.getChildren().get(ch);

  if (children == null) {
    return false;
  }

  boolean deleteChildren = delete(children, word, position + 1);

  if (deleteChildren && !children.isWord()) {
    node.getChildren().remove(ch);

    return node.getChildren().isEmpty();
  }

  return false;
}

查找的复杂度为O(n)，其中n表示字长。

现在，我们可以构建一个 Trie，如下所示：

Trie trie = new Trie();
trie.insert/contains/delete(...);

125 元组

基本上，元组是由多个部分组成的数据结构。通常，元组有两到三个部分。通常，当需要三个以上的部分时，一个专用类是更好的选择。

元组是不可变的，每当我们需要从一个方法返回多个结果时就使用元组。例如，假设有一个方法返回数组的最小值和最大值。通常，一个方法不能同时返回这两个值，使用元组是一个方便的解决方案。

不幸的是，Java 不提供内置元组支持。然而，Java 附带了Map.Entry<K,V>，用于表示来自Map的条目。此外，从 JDK9 开始，Map接口被一个名为entry(K k, V v)的方法丰富，该方法返回一个包含给定键和值的不可修改的Map.Entry<K, V>。

对于一个由两部分组成的元组，我们可以编写如下方法：

public static <T> Map.Entry<T, T> array(
    T[] arr, Comparator<? super T> c) {

  T min = arr[0];
  T max = arr[0];

  for (T elem: arr) {
    if (c.compare(min, elem) > 0) {
      min = elem;
    } else if (c.compare(max, elem)<0) {
      max = elem;
    }
  }

  return entry(min, max);
}

如果这个方法存在于一个名为Bounds的类中，那么我们可以如下调用它：

public class Melon {

  private final String type;
  private final int weight;

  // constructor, getters, equals(), hashCode(),
  // toString() omitted for brevity
}

Melon[] melons = {
  new Melon("Crenshaw", 2000), new Melon("Gac", 1200),
  new Melon("Bitter", 2200), new Melon("Hami", 800)
};

Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight);
Map.Entry<Melon, Melon> minmax = Bounds.array(melons, byWeight);

System.out.println("Min: " + minmax1.getKey());   // Hami(800g)
System.out.println("Max: " + minmax1.getValue()); // Bitter(2200g)

但我们也可以编写一个实现。一个由两部分组成的元组通常被称为一个对；因此，一个直观的实现可以如下所示：

public final class Pair<L, R> {

  final L left;
  final R right;

  public Pair(L left, R right) {
    this.left = left;
    this.right = right;
  }

  static <L, R> Pair<L, R> of (L left, R right) {

    return new Pair<>(left, right);
  }

  // equals() and hashCode() omitted for brevity
}

现在，我们可以重写计算最小值和最大值的方法，如下所示：

public static <T> Pair<T, T> array(T[] arr, Comparator<? super T> c) {
  ...
  return Pair.of(min, max);
}

126 并查集

并查算法在不相交集数据结构上运行。

不相交的集合数据结构定义了在某些不相交的子集中分离的元素集合，这些子集是不重叠的。从图形上看，我们可以用三个子集表示不相交集，如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iaVfBm9A-1657077783918)(img/15039898-6c0a-4ebd-9eb9-c4daef5aecf0.png)]

在代码中，不相交集表示为：

n是元素的总数（例如，在上图中，n是 11）。
rank是一个用 0 初始化的数组，用于决定如何合并两个具有多个元素的子集（具有较低rank的子集成为具有较高rank的子集的子子集）。
parent是允许我们构建基于数组的并查的数组（最初为parent[0] = 0; parent[1] = 1; ... parent[10] = 10;）：

public DisjointSet(int n) {

  this.n = n;
  rank = new int[n];
  parent = new int[n];

  initializeDisjointSet();
}

并查算法主要应具备以下功能：

将两个子集合并为一个子集
返回给定元素的子集（这对于查找同一子集中的元素很有用）

为了在内存中存储不相交的集合数据结构，我们可以将它表示为一个数组。最初，在数组的每个索引处，我们存储该索引（x[i] = i。每个索引可以映射到一段对我们有意义的信息，但这不是强制性的。例如，这样一个数组的形状可以如下图所示（最初，我们有 11 个子集，每个元素都是它自己的父元素）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a6xz1ouh-1657077783919)(img/ba9b8954-73d6-4bd1-985d-c0440bd7f127.png)]

或者，如果我们使用数字，我们可以用下图来表示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mBEnMhsP-1657077783919)(img/e9d26d14-2c11-448e-941f-e158edd1947c.png)]

在代码行方面，我们有以下内容：

private void initializeDisjointSet() {

  for (int i = 0; i < n; i++) {
    parent[i] = i;
  }
}

此外，我们需要通过并集操作来定义我们的子集。我们可以通过（父、子对）序列来定义子集。例如，让我们定义以下三对-union(0,1);、union(4, 9);和union(6, 5);。每次一个元素（子集）成为另一个元素（子集）的子元素时，它都会修改其值以反映其父元素的值，如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kWc5umWc-1657077783919)(img/342345bb-564b-4498-bcb6-e65203a4656c.png)]

这个过程一直持续到我们定义了所有的子集。例如，我们可以添加更多的联合-union(0, 7);、union(4, 3);、union(4, 2);、union(6, 10);和union(4, 5);。这将产生以下图形表示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cJ0yGoiI-1657077783920)(img/d2d1886f-9742-4158-840f-501262d12031.png)]

根据经验，建议将较小的子集合并为较大的子集，反之亦然。例如，检查包含4的子集与包含5的子集相统一的时刻。此时，4是子集的父项，它有三个子项（2、3、9），而5紧挨着10，6的两个子项。因此，包含5的子集有三个节点（6、5、10），而包含4的子集有四个节点（4、2、3、9）。因此，4成为6的父，并且隐含地成为5的父。

在代码行中，这是rank[]数组的工作：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zAXfAF2g-1657077783920)(img/314916a2-237a-4366-a08f-3b9f73abdbb3.png)]

现在让我们看看如何实现find和union操作

实现查找操作

查找给定元素的子集是一个递归过程，通过跟随父元素遍历子集，直到当前元素是其自身的父元素（根元素）：

public int find(int x) {

  if (parent[x] == x) {
    return x;
  } else {
    return find(parent[x]);
  }
}

实现并集操作

并集操作首先获取给定子集的根元素。此外，如果这两个根是不同的，它们需要依赖于它们的秩来决定哪一个将成为另一个的父（较大的秩将成为父）。如果它们的等级相同，则选择其中一个并将其等级增加 1：

public void union(int x, int y) {

  int xRoot = find(x);
  int yRoot = find(y);

  if (xRoot == yRoot) {
    return;
  }

  if (rank[xRoot] < rank[yRoot]) {
    parent[xRoot] = yRoot;
  } else if (rank[yRoot] < rank[xRoot]) {
    parent[yRoot] = xRoot;
  } else {
    parent[yRoot] = xRoot;
    rank[xRoot]++;
  }
}

好吧。现在让我们定义一个不相交集：

DisjointSet set = new DisjointSet(11);
set.union(0, 1);
set.union(4, 9);
set.union(6, 5);
set.union(0, 7);
set.union(4, 3);
set.union(4, 2);
set.union(6, 10);
set.union(4, 5);

现在让我们来玩玩它：

// is 4 and 0 friends => false
System.out.println("Is 4 and 0 friends: " 
  + (set.find(0) == set.find(4)));

// is 4 and 5 friends => true
System.out.println("Is 4 and 5 friends: " 
  + (set.find(4) == set.find(5)));

该算法可以通过压缩元素间的路径来优化。例如，检查下图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8eyQtDe0-1657077783921)(img/4cf68dd2-b2c2-40bf-baae-969b28f3f902.png)]

在左侧，在寻找5的父代时，必须经过6直到4。同样，在寻找10的父代时，必须经过6，直到4为止。然而，在右侧，我们通过直接链接到4来压缩5和10的路径。这一次，我们不需要通过中间元素就可以找到5和10的父代。

路径压缩可以针对find()操作进行，如下所示：

public int find(int x) {

  if (parent[x] != x) {
    return parent[x] = find(parent[x]);
  }

  return parent[x];
}

捆绑到本书中的代码包含两个应用，有路径压缩和没有路径压缩。

127 Fenwick 树或二叉索引树

芬威克树（FT）或二叉索引树（BIT）是为存储对应于另一给定数组的和而构建的数组。构建数组的大小与给定数组的大小相同，并且构建数组的每个位置（或节点）都存储给定数组中某些元素的总和。由于 BIT 存储给定数组的部分和，因此通过避免索引之间的循环和计算和，它是计算给定数组中两个给定索引（范围和/查询）之间的元素和的非常有效的解决方案。

位可以在线性时间或O(n log n)中构造。显然，我们更喜欢线性时间，所以让我们看看如何做到这一点。我们从给定的（原始）数组开始，该数组可以是（下标表示数组中的索引）：

3(1), 1(2), 5(3), 8(4), 12(5), 9(6), 7(7), 13(8), 0(9), 3(10), 1(11), 4(12), 9(13), 0(14), 11(15), 5(16)

构建位的想法依赖于最低有效位（LSB)概念。更准确地说，假设我们正在处理索引中的元素，a。那么，紧靠我们上方的值必须位于索引b，其中b = a + LSB(a)。为了应用该算法，索引 0 的值必须是 0；因此，我们操作的数组如下：

0(0), 3(1), 1(2), 5(3), 8(4), 12(5), 9(6), 7(7), 13(8), 0(9), 3(10), 1(11), 4(12), 9(13), 0(14), 11(15), 5(16)

现在，让我们应用算法的几个步骤，用和填充位。在位的索引 0 处，我们有 0。此外，我们使用b = a + LSB(a)公式计算剩余和，如下所示：

a=1：如果a=1=0b00001，则b=0b00001+0b00001=1+1=2=0b00010。我们说 2 负责a（也就是 1）。因此，在位中，在索引 1 处，我们存储值 3，在索引 2 处，我们存储值的和，3+1=4。
a=2：如果a=2=0b00010，则b=0b00010+0b00010=2+2=4=0b00100。我们说 4 负责a（即 2）。因此，在索引 4 处，我们以位的形式存储值的和，8+4=12。
a=3：如果a=3=0b00011，则b=0b00011+0b00001=3+1=4=0b00100。我们说 4 负责a（也就是 3）。因此，在位中，在索引 4 处，我们存储值的和，12+5=17。
a=4。如果a=4=0b00100，则b=0b00100+0b00100=4+4=8=0b01000。我们说 8 负责a（也就是 4）。因此，在位中，在索引 8 处，我们存储值的和，13+17=30。

算法将以相同的方式继续，直到位完成。在图形表示中，我们的案例可以如下所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lHUvmnuT-1657077783921)(img/73588a84-ac0f-4c97-9916-e907a74b3f2d.png)]

如果索引的计算点超出了界限，那么只需忽略它。

在代码行中，前面的流的形状可以如下所示（值是给定的数组）：

public class FenwickTree {

  private final int n;
  private long[] tree;
  ...

  public FenwickTree(long[] values) {

    values[0] = 0 L;
    this.n = values.length;
    tree = values.clone();

    for (int i = 1; i < n; i++) {

      int parent = i + lsb(i);
      if (parent < n) {
        tree[parent] += tree[i];
      }
    }
  }

  private static int lsb(int i) {

      return i & -i;

      // or
      // return Integer.lowestOneBit(i);
    }

    ...
}

现在，位准备好了，我们可以执行更新和范围查询。

例如，为了执行范围求和，我们必须获取相应的范围并将它们相加。请考虑下图右侧的几个示例，以快速了解此过程：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gDcEdCdw-1657077783922)(img/0fa4928e-5819-457a-85b5-7c438cc46019.png)]

就代码行而言，这可以很容易地形成如下形状：

public long sum(int left, int right) {

  return prefixSum(right) - prefixSum(left - 1);
}

private long prefixSum(int i) {

  long sum = 0L;

  while (i != 0) {
    sum += tree[i];
    i &= ~lsb(i); // or, i -= lsb(i);
  }

  return sum;
}

此外，我们还可以增加一个新的值：

public void add(int i, long v) {

  while (i < n) {
    tree[i] += v;
    i += lsb(i);
  }
}

我们还可以为某个索引设置一个新值：

public void set(int i, long v) {
  add(i, v - sum(i, i));
}

具备所有这些功能后，我们可以按如下方式为数组创建位：

FenwickTree tree = new FenwickTree(new long[] {
  0, 3, 1, 5, 8, 12, 9, 7, 13, 0, 3, 1, 4, 9, 0, 11, 5
});

然后我们可以玩它：

long sum29 = tree.sum(2, 9); // 55
tree.set(4, 3);
tree.add(4, 5);

128 布隆过滤器

布隆过滤器是一种快速高效的数据结构，能够提供问题的概率答案“值 X 在给定的集合中吗？”

通常情况下，当集合很大且大多数搜索算法都面临内存和速度问题时，此算法非常有用。

布隆过滤器的速度和内存效率来自这样一个事实，即该数据结构依赖于位数组（例如，java.util.BitSet）。最初，该数组的位被设置为0或false。

比特数组是布隆过滤器的第一个主要组成部分。第二个主要成分由一个或多个哈希函数组成。理想情况下，这些是成对独立的和均匀分布的散列函数。另外，非常重要的是要非常快。murrur、fnv系列和HashMix是一些散列函数，它们在布鲁姆过滤器可以接受的范围内遵守这些约束。

现在，当我们向布隆过滤器添加一个元素时，我们需要对这个元素进行散列（通过每个可用的散列函数传递它），并将这些散列的索引处的位数组中的位设置为1或true。

下面的代码片段应该可以阐明主要思想：

private BitSet bitset; // the array of bits
private static final Charset CHARSET = StandardCharsets.UTF_8;
...
public void add(T element) {

  add(element.toString().getBytes(CHARSET));
}

public void add(byte[] bytes) {

  int[] hashes = hash(bytes, numberOfHashFunctions);

  for (int hash: hashes) {
    bitset.set(Math.abs(hash % bitSetSize), true);
  }

  numberOfAddedElements++;
}

现在，当我们搜索一个元素时，我们通过相同的散列函数传递这个元素。此外，我们检查结果值是否在位数组中标记为1或true。如果不是，那么元素肯定不在集合中。但如果它们是，那么我们就以一定的概率知道元素在集合中。这不是 100% 确定的，因为另一个元素或元素的组合可能已经翻转了这些位。错误答案称为假正例。

在代码行方面，我们有以下内容：

private BitSet bitset; // the array of bits
private static final Charset CHARSET = StandardCharsets.UTF_8;
...

public boolean contains(T element) {

  return contains(element.toString().getBytes(CHARSET));
}

public boolean contains(byte[] bytes) {

  int[] hashes = hash(bytes, numberOfHashFunctions);

  for (int hash: hashes) {
    if (!bitset.get(Math.abs(hash % bitSetSize))) {

      return false;
    }
  }

  return true;
}

在图形表示中，我们可以用大小为 11 的位数组和三个哈希函数来表示布隆过滤器，如下所示（我们添加了两个元素）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2waQRhdB-1657077783922)(img/98ef7cb6-4c89-4d32-a26f-564448fffb33.png)]

显然，我们希望尽可能减少假正例的数量。虽然我们不能完全消除它们，但我们仍然可以通过调整位数组的大小、哈希函数的数量和集合中元素的数量来影响它们的速率。

以下数学公式可用于塑造最佳布隆过滤器：

过滤器中的项数（可根据m、k、p估计）：

n = ceil(m / (-k / log(1 - exp(log(p) / k))));

假正例的概率，介于 0 和 1 之间的分数，或表示p中的 1 的数量：

p = pow(1 - exp(-k / (m / n)), k);

过滤器中的位数（或按 KB、KiB、MB、MB、GiB 等表示的大小）：

m = ceil((n * log(p)) / log(1 / pow(2, log(2))));

散列函数个数（可根据m和n估计）：

k = round((m / n) * log(2));

根据经验，一个较大的过滤器比一个较小的过滤器具有更少的假正例。此外，通过增加散列函数的数量，我们可以获得较少的假正例，但我们会减慢过滤器的速度，并将其快速填充。布隆过滤器的性能为O(h)，其中h是散列函数的个数。

在本书附带的代码中，有一个布隆过滤器的实现，它使用基于 SHA-256 和 murrur 的散列函数。由于这段代码太大，无法在本书中列出，因此请考虑将Main类中的示例作为起点。

总结

本章涵盖了涉及数组、集合和几个数据结构的 30 个问题。虽然涉及数组和集合的问题是日常工作的一部分，但涉及数据结构的问题引入了一些不太知名（但功能强大）的数据结构，如并查集和 Trie。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-07-06，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap

编程算法

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

hashmap

编程算法

java