我有一个简单的类
public class A {
int val;
public A(int val) {this.val = val;}
}
我将A
实例存储在java.util.TreeSet
中,如下:
SortedSet<A> ss = new TreeSet<A>(new Comparator<A>() {
@Override
public int compare(A o1, A o2) {
return Integer.compare(o1.val, o2.val);
}
});
只有后来才发现,在TreeSet中,具有相同val值的A实例无法共存。
我需要TreeSet,因为我想要:
- 快速插入 - 快速删除 - 快速查询具有最小val元素
由于相等性完全取决于compare()的返回值0及其实现方式,是否存在一种黑客方式允许具有相同val值的实例在TreeSet中共存?
我的解决方法是,如果val相等,则返回一个稳定的非零值,但它被证明是不稳定的。
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
}
});
我应该换用其他数据结构吗?(如果存在比R-B树更好的替代品)
哦天啊,我知道建模数学集合抽象很酷,这里的每个人都喜欢它。
结论:使用优先队列。
Guava
中的Multiset
可以帮助解决问题。 - dehasijava.util.TreeMap
源代码中的final Entry<K,V> getEntry(Object key)
方法...我相信在Map
和Set
实现方面,equals
和hashCode
只对HashMap
和HashSet
至关重要。 - SedriX