Does Java have a multiset data structure like the one in C++ STL?

Using Map<E, Integer> where Integer is the count is a good replacement for Multiset, and it does not need any third party library as well.

Update: If you really want to store the object twice, use a List with a Map like Map<E, List<E>>.