Java数组元素频率统计：全面解析与性能优化379

在日常的编程任务中，我们经常需要对数据进行分析和统计。其中一个非常常见且基础的需求是：给定一个整数数组（或其他数字类型），统计其中每个数字出现的次数，即计算其频率。这个问题在数据分析、算法竞赛、面试以及各种实际应用场景中都非常普遍。本文将作为一名专业的Java程序员，深入探讨在Java中解决“数组数字次数”问题（即统计数组元素频率）的多种方法，从基础到高级，从效率到代码简洁性，并对它们的性能、适用场景进行详细分析和比较。

理解问题与核心挑战

我们需要解决的问题是：给定一个int[]数组（例如[1, 2, 3, 2, 1, 4, 5, 4]），输出每个数字及其出现的次数。理想的输出可能是一个Map（例如{1=2, 2=2, 3=1, 4=2, 5=1}）或者其他方便后续处理的数据结构。核心挑战在于如何高效地遍历数组，记录每个元素的出现次数，并处理重复元素，最终得到正确的统计结果。

我们将从以下几个主要方面展开讨论：
使用排序（Sorting）与遍历
使用哈希表（HashMap）
使用计数数组（Counting Array / Frequency Array）
Java 8 Stream API
性能比较与选择建议
高级考量与扩展

一、方法一：排序与遍历

这种方法的核心思想是：首先对数组进行排序，这样所有相同的数字都会相邻。然后，我们只需要遍历一次已排序的数组，就可以轻松地统计每个数字出现的次数。

实现步骤：
使用()对数组进行升序排序。
遍历排序后的数组。维护一个当前数字和其出现次数的计数器。
当遇到与当前数字不同的新数字时，将上一个数字及其计数结果保存起来，并重置计数器开始统计新数字。

代码示例：import ;
import ;
import ;
public class ArrayFrequencySorted {
public static Map<Integer, Integer> getFrequenciesSorted(int[] arr) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
if (arr == null || == 0) {
return frequencyMap;
}
// 步骤1：对数组进行排序
(arr); // 时间复杂度 O(N log N)
// 步骤2&3：遍历排序后的数组进行计数
int currentNum = arr[0];
int count = 1;
for (int i = 1; i < ; i++) {
if (arr[i] == currentNum) {
count++;
} else {
(currentNum, count);
currentNum = arr[i];
count = 1;
}
}
// 处理数组中最后一个数字的频率
(currentNum, count);
return frequencyMap;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 2, 1, 4, 5, 4};
("原始数组: " + (arr1));
Map<Integer, Integer> freqMap1 = getFrequenciesSorted(arr1);
("频率统计 (排序法): " + freqMap1); // 输出: {1=2, 2=2, 3=1, 4=2, 5=1}
int[] arr2 = {7, 7, 7, 7, 7};
("原始数组: " + (arr2));
Map<Integer, Integer> freqMap2 = getFrequenciesSorted(arr2);
("频率统计 (排序法): " + freqMap2); // 输出: {7=5}
int[] arr3 = {};
("原始数组: " + (arr3));
Map<Integer, Integer> freqMap3 = getFrequenciesSorted(arr3);
("频率统计 (排序法): " + freqMap3); // 输出: {}
}
}

性能分析：
时间复杂度： 主要取决于排序算法。Java中()对于原始类型数组使用双轴快速排序（Dual-Pivot Quicksort），平均时间复杂度为O(N log N)。后续的遍历是O(N)。因此，总的时间复杂度为O(N log N)。
空间复杂度： ()在某些情况下可能需要O(log N)到O(N)的额外空间（取决于具体实现和数据特性）。我们创建了一个HashMap来存储结果，最坏情况下（所有元素都不同）需要O(N)的空间。因此，总的空间复杂度为O(N)。

优点： 逻辑相对直观，不需要额外的复杂数据结构（除了排序算法内部可能使用的）。

缺点： 排序操作会改变原数组的顺序（如果需要保留原顺序，需要复制一份），且O(N log N)的性能对于大数据量可能不是最优。

二、方法二：使用哈希表（HashMap）

这是在实际开发中最常用且推荐的方法之一，因为它通常能提供最佳的平均时间复杂度。HashMap允许我们以O(1)的平均时间复杂度进行插入和查找操作。

实现步骤：
创建一个HashMap<Integer, Integer>，其中键（Key）表示数组中的数字，值（Value）表示该数字出现的次数。
遍历数组中的每个数字。
对于每个数字：

如果HashMap中已经存在该数字作为键，则将其对应的值（计数）加1。
如果HashMap中不存在该数字作为键，则将其作为新键插入，并将值初始化为1。

代码示例：import ;
import ;
import ;
public class ArrayFrequencyHashMap {
public static Map<Integer, Integer> getFrequenciesHashMap(int[] arr) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
if (arr == null || == 0) {
return frequencyMap;
}
// 遍历数组，利用HashMap进行计数
for (int num : arr) {
// 使用 getOrDefault 方法可以简化代码
(num, (num, 0) + 1);

// 等价于以下传统写法：
// if ((num)) {
// (num, (num) + 1);
// } else {
// (num, 1);
// }
}
return frequencyMap;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 2, 1, 4, 5, 4};
("原始数组: " + (arr1));
Map<Integer, Integer> freqMap1 = getFrequenciesHashMap(arr1);
("频率统计 (HashMap法): " + freqMap1);
int[] arr2 = {7, 7, 7, 7, 7};
("原始数组: " + (arr2));
Map<Integer, Integer> freqMap2 = getFrequenciesHashMap(arr2);
("频率统计 (HashMap法): " + freqMap2);
int[] arr3 = {};
("原始数组: " + (arr3));
Map<Integer, Integer> freqMap3 = getFrequenciesHashMap(arr3);
("频率统计 (HashMap法): " + freqMap3);
}
}

性能分析：
时间复杂度： 遍历数组一次，每次操作（插入或更新）在HashMap中平均为O(1)。在最坏情况下（哈希冲突严重），可能退化为O(N)，但实际应用中很少发生。因此，总的平均时间复杂度为O(N)。
空间复杂度： HashMap需要存储每个唯一的数字及其计数。在最坏情况下（所有数字都不同），需要O(N)的空间。

优点： 效率高，平均时间复杂度为O(N)，不改变原数组顺序。代码简洁易懂，适用范围广（可处理负数、非整数、字符串等）。

缺点： 需要额外的空间来存储HashMap。

三、方法三：使用计数数组（Counting Array / Frequency Array）

这种方法在特定条件下非常高效：当数组中的数字范围已知且相对较小，并且是非负整数时。我们可以直接使用一个数组的索引来代表数字，索引处的值代表该数字出现的次数。

实现步骤：
确定数组中数字的最大值（或最大绝对值）。创建一个大小为(maxValue + 1)的计数数组，并初始化所有元素为0。
遍历原始数组中的每个数字。
对于每个数字num，将其作为索引，将计数数组中对应索引位置的值加1，即countArray[num]++。
遍历计数数组，非零的索引值即为对应数字的频率。

代码示例：import ;
import ;
import ;
public class ArrayFrequencyCountingArray {
public static Map<Integer, Integer> getFrequenciesCountingArray(int[] arr) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
if (arr == null || == 0) {
return frequencyMap;
}
// 步骤1：找到数组中的最大值，确定计数数组的大小
int maxVal = arr[0];
for (int i = 1; i < ; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
// 如果包含负数，需要调整索引映射，这里假设都是非负数
if (maxVal < 0) {
("错误：计数数组法不适用于所有数字都是负数的情况（除非进行索引偏移）");
return frequencyMap; // 或者抛出异常
}
// 创建计数数组
int[] counts = new int[maxVal + 1]; // 索引代表数字，值代表频率
// 步骤2&3：遍历原始数组进行计数
for (int num : arr) {
if (num >= 0 && num <= maxVal) { // 确保数字在有效范围内
counts[num]++;
} else {
// 处理超出范围的数字，例如负数或大于maxVal的数字
// 对于本方法，这通常意味着该方法不适用或需要扩展
("警告：数字 " + num + " 超出计数数组范围，将被忽略。");
}
}
// 步骤4：将计数数组结果转换回Map
for (int i = 0; i < ; i++) {
if (counts[i] > 0) {
(i, counts[i]);
}
}
return frequencyMap;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 2, 1, 4, 5, 4}; // 0-5
("原始数组: " + (arr1));
Map<Integer, Integer> freqMap1 = getFrequenciesCountingArray(arr1);
("频率统计 (计数数组法): " + freqMap1); // {1=2, 2=2, 3=1, 4=2, 5=1}
int[] arr2 = {7, 7, 7, 7, 7}; // 0-7
("原始数组: " + (arr2));
Map<Integer, Integer> freqMap2 = getFrequenciesCountingArray(arr2);
("频率统计 (计数数组法): " + freqMap2); // {7=5}
int[] arr3 = {0, 0, 1, 10, 5}; // 0-10
("原始数组: " + (arr3));
Map<Integer, Integer> freqMap3 = getFrequenciesCountingArray(arr3);
("频率统计 (计数数组法): " + freqMap3); // {0=2, 1=1, 5=1, 10=1}

// 尝试一个包含负数的数组 (此实现不支持)
// int[] arr4 = {-1, 0, 1, 0, -1};
// ("原始数组: " + (arr4));
// Map freqMap4 = getFrequenciesCountingArray(arr4);
// ("频率统计 (计数数组法): " + freqMap4);
}
}

处理负数扩展： 如果数组包含负数，我们可以找到最小值和最大值，然后创建一个大小为(max - min + 1)的计数数组。在存储时，将数字num映射到索引num - min；在取出时，将索引i映射回数字i + min。

性能分析：
时间复杂度： 第一次遍历找到最大值是O(N)，第二次遍历填充计数数组是O(N)，第三次遍历计数数组生成结果是O(MaxVal)。因此，总时间复杂度为O(N + MaxVal)。
空间复杂度： 计数数组的大小为O(MaxVal)，HashMap同样是O(U)（U为唯一元素数量，最坏O(N)）。因此，总的空间复杂度是O(MaxVal) + O(N)，主要受MaxVal影响。

优点： 当MaxVal相对较小（例如10万以内）时，这种方法非常快，甚至可以比HashMap更快，因为它避免了哈希计算和对象封装的开销。

缺点：

对数据范围有严格限制：只适用于非负整数，且数字范围不能太大，否则会导致巨大的计数数组，浪费内存或超出内存限制。
无法直接处理负数、浮点数或非整数类型。

四、方法四：Java 8 Stream API

Java 8引入的Stream API提供了一种声明式、函数式编程的风格来处理集合数据。对于频率统计，它提供了非常简洁且功能强大的解决方案，尤其适用于需要链式操作的场景。

实现步骤：
将数组转换为流（Stream）。
使用()进行分组操作。传入一个函数将元素本身作为分组的键。
使用()作为下游收集器，计算每个分组中元素的数量。

代码示例：import ;
import ;
import ;
import ;
public class ArrayFrequencyStream {
public static Map<Integer, Long> getFrequenciesStream(int[] arr) {
if (arr == null || == 0) {
return new HashMap<>();
}
// 使用 Stream API 结合 进行频率统计
// () 表示以元素本身作为Map的Key
// () 表示以计数作为Map的Value (返回类型是Long)
return (arr) // 将 int[] 转换为 IntStream
.boxed() // 将 IntStream 转换为 Stream<Integer> (因为groupingBy需要对象流)
.collect(((), ()));
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 2, 1, 4, 5, 4};
("原始数组: " + (arr1));
Map<Integer, Long> freqMap1 = getFrequenciesStream(arr1);
("频率统计 (Stream API法): " + freqMap1); // 输出: {1=2, 2=2, 3=1, 4=2, 5=1}
int[] arr2 = {7, 7, 7, 7, 7};
("原始数组: " + (arr2));
Map<Integer, Long> freqMap2 = getFrequenciesStream(arr2);
("频率统计 (Stream API法): " + freqMap2); // 输出: {7=5}
int[] arr3 = {};
("原始数组: " + (arr3));
Map<Integer, Long> freqMap3 = getFrequenciesStream(arr3);
("频率统计 (Stream API法): " + freqMap3); // 输出: {}
}
}

性能分析：
时间复杂度： Stream API的内部实现通常是基于迭代的，类似于HashMap方法。因此，平均时间复杂度为O(N)。但是，由于Stream的包装、拆箱、函数调用和额外的对象创建，其常数因子可能比手动实现的HashMap方法略高。
空间复杂度： 与HashMap方法类似，需要O(N)的空间来存储HashMap。

优点： 代码极其简洁、可读性强，符合现代Java的函数式编程风格。能够优雅地处理各种复杂的分组和聚合需求。

缺点： 在纯粹的性能方面，对于大规模数据集，可能略逊于手工优化的HashMap循环。返回的计数类型是Long，可能需要额外的类型转换。

五、性能比较与选择建议

下表总结了各种方法的性能特点和适用场景：


方法
时间复杂度 (平均)
空间复杂度
优点
缺点
适用场景




排序与遍历
O(N log N)
O(N)
逻辑直观，不依赖额外数据结构（Map除外）
改变原数组，性能非最优
数组较小，或后续需要排序结果，或不介意性能


哈希表 (HashMap)
O(N)
O(N)
平均性能最优，不改变原数组，适用范围广
需要额外空间，哈希冲突可能影响最坏情况性能
最常用、最通用、推荐方案


计数数组
O(N + MaxVal)
O(MaxVal)
当MaxVal小且非负时非常快
限制数字范围，无法处理负数/浮点数，MaxVal过大时浪费内存
数字范围小且非负（如学生分数、年龄等）


Stream API
O(N)
O(N)
代码简洁、声明式、函数式风格
常数因子可能略高，返回Long类型
追求代码简洁性，或复杂聚合场景，数据量非极端大

选择建议：
通用首选： HashMap方法。它在大多数情况下提供了最佳的平衡点：优秀的平均时间复杂度、良好的可读性，并且能够处理各种类型的数字（包括负数、浮点数，甚至字符串或其他对象）。
特定优化： 如果你确定数组中的数字都是非负整数，且其最大值非常小（例如几千到几十万），那么计数数组方法可能会比HashMap更快，因为它避免了哈希计算的开销。
代码简洁性： 如果你更偏爱函数式编程风格，并且不追求极致的微秒级性能，Java 8 Stream API提供了最简洁的解决方案。
历史遗留或特定算法需求： 排序与遍历方法在某些特定算法（例如需要先排序再处理的）中可能被考虑，但作为通用的频率统计，它不是最优解。

六、高级考量与扩展

1. 处理大数据量与内存限制

如果数组包含数十亿甚至更多的数字，且无法一次性加载到内存中，那么上述所有基于内存的方法都将失效。这时需要考虑：
外部排序（External Sorting）： 将数据分块排序，然后合并。但这通常更适用于排序而非简单计数。
流式处理（Streaming Algorithms）： 如果数据以流的形式到来，或者可以通过迭代器访问，可以考虑使用像Flume、Kafka Streams、Spark Streaming等框架进行实时或批处理。
分布式计算： 使用Hadoop MapReduce或Spark等分布式框架，将计数任务分发到多个节点并行处理。

2. 并发环境下的频率统计

如果在多线程环境下进行频率统计，HashMap不是线程安全的。你需要使用线程安全的替代品：
ConcurrentHashMap：提供高并发的哈希表实现，适用于读多写少的场景。
使用()：将普通HashMap包装成线程安全的，但性能可能不如ConcurrentHashMap。
AtomicInteger作为值：在ConcurrentHashMap中，可以将值存储为AtomicInteger，以原子方式更新计数。

import ;
import ;
public class ConcurrentArrayFrequency {
public static Map<Integer, AtomicInteger> getFrequenciesConcurrent(int[] arr) {
ConcurrentHashMap<Integer, AtomicInteger> frequencyMap = new ConcurrentHashMap<>();
if (arr == null || == 0) {
return frequencyMap;
}
// 使用并行流进行计数
(arr).parallel().forEach(num ->
(num, k -> new AtomicInteger(0)).incrementAndGet()
);
return frequencyMap;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 1, 4, 5, 4, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
Map<Integer, AtomicInteger> freqMap = getFrequenciesConcurrent(arr);
("并发频率统计: " + freqMap); // 输出: {1=AtomicInteger[3], 2=AtomicInteger[3], ...}

// 转换成普通Map<Integer, Integer>
Map<Integer, Integer> finalMap = new HashMap<>();
((k, v) -> (k, ()));
("转换后: " + finalMap);
}
}

3. 使用第三方库：Guava 的 Multiset

Google Guava库提供了一个非常有用的集合类型Multiset（多重集），它专门设计用来统计元素出现的次数。Multiset的行为类似于一个集合，但允许包含重复元素，并且提供方便的API来获取元素的计数。import ;
import ;
import ;
public class ArrayFrequencyGuava {
public static Multiset<Integer> getFrequenciesGuava(int[] arr) {
Multiset<Integer> multiset = ();
if (arr == null || == 0) {
return multiset;
}
for (int num : arr) {
(num);
}
return multiset;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 2, 1, 4, 5, 4};
("原始数组: " + (arr1));
Multiset<Integer> freqMultiset1 = getFrequenciesGuava(arr1);
("频率统计 (Guava Multiset): " + freqMultiset1); // 输出: [1 x 2, 2 x 2, 3, 4 x 2, 5]
("数字 1 的次数: " + (1)); // 输出: 2
}
}

Multiset在内部通常也是通过哈希表实现，因此其性能特征与HashMap类似，但API更加专注于计数场景，使用起来更直观。

本文全面探讨了在Java中统计数组数字频率的多种方法，包括经典的排序与遍历、高效的哈希表、受限但快速的计数数组以及简洁的Java 8 Stream API。每种方法都有其独特的优点和适用场景。作为专业的程序员，我们应根据具体的业务需求（如数据量大小、数字范围、性能要求、代码可读性以及并发需求等）来选择最合适的方案。

在大多数通用场景下，使用HashMap进行频率统计是效率和灵活性的最佳平衡点。对于追求极致简洁的现代Java代码，Stream API提供了优雅的替代方案。而当面临特定约束（如小范围非负整数）时，计数数组则能提供无与伦比的性能。理解这些方法的内部机制和权衡取舍，将使我们能够编写出更健壮、更高效的Java代码。

2026-04-05

下一篇：精通Java方法重载：从概念到实战的全面指南