Counting the number of occurrences of each item in a list

Question

I have a streaming input which has repeated values. I can use any data structure but I have to count the number of occurence of each element. Suppose I have a list of mobile phone suppliers like the following:

Apple
Nokia
Samsung
Apple
LG
Nokia
HTC
Android
Apple
Nokia
Nokia
Apple
Samsung

I have to build any data structure preferably a map with details like

Apple,4
Nokia,4
Samsung,2
LG,1
Android,1

I am not sure whether this is optimal. Is there a better solution than this?
In fact I have yet to write the above as a code. So better code will also help.

Answer 1

Where is the data comming from? If a db - you can do this very easily in the query on the backend with group by.

Answer 2

Yes, I would use a Map<String, Integer>. I would wrap the add in something like this:

private static void incrementValue(Map<String, Integer> counters, String toAdd) {
    Integer currValue = counters.get(toAdd);
    if (currValue == null)
        counters.put(toAdd, 1);
    else
        counters.put(toAdd, currValue+1);
}

Or without generics:

private static void incrementValue(Map counters, String toAdd) {
    Integer currValue = (Integer) counters.get(toAdd);
    if (currValue == null)
        counters.put(toAdd, 1);
    else
        counters.put(toAdd, currValue+1);
}

Answer 3

A map seems the way to go. Direct access :)

Key: Element value: number of ocurrences, or a list with indexes of the element in the list.

Answer 4

Besides the solutions that have been posted the first thing that comes to my mind is to make a table "code - value" and encode the list using codes. It would be very space efficient.

Answer 5

The most natural structure for this is a Bag aka a Multiset.

A bag is essentially a function from Object to Count.

Google collections has a Multiset however you could easily build your own using a HashMap.

http://google-collections.googlecode.com/svn/trunk/javadoc/index.html?com/google/common/collect/Multiset.html

Answer 6

Since it was mentioned by the questioner that generics could not be used, as the target platform was Java 1.4, one could use the Apache Commons Collections which doesn't use generics.

The answer by pjp mentions that a Bag can be used.

It turns out, the Apache Commons Collections has a Bag which has a getCount method which will return the count of a certain object that was added to the Bag.

The following is an example that adds some Integer objects to a HashBag, and counts how many of each Integer object that the Bag contains:

Bag b = new HashBag();

b.add(Integer.valueOf(1));
b.add(Integer.valueOf(2));
b.add(Integer.valueOf(2));
b.add(Integer.valueOf(3));

System.out.println("Count for 1: " + b.getCount(Integer.valueOf(1)));
System.out.println("Count for 2: " + b.getCount(Integer.valueOf(2)));
System.out.println("Count for 3: " + b.getCount(Integer.valueOf(3)));

The results were:

Count for 1: 1
Count for 2: 2
Count for 3: 1

(I should add a disclaimer that this code was actually compiled and run on Java 6, but I believe I've only used features which were present from the pre-Java 5 days.)