计数更高效的方式是什么，使用数组还是哈希表（或集合）？

Question

假设我们需要计算并打印给定字符串中每个字符的出现次数。为简单起见，该字符串仅由小写字母组成。我编写了以下两个函数，并想知道哪个在Java中更有效/更可取。 函数1：

private void countAndPrintArray1(String str){
        int[] a = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'a';
            a[index] = a[index] + 1;
        }

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int freq = a[c -'a'];
            System.out.println(c+" -> "+ freq);
        }
    }

功能2：

    private void countAndPrintArray2(String str){
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int freq = map.getOrDefault(c, 0) + 1;
            map.put(c, freq);
        }

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int freq = map.get(c);
            System.out.println(c+" -> "+ freq);
        }
    }

- sparrow

---

当你测试它们时，你看到了什么？ - Scott Hunter

两种解决方案都是可接受的。 - Kayaman

我的直觉是Function1会更好，因为数组具有良好的引用局部性，但我们不应该只凭直觉，我们应该先进行基准测试。使用JMH进行基准测试。 - Debapriya Biswas

你在 Code Review 上提问的机会更大。 - M--

Answer 1

比较这两种方法的性能，两种算法都在提供的字符串大小为n时以O(n)时间复杂度运行。此外，在两种情况下空间复杂度均为O(1)。 谈到偏好，这取决于开发人员和团队正在开发的产品。虽然HashMap方法似乎更加精简和清晰（再次强调是开发者的意见）。

- Vipul Lohani