唯一包含密钥但在不同字段上排序的java集
我正在寻找一个Java集合,可能在标准库中,它能够收集以下结构:
class Item {
String key;
double score;
}
并具有以下特性:
- 只允许一个具有相同密钥的项目(如一套)
- 插入、移除、检查max O(logn)中的存在
- 按分数排序的遍历,在max O(logn)中查找下一个
据我所知,标准OrderedSet必须具有与equals()接口一致的可比接口,但这不是我的情况,因为具有不同键的两个项可能具有相同的分数
事实上,我注意到TreeSet使用返回0的比较器来检查项目是否已经存在
有什么建议吗
# 1 楼答案
哈希集不保证其元素的任何顺序。如果需要此保证,请考虑使用树集来保存元素。 但是为了通过键实现唯一性并保持恒定时间覆盖
hashCode()
和equals()
有效地满足您的以下要求:输出:
# 2 楼答案
我认为不存在这样的结构。您没有指定遍历性能要求,因此可以使用一个普通集,将值添加到列表中,并按遍历分数对该列表进行排序
# 3 楼答案
您的
Item
类应该只使用key
属性实现hashCode()和equals()TreeSet
add()和remove()是O(ln N),因此它们不符合您的条件添加()和删除()通常是O(1)
你在这里的表现要求是什么?您将多久浏览一次该系列?如果主要是添加和删除项目,而很少遍历它,那么可以在遍历操作期间将
HashSet
复制到TreeSet
# 4 楼答案
现在insert已被放宽为O(logn),您可以使用一个双集合来实现这一点,即实现您自己的集合,在幕后维护两个集合
最好是修改类
Item
来实现equals()
,而hashCode()
只使用key
字段。在这种情况下,您的类将使用HashSet
和TreeSet
。如果hashCode()
覆盖的不仅仅是key
字段,那么使用两个TreeSet
对象# 5 楼答案
感谢那些用他们的评论和回答让我思考的人。我相信我们可以通过以下方式达到要求:
只是因为(我没有说过)两个相等的键产生相同的分数;但更一般地说,有两个集合映射就足够了:一个(有序)以排序字段作为键,另一个(不有序)以唯一字段作为键