允许重复的TreeSet或TreeMap

Question

我需要一个可以对元素进行排序但不会删除重复项的Collection。

我选择了TreeSet，因为TreeSet实际上是将值添加到支持的TreeMap中：

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

TreeMap将使用Comparators的compare逻辑来删除重复项。

我编写了一个Comparator，在元素相等的情况下返回1而不是0。因此，在具有此Comparator的TreeSet中，对于相等的元素，它将不会覆盖重复项，而只是对其进行排序。

我已经为简单的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);
        }
    }
}

这种方法可行吗？还有更好的方法可以实现吗？

编辑

实际上，我有一个包含以下类的ArrayList：

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

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

我需要所有最高fundValue的fundCode。

- Zeeshan

---

在编程中，为您保留每个元素出现次数的计数是否足够？换句话说，在您的实际代码中，重复项是否完全等价，或者您需要保留一些差异？一个例子是大小写不敏感但保留大小写的集合或映射。 - Jon Skeet

这不会是一个Set。你需要一个已排序的列表或类似物品。从javadoc来看：Set是一种不能包含重复元素的集合。 违反这个契约并不是一个好主意。 - NeplatnyUdaj

如果您可以使用第三方库，那么Guava库可能会很有帮助。请参阅http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/TreeMultiset.html（有关集合的更多信息：https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained） - Arek Woźniak

可能是Java中的排序集合的重复问题。 - Markus Malkusch

@NeplatnyUdaj 好的，我删除了我的评论。我受到OP对排序数据结构（即在插入操作时排序的列表）想法的过多影响。外部排序列表当然是有效的。 - Markus Malkusch

Answer 1

您可以使用优先队列。

PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(); 

PriorityQueue()：创建一个使用默认初始容量（11）的PriorityQueue，按其元素的自然顺序排序。

这是文档的链接：https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html

- Sohit Gore

---

这些提示应该在TreeSet的官方文档中提供。经过几分钟的谷歌搜索，我终于找到了这个SO页面。我知道Set不允许重复，但是插入期间的自然顺序功能使我使用了TreeSet。 - sancho21

Answer 2

你可以使用Collections.sort对List进行排序。

假设你有一个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

- Max Fichtelmann

Answer 3

我需要所有基金价值最高的fundCode。

如果排序仅仅出于这个原因，我建议不排序。排序通常有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);

    }
}

您可以使用第三方库（例如Guava）来避免编写那段代码。请参见：如何在 Guava 中从 List 中获取最大元素

- Markus Malkusch

Answer 4

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

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());
        }
    }
}

- Gaya3

Answer 5

将元素添加到ArrayList中，然后使用Collections.sort实用程序对元素进行排序，然后实现Comparable接口并根据您的键编写自己的compareTo方法。

也可以对其进行排序，但不会删除重复项：

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

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

  @Override


  public int compare(Objectleft, Object right) {


**your logic**

     return '';

  }

}

)
;

- Amrut Malaji

Answer 6

在TreeSet的情况下，使用Comparator或Comparable来比较和存储对象。不会调用Equals方法，这就是为什么它无法识别重复项的原因。

- Anindya Mukherjee

Answer 7

虽然直接不可能，但有几种变通方法。

---

在任何情况下都不应该做的事情

这可能不太明显，但是擅自修改Comparator参数或者compareTo(T other)方法是不可接受的，而且集成开发环境通常会显示出问题。这种做法的问题在于，任何破坏了比较算法的行为都会导致TreeSet以意想不到的方式出错。例如，像这样实例化它：

new TreeSet<Integer>((x, y) -> y - x == 0 ? 1 : y - x);

肯定会允许您在这样的TreeSet中存储重复的Integer元素。然而，它将TreeSet分成两半，因为现在存储的每个元素都是绝对不可移除的。remove方法将不起任何作用，因为TreeSet无法找到与传入remove方法的元素相等的任何元素（请记住，TreeSet只通过调用Comparator或compareTo方法来比较元素，从不使用equals方法）。

---

更糟糕的解决方法

不要直接传递类型为T的元素，而是可以创建一个包含T和一些标识符（例如UUID）的封装类。

record TreeSetEntry<T>(T value, UUID uuid) {
    TreeSetEntry(T value) {
        this(value, UUID.randomUUID());
    }
}

将此作为类型传递给TreeSet（当然要有适当的比较器）将创建一个可以接受TreeSetEntry作为具有相等值的元素的集合。

new TreeSet<>(Comparator.comparingInt(TreeSetEntry<Integer>::value).thenComparing(TreeSetEntry::uuid));

通过这种方式克服TreeSet的局限性，在自身上是正确的，但代价是因为每个值都会创建两个额外的对象而带来的巨大内存开销。

---

更好的方法

实际上，如果您需要将重复项存储在TreeSet中作为单独的元素，您唯一可以存储的有价值信息是元素是什么以及它在TreeSet中出现的次数。我发现用TreeMap<T, Long>替换TreeSet<T>是最佳方法。当然，需要管理TreeMap中值的存在和不存在作为键，但可以通过继承或委托来自动化此过程，然后引入添加或删除值单位的方法。

下面是继承的示例。这种方法保留了TreeMap的所有功能。

class TreeCounter<T> extends TreeMap<T, Long> {
    TreeCounter(Comparator<T> comparator) {
        super(comparator);
    }

    void increase(T item) {
        increase(item, 1);
    }

    void increase(T item, int difference) {
        var count = this.getOrDefault(item, 0L);
        this.put(item, count + difference);
    }

    void decrease(T item) {
        decrease(item, 1);
    }

    void decrease(T item, int difference) {
        var currentCount = this.getOrDefault(item, 0L);
        if (currentCount <= 1) {
            this.remove(item);
            return;
        }

        this.put(item, currentCount - 1);
    }
}

意识到在Java中，特别是TreeSet和TreeMap都分配大致相等的内存量，我可以毫不夸张地说，这种解决方法在内存效率方面非常出色，尤其是在需要存储大量重复元素的情况下。

- In Dev

Answer 8

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

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

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

为了说明这一点，假设我们有一个大型零售购买清单，我们想要获取成本在特定范围内的所有购买清单。

// 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);

这个列表中创建了3个类：

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

最初我使用 TreeSet 实现时，它可以正常运行，但是在价格相同时就不行了。关键是定义 compareTo() 方法时要进行多态处理：

1. 如果我们比较 Purchase 和 PriceKey，则仅比较价格。
2. 如果我们比较 Purchase 和 Purchase，则比较价格和名称（如果价格相同）。

例如，以下是 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());
}

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

总的来说，我需要一个对象索引来支持范围扫描，其中键是像double这样的连续值，而添加/删除是有效的。

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

- Chad Juliano