技术面试通常会提出一些问题来测试您对集合的理解，尤其是HashMaps。一个常见的挑战涉及计算列表中元素的出现次数。这个问题可以帮助面试官评估您有效处理数据聚合并避免NullPointerException等陷阱的能力。

如果您是 HashMap 新手，在深入研究本文之前，您可能需要查看我的破解 HashMap 基础知识：Java 开发人员的关键概念 了解基础知识。

在这篇文章中，我们将：

• 详细探索问题陈述。
• 用两种方法解决它：传统的 if-else 解决方案和getOrDefault()方法。
• 讨论两种实现的时间和空间复杂度。
• 两种解决方案的比较，包括何时使用每种解决方案。

问题陈述

您将获得一个整数列表，您的任务是返回每个唯一数字及其在列表中出现的次数。这是一个典型的问题，考验你对HashMap数据结构的理解以及高效实现它的能力。

这是一个例子：

输入：

[1, 2, 3, 5, 2, 1]

输出：

{1=2, 2=2, 3=1, 5=1}

如果输入列表为空或空，结果应返回一个空的HashMap。

解决方案 1：使用 if-else 的传统方法

在此解决方案中，我们手动检查HashMap是否已包含数字作为键。如果是，我们增加该值；如果没有，我们插入值为 1 的键。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class CountNumbers {

    private HashMap getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap map = new HashMap();

        // To avoid NullPointerException in case of a null list
        if (list != null) {
           // Iterate through each number in the list
            for (int num : list) {
                // If first occurrence, add number with count 1
                if (!map.containsKey(num)) {
                    map.put(num, 1);
                } else { // If the number already exists, increment its count by 1
                    map.put(num, map.get(num)   1);
                }
            }
        }
        return map;
    }

    public static void main(String[] args) {
        // Using ArrayList Parameterized Constructor with Collection as argument
        List numbers = new ArrayList(Arrays.asList(1, 2, 3, 5, 2, 1));

        CountNumbers nums = new CountNumbers();
        System.out.println(nums.getCount(null)); // Result -> {}
        System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
    }
}

解释

1. 如果列表为空：我们通过在迭代之前检查列表是否为空来避免 NullPointerException。
2. 迭代列表：对于每个数字，如果它已经存在于 HashMap 中，我们就递增它的值。否则，我们插入值为 1.

时间和空间复杂性

• 时间复杂度：

  • O(n) – 我们遍历列表一次，其中 n 是元素的数量。
  • 每个 HashMap 操作（put 和 get）平均需要 O(1)，使得整体时间复杂度 O(n).

• 空间复杂度：O(n) – 在最坏的情况下，所有数字都是唯一的并存储在 HashMap 中。

解决方案 2：使用 getOrDefault() 方法的优化方法

Java HashMap 类提供了更干净、更简洁的方式用 getOrDefault() 方法来处理这个问题。如果在映射中找不到键，它会通过返回 默认值 来消除对 if-else 逻辑的需要。

方法定义

V getOrDefault(Object key, V defaultValue)

• 参数：

  • key: 要返回关联值的键。
  • defaultValue：如果映射不包含键的映射则返回的值。

• 返回：指定键映射到的值，如果映射不包含该键的映射，则返回 defaultValue。

更多信息可以查看HashMap官方Javadoc。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class CountNumbers {

    private HashMap getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap map = new HashMap();

        // To avoid NullPointerException in case of a null list
        if (list != null) {
            // Iterate through each number in the list
            for (int num : list) {
                // Cleaner solution using getOrDefault()
                map.put(num, map.getOrDefault(num, 0)   1);
            }
        }
        return map;
    }

    public static void main(String[] args) {
        // Using ArrayList Parameterized Constructor with Collection as argument
        List numbers = new ArrayList(Arrays.asList(1, 2, 3, 5, 2, 1));

        CountNumbers nums = new CountNumbers();
        System.out.println(nums.getCount(null)); // Result -> {}
        System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
    }
}

解释

1. 使用 getOrDefault()：此方法返回键的值（如果存在）。如果不是，则返回提供的默认值（在本例中为0）。
2. 插入和自增：代码直接在默认值上加1，省去了if-else逻辑。

getOrDefault() 的优点

• 更简洁的代码：通过消除 if-else 的需要来减少样板文件。
• 相同的复杂度：O(n)时间和空间。

两种方法的比较

结论

使用 getOrDefault() 使代码更加简洁和可读。这个问题是面试中常见的问题，因为它评估您对 HashMap、迭代和处理空值 的理解。它还与涉及频率计数和数据聚合的问题密切相关。

• Java 基础知识

• Array面试要点

• Java 内存基础知识