Multiset Implementation in Java

In this post, we will see how to implement a Multiset in Java.


 

A Multiset is a collection similar to a Set that doesn’t guarantee any particular ordering on its elements, but it can accommodate duplicate elements unlike Set. It supports duplicates by maintaining a count of number of occurrences of each element in the collection. Counting the frequency of elements is very common operation in Java. We can use MultiSet to find most frequent letter in a file or sort an limited range array efficiently.

We know that Java doesn’t provides Multiset implementation, so programmers often switch to HashMap to store the number of times each key occurs. Although, both Google Guava Library and Apache commons Collections provides Multiset implementation, wouldn’t it be great to implement our own Multiset class in Java.

 
Well writing a Multiset class is actually very simple in Java. Below is simple implementation of Multiset class in Java that uses two List – one to store the distinct elements and another to store their counts. Since List is used, the time complexity for most operations is linear in terms of number of distinct elements. A Hash Table is recommended over a List for optimal constant time operations.

 

Download   Run Code

Output:

[USA x 2, Japan x 3, India x 2, China x 2]
[USA x 2, Japan, India x 2, China]
[USA x 4, Japan x 5, India x 2, Mexico x 3]

 
Also See:

1. Guava’s Multiset

2. Implement a Multimap in Java

 
References: Multiset (Guava: Google Core Libraries for Java 23.0 API)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz