Hack: Duplicates in java.util.TreeSet?

Question

I have a simple class

public class A { int val; public A(int val) {this.val = val;} } 

I store instances of A in java.util.TreeSet as:

 SortedSet<A> ss = new TreeSet<A>(new Comparator<A>() { @Override public int compare(A o1, A o2) { return Integer.compare(o1.val, o2.val); } }); 

Only to find later that instances of A with the same val values ​​cannot coexist in the TreeSet .

I need a TreeSet because I want:

• Quick insert
• Quick delete
• Quick item request with minimal val

Since equality is completely dependent on the return value 0 from compare() and how we implement it, is there a hack way that allows instances with the same val value to coexist in the TreeSet ?

My workaround is to return a stable non-zero value if val are equal, but it turns out to be unstable.

 SortedSet<ListNode> ss = new TreeSet<ListNode>(new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { if (o1.val != o2.val) return Integer.compare(o1.val, o2.val); return o1.hashCode() - o2.hashCode(); // not to return 0 } }); 

Or do I just need to switch to a different data structure? (if there is some kind of replacement better than the RB tree)

And, Oh Geez, I know, modeling a mathematical set of abstractions is cool, and everyone here loves it.

Conclusion : Use the priority queue .

Answer 1

What I wanted to say ... why not use Queue and especially PriorityQueue , which is mentioned in the documentation:

Implementation note: this implementation provides O (log (n)) time for the enqueuing and dequeuing methods: offer, poll, delete, and add; linear time to delete (Object) and contains (Object) methods; and constant time for search, view, and size methods.

The difference in PriorityQueue vs Tree also that the first one is lighter because it uses a binary heap as opposed to a red-black tree ; therefore, PriorityQueue will use an array to store data that is not so difficult to understand.

Also note that if you often fill out your PriorityQueue with high priority tasks, your low priority tasks can wait a long time before they are processed.

Answer 2

I assume that you want different instances of A to coexist in your set, even if they have the same val and do not add the same instance of A more than once.

 A a = new A(1); A b = new A(1); A c = new A(2); A d = c; ss.add(a); ss.add(b); ss.add(c); ss.add(d); 

After that, you want ss contain three instances: two values ​​1 and one value (because a and b are different instances, c and d contain the same thing). This will do your code (unless you override the hashCode () method from Object).

Only one improvement: o1.hashCode() - o2.hashCode() can cause arithmetic overflow, it is better to use Integer.compare() for this part. For instance. 2,000,000,000 - (-200,000,000,000) will give a negative result, although the first number is greater. And this will lead to the fact that all structures based on Comparator will behave strangely.