Adding duplicates in a custom Set

Question

A step ahead in tweaking the API.

Basically, Set doesn't allow for duplicate entries.

But when I would be writing a customized Set how could it be achieved to allow adding duplicates?

Answer 1

A set by its very mathematical definition is:

A well-defined collection of distinct objects

This is also reiterated in the Java definition:

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

So in your case, you would need to use a List in order to have duplicates.

Answer 2

Set, in Java, by definition is a data structure which cannot have duplicates. So, if you want a data structure which allows duplicates, you might want to use java.util.List instead.

Answer 3

Simple, but serious answer: do not do that.

You are basically asking: how should I draw a triangle that has 4 corners? Or how do I prepare a vegetarian meal using chicken wings?!

The Java Set interface is meant to not allow duplicates. That is one of the essential cornerstones of that concept. And there is no "but".

You are suggesting to violate the contract that Set gives.

In other words: inheritance and polymorphism is more than just writing down A extends B. There are rules that one has to understand when creating subclasses; or new implementations of interfaces. For example the Liskov Substitution principle.

Assume you got:

Set<Integer> someSet = new HashSet<Integer>;
someSet.add(1); someSet.add(1);
System.out.println(someSet);

Should show one entry in the set afterwards. If you now go for

Set<Integer> someSet = new YourSpecialDuplicatesAllowingSet<Integer>;
someSet.add(1); someSet.add(1);

all of a sudden ... someSet might contain two entries.

Long story short: your idea would achieve only two things: confusing other people; and thereby creating a lot of potential for ugly bugs. Hard bugs; as those things were "contracts" are violated in such ways are often hard to find and debug!

Given your comment: doing this would be rather easy:

public class FakedSet<T> implements Set<T> {
  private final List<T> elements = new ArrayList<>();
  @Override
  public void add(T elem) { elements.add(T); }

and so on; you would @Override all methods that the Set interfaces has; and try to implement them somehow. Don't ask how to do that in a reasonable manner; because well; that is not possible!

Answer 4

As others have correctly stated, there doesn't exist a set that contains duplicates, neither in Java nor in mathematics.

But you might want to have a map that counts how many duplicates you have:

Map<Whatever, Long> multiset = new HashMap<>();

To add an element, use the merge method:

multiset.merge(someElement, 1, (oldValue, value) -> oldValue + 1);

And to remove an element, you might want to use the computeIfPresent method:

multiset.computeIfPresent(someElement, (key, value) -> (value == 1 ? null : value - 1));