咨询Java内置函数Collections.frequency()的算法复杂度（含ArrayList<String>场景）

Great question! Let's break this down step by step, covering both the general case and your specific scenario with ArrayList<String>.

通用情况：任意Collection的复杂度 #

First off, let's look at how Collections.frequency(Collection<?> c, Object o) works under the hood. This method iterates every single element in the input collection, calling the equals() method on each element to compare it with the target element.

Since it has to traverse the entire collection without skipping any elements, its time complexity is O(n) where n is the number of elements in the collection. This holds true for any implementation of Collection—whether it's an ArrayList, LinkedList, HashSet, etc.—because the method doesn't rely on any collection-specific optimizations like indexing or hashing.

针对ArrayList的场景 #

Now, let's zoom in on your specific case: an ArrayList containing String elements.

Here, the core traversal is still O(n) (we still have to check every element in the ArrayList), but the cost of each equals() comparison changes. The String.equals() method works by comparing characters one by one until it finds a mismatch or reaches the end of both strings. This means each comparison takes O(k) time, where k is the length of the strings being compared (or the average length across your list, for a more general estimate).

Putting it all together, the total time complexity for Collections.frequency(arrayListOfStrings, targetString) is O(n*k).

A quick edge case note: if the target element is null, the comparison becomes O(1) (since we're just checking for null references, not comparing string content), so the complexity drops back to O(n) in that scenario.

内容的提问来源于stack exchange，提问作者Munauwar Shaikh