How to count occurrencies of an entity in a list with repetitions?

Question

I have a list of 5-digit combinations (possibly with repetitions: doubles, triples, etc). I need to count how often every combination appears in that list. Actually, a combination is a unique BitSet with respective bits set (if combination contains digit 5 then 5th bit is set, etc.)

Given list

I shall get

12345 -> 3
34578 -> 1
98710 -> 1

Is there anything ready to solve this task? Like I add 12345 string to this data structure three times and then I query it for 12345 (respective Bitset object) and it returns 3 as number of occurrencies. I thought of Apache Commons Frequency class, but it does not help.

Convert the list into a set and then iterate over the set and count against the list — fasaas, Oct 13 '18 at 15:16
Streams can help, see https://stackoverflow.com/questions/23925315/count-int-occurrences-with-java8 — Turo, Oct 13 '18 at 15:26
A frequency count sounds like what you need. Can you explain `it does not help`? — Peter Lawrey, Oct 13 '18 at 15:27

Alex Shesterov · Answer 1 · 2018-10-13T16:05:30.843

If you are looking for a ready-to-use data structure which stores elements with counts, then Guava's Multiset does exactly that.

If you just need to convert a list to a map of counts, please read on.

You can convert a list to a map of counts in a single statement using Java 8 Streams API:

final var list = List.of("12345", "34578", "12345", "98710", "12345");

final var counts = list.stream()
    .collect(Collectors.toMap(
        Function.identity(), // Map keys are list elements
        value -> 1, // Map values are counts, a single item counts "1"
        (count1, count2) -> count1 + count2 // On duplicate keys, counts are added
    ));

Under the hood, this solution uses a hash map (elements to counts) as a data structure.

You may also use the groupingBy collector, as Peter Lawrey kindly suggested:

final var list = List.of("12345", "34578", "12345", "98710", "12345");

final var counts = list.stream()
    .collect(Collectors.groupingBy(
        Function.identity(), // Group the elements by equality relation
        Collectors.counting() // Map values are counts of elements in the equality groups
    ));

Sometimes (while learning) it's beneficial to implement everything "by hand" to understand the algorithms. So here a version without Java 8 goodies like streams, collectors and new map methods like Map.compute():

final List<Stream> list = List.of("12345", "34578", "12345", "98710", "12345"); // Use ArrayList if you're below Java 9

final Map<String, Integer> counts = new HashMap<>();
for (final String item : list) {
    // Note: I'm deliberately NOT using Map.compute() here
    // to demonstrate how to do everything "manually"
    Integer count = counts.get(item);
    if (count == null) {
        count = 0;
    }
    counts.put(item, count + 1);
}

"I'm deliberately NOT using Map.compute()" `Map.merge` would be an easier alternative than `Map.compute` anyway. — Andy Turner, Oct 13 '18 at 18:59

score 0 · Answer 2 · answered Oct 13 '18 at 15:30

Assuming your list are strings (if not you might need a "comparator"). Loop over the entire list adding the elements to a HashMap and a counter of themselves; but right before doing that, check if the element in question exists, updating the counter accordingly.

Eventually, Java streams can help too.

score 0 · Answer 3 · answered May 07 '20 at 23:26

You can use the plain Collections.frequency method that does exactly that.

import java.util.List;
import static java.util.Collections.frequency;

List list = List.of("12345", "34578", "12345", "98710", "12345");
System.out.println( frequency(list, "12345") );

How to count occurrencies of an entity in a list with repetitions?

3 Answers3