Java 允许重复的 TreeSet 或 TreeMap

A TreeSet or TreeMap that allow duplicates

提问by Zeeshan

I need a Collectionthat sorts the element, but does not removes the duplicates.

我需要Collection对元素进行排序，但不删除重复项。

I have gone for a TreeSet, since TreeSetactually adds the values to a backed TreeMap:

我已经去了 a TreeSet，因为TreeSet实际上将值添加到了 a 支持TreeMap：

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

And the TreeMap removes the duplicates using the Comparatorscomparelogic

并且 TreeMap 使用Comparatorscompare逻辑删除重复项

I have written a Comparatorthat returns 1 instead of 0 in case of equal elements. Hence in the case of equal elements the TreeSetwith this Comparatorwill not overwrite the duplicate and will just sort it.

我写了 aComparator在元素相等的情况下返回 1 而不是 0 。因此，在元素相等的情况下，TreeSetthisComparator不会覆盖重复项，只会对其进行排序。

I have tested it for simple Stringobjects, but I need a Set of Custom objects.

我已经针对简单String对象对其进行了测试，但我需要一组自定义对象。

public static void main(String[] args)
{       
        List<String> strList = Arrays.asList( new String[]{"d","b","c","z","s","b","d","a"} );      
        Set<String> strSet = new TreeSet<String>(new StringComparator());       
        strSet.addAll(strList);     
        System.out.println(strSet); 
}

class StringComparator implements Comparator<String>
{
    @Override
    public int compare(String s1, String s2)
    {
        if(s1.compareTo(s2) == 0){
            return 1;
        }
        else{
            return s1.compareTo(s2);
        }
    }
}

Is this approach fine or is there a better way to achieve this?

这种方法很好还是有更好的方法来实现这一目标？

EDIT

编辑

Actually I am having a ArrayList of the following class:

实际上，我有以下类的 ArrayList：

class Fund 
{
    String fundCode;
    BigDecimal fundValue;
    .....

    public boolean equals(Object obj) {
    // uses fundCode for equality
    }
}

I need all the fundCodewith highest fundValue

我需要所有fundCode最高的fundValue

采纳答案by Markus Malkusch

I need all the fundCode with highest fundValue

我需要所有具有最高基金价值的基金代码

If that's the only reason why you want to sort I would recommend not to sort at all. Sorting comes mostly with a complexity of O(n log(n)). Finding the maximum has only a complexity of O(n)and is implemented in a simple iteration over your list:

如果这是您想要排序的唯一原因，我建议您根本不要进行排序。排序的复杂性主要是O(n log(n))。查找最大值只有O(n)的复杂性，并通过对列表的简单迭代实现：

List<Fund> maxFunds = new ArrayList<Fund>();
int max = 0;
for (Fund fund : funds) {
    if (fund.getFundValue() > max) {
        maxFunds.clear();
        max = fund.getFundValue();

    }
    if (fund.getFundValue() == max) {
        maxFunds.add(fund);

    }
}

You can avoid that code by using a third level library like Guava. See: How to get max() element from List in Guava

您可以通过使用像Guava这样的第三级库来避免该代码。请参阅：如何从 Guava 中的 List 中获取 max() 元素

回答by Max Fichtelmann

you can sort a List using Collections.sort.

您可以使用Collections.sort.

given your Fund:

鉴于您的Fund：

List<Fund> sortMe = new ArrayList(...);
Collections.sort(sortMe, new Comparator<Fund>() {
  @Override
  public int compare(Fund left, Fund right) {
    return left.fundValue.compareTo(right.fundValue);
  }
});
// sortMe is now sorted

回答by Anindya Mukherjee

In case of TreeSet either Comparator or Comparable is used to compare and store objects . Equals are not called and that is why it does not recognize the duplicate one

在 TreeSet 的情况下，Comparator 或 Comparable 用于比较和存储对象。不调用等于，这就是为什么它不识别重复的

回答by Gaya3

Instead of the TreeSet we can use List and implement the Comparable interface.

我们可以使用 List 代替 TreeSet 并实现 Comparable 接口。

public class Fund implements Comparable<Fund> {

    String fundCode;
    int fundValue;

    public Fund(String fundCode, int fundValue) {
        super();
        this.fundCode = fundCode;
        this.fundValue = fundValue;
    }

    public String getFundCode() {
        return fundCode;
    }

    public void setFundCode(String fundCode) {
        this.fundCode = fundCode;
    }

    public int getFundValue() {
        return fundValue;
    }

    public void setFundValue(int fundValue) {
        this.fundValue = fundValue;
    }

    public int compareTo(Fund compareFund) {

        int compare = ((Fund) compareFund).getFundValue();
        return compare - this.fundValue;
    }

    public static void main(String args[]){

        List<Fund> funds = new ArrayList<Fund>();

        Fund fund1 = new Fund("a",100);
        Fund fund2 = new Fund("b",20);
        Fund fund3 = new Fund("c",70);
        Fund fund4 = new Fund("a",100);
        funds.add(fund1);
        funds.add(fund2);
        funds.add(fund3);
        funds.add(fund4);

        Collections.sort(funds);

        for(Fund fund : funds){
            System.out.println("Fund code: " + fund.getFundCode() +  "  Fund value : " + fund.getFundValue());
        }
    }
}

回答by Amrut Malaji

Add the elements to the arraylist and then sort the elements using utility Collections.sort,. then implement comparable and write your own compareTo method according to your key.

将元素添加到数组列表中，然后使用实用程序 Collections.sort 对元素进行排序。然后根据您的密钥实现可比较并编写您自己的 compareTo 方法。

wont remove duplicates as well, can be sorted also:

也不会删除重复项，也可以排序：

List<Integer> list = new ArrayList<>();

Collections.sort(list,new Comparator<Integer>() 
{

  @Override


  public int compare(Objectleft, Object right) {


**your logic**

     return '';

  }

}

)
;

回答by Sohit Gore

You can use a PriorityQueue.

您可以使用 PriorityQueue。

PriorityQueue<Integer> pQueue = 

???????????????new PriorityQueue<Integer>(); 

PriorityQueue():?Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

PriorityQueue():? 创建一个具有默认初始容量 (11) 的 PriorityQueue，它根据元素的自然顺序对其进行排序。

回答by Chad Juliano

I found a way to get TreeSetto store duplicate keys.

我找到了一种让TreeSet存储重复键的方法。

The problem originated when I wrote some code in python using SortedContainers. I have a spatial index of objects where I want to find all objects between a start/end longitude.

问题起源于我使用SortedContainers在 python 中编写一些代码。我有一个对象的空间索引，我想在其中找到开始/结束经度之间的所有对象。

The longitudes could be duplicates but I still need the ability to efficiently add/remove specific objects from the index. Unfortunately I could not find the Java equivalent of the Python SortedKeyListthat separates the sort key from the type being stored.

经度可能是重复的，但我仍然需要能够有效地从索引中添加/删除特定对象。不幸的是，我找不到将排序键与存储的类型分开的Python SortedKeyList的 Java 等效项。

To illustrate this consider that we have a large list of retail purchases and we want to get all purchases where the cost is in a specific range.

为了说明这一点，请考虑我们有大量的零售采购清单，我们希望获取成本在特定范围内的所有采购。

// We are using TreeSet as a SortedList
TreeSet _index = new TreeSet<PriceBase>()

// populate the index with the purchases. 
// Note that 2 of these have the same cost
_index.add(new Purchase("candy", 1.03));
Purchase _bananas = new Purchase("bananas", 1.45);
_index.add(new Purchase(_bananas);
_index.add(new Purchase("celery", 1.45));
_index.add(new Purchase("chicken", 4.99));

// Range scan. This iterator should return "candy", "bananas", "celery"
NavigableSet<PriceBase> _iterator = _index.subset(
    new PriceKey(0.99), new PriceKey(3.99));

// we can also remove specific items from the list and
// it finds the specific object even through the sort
// key is the same
_index.remove(_bananas);

There are 3 classes created for the list

为列表创建了 3 个类

• PriceBase: Base class that returns the sort key (the price).
• Purchase: subclass that contains transaction data.
• PriceKey: subclass used for the range search.

• PriceBase：返回排序键（价格）的基类。
• 购买：包含交易数据的子类。
• PriceKey：用于范围搜索的子类。

When I initially implemented this with TreeSet it worked except in the case where the prices are the same. The trick is to define the compareTo() so that it is polymorphic:

当我最初用 TreeSet 实现它时，它工作正常，除非价格相同。诀窍是定义 compareTo() 以便它是多态的：

1. If we are comparing Purchase to PriceKey then only compare the price.
2. If we are comparing Purchase to Purchase then compare the price and the name if the prices are the same.

1. 如果我们将购买与 PriceKey 进行比较，则只比较价格。
2. 如果我们比较购买与购买，那么如果价格相同，则比较价格和名称。

For example here are the compareTo() functions for the PriceBase and Purchase classes.

例如，这里是 PriceBase 和 Purchase 类的 compareTo() 函数。

// in PriceBase
@Override
public int compareTo(PriceBase _other) {
    return Double.compare(this.getPrice(), _other.getPrice());
}

// in Purchase
@Override
public int compareTo(PriceBase _other) {

    // compare by price
    int _compare = super.compareTo(_other);

    if(_compare != 0) {
        // prices are not equal
        return _compare;
    }

    if(_other instanceof Purchase == false) {
        throw new RuntimeException("Right compare must be a Purchase");
    }

    // compare by item name
    Purchase _otherPurchase = (Purchase)_other;
    return this.getName().compareTo(_otherChild.getName());
}

This trick allows the TreeSet to sort the purchases by price but still do a real comparison when one needs to be uniquely identified.

这个技巧允许 TreeSet 按价格对购买进行排序，但在需要唯一标识时仍会进行真正的比较。

In summary I needed an object index to support a range scan where the key is a continuous value like double and add/remove is efficient.

总之，我需要一个对象索引来支持范围扫描，其中键是一个连续的值，比如 double 并且添加/删除是有效的。

I understand there are many other ways to solve this problem but I wanted to avoid writing my own tree class. My solution seems like a hack and I am surprised that I can't find anything else. if you know of a better way then please comment.

我知道有很多其他方法可以解决这个问题，但我想避免编写自己的树类。我的解决方案似乎是一个黑客，我很惊讶我找不到其他任何东西。如果您知道更好的方法，请发表评论。