时间戳

首页 > 解决方案 > java - 如何使用java TreeSet实现排序表（按元素的字段排序）？

java - java - 如何使用java TreeSet实现排序表（按元素的字段排序）？

问题描述

我为此使用了 TreeSet，它以每个快照样式工作。换句话说，排序一次显示一次。

现在，我想实现一个实时排序表。

每当任何元素的值发生变化时，排序表都会相应地更新。

为了使按更新样式进行排序，我尝试删除该元素并将其再次添加到 TreeSet。

quotes.remove(quote);
quotes.add(quote);

它不起作用，因为我必须在 compareTo() 中实现排序逻辑，但它违反了识别使 remove() 工作的对象的合同。TreeSet 永远不会像 Java Doc 中描述的那样调用 equals() 和 hashcode()。

任何想法？请指教。

代码：

import java.util.TreeSet;

public class TreeSetTest {

    public static void main(String args[]) {        
        TreeSetTest test = new TreeSetTest();
        test.onQuoteUpdate("appl", 1000d);
        test.onQuoteUpdate("msft", 2000d);
        test.onQuoteUpdate("face", 3000d);
        test.printTopStocks();
        test.onQuoteUpdate("msft", 5000d);
        test.printTopStocks();
    }

    private Set<Quote> quotes = new TreeSet<Quote>();

    public void onQuoteUpdate(String symbol, double turnover) {
        final Quote quote = new Quote(symbol, turnover);
        quotes.remove(quote);
        quotes.add(quote);
    }

    public void printTopStocks() {
        System.out.println("--Top Stocks By Turnover--");
        for (final Quote quote : quotes) {
            System.out.println(quote);
        }
    }
    public static class Quote implements Comparable<Quote> {

        private String symbol;

        private double turnover;

        public Quote(String symbol, double turnover) {
            this.symbol = symbol;
            this.turnover = turnover;
        }

        @Override
        public int compareTo(Quote o) {
            return Double.compare(o.turnover, turnover);
//          return symbol.compareTo(o.symbol);
        }

    }
}

更新1：

正如提议的那样，我尝试了这个：

public static void main(String args[]) {        
    TreeMapTest test = new TreeMapTest();
    test.onQuoteUpdate("appl", 1000d);
    test.onQuoteUpdate("msft", 2000d);
    test.onQuoteUpdate("face", 3000d);
    test.printTopStocks();
    test.onQuoteUpdate("face", 50d);
    test.printTopStocks();
}

    public int compareTo(Quote o) {
        if(o.symbol.equals(symbol)) return 0;
        return Double.compare(o.turnover, turnover);
    }

remove() 返回 false，最终在 Set 中有四个元素（预期为 3）。

--Top Stocks By Turnover--
Quote [symbol=face, turnover=3000.0]
Quote [symbol=msft, turnover=2000.0]
Quote [symbol=appl, turnover=1000.0]
remove symbol face : false
add    symbol face : true
--Top Stocks By Turnover--
Quote [symbol=face, turnover=3000.0]
Quote [symbol=msft, turnover=2000.0]
Quote [symbol=appl, turnover=1000.0]
Quote [symbol=face, turnover=50.0]

更新 2：

我试过 PriorityQueue ，这里是代码： https ://code.sololearn.com/cb38Eo036c8y/#java

它不起作用，因为 PriorityQueue 没有按顺序存储元素。仅当您从队列中轮询元素时，排序才有效。

更新 3：

通过使用自定义集合尝试了 user54321 的建议（请参见下面的答案）。但是，如果还有两个元素具有相同的“营业额”值，则看起来不太好。

我的要求很普通。似乎 JDK 的集合都不适合我的情况。

更新 4：

user54321 的解决方案适合我的临时需求。 https://code.sololearn.com/c14Ybab7AOFm/#java

标签： javasortingtreeset

解决方案

删除了我之前添加的答案。看起来该场景使用了错误的数据结构。

这就是为什么。

当添加或删除项目时，TreeSet 使用compareTo().

在你的情况下，

添加前 3 个元素后，set 看起来像这样。
[{appl, 1000d}, {msft, 2000d}, {face, 3000d}]

现在，当您尝试删除元素{face, 50d}时，

它开始搜索{msft, 2000d}，从compareTo()它确定的结果{face, 50d}应该在之前{msft, 2000d}。

并继续搜索元素的开始（检查{appl, 1000d}下一个）。

由于搜索未找到{face, 3000d}，因此该元素将保留而不会被删除。

接下来，当您添加元素时{face,50}，会发生类似的搜索，并且由于搜索未找到{face, 3000}，它会添加{face, 50}到开头。

现在套装看起来像这样。
[{face, 50}, {appl, 1000d}, {msft, 2000d}, {face, 3000d}]

现在这里的问题是它compareTo()不能同时考虑符号和营业额来进行合理的排序。 TreeSet可用于获取唯一元素的排序集合。

如果您需要获取具有特定排序标准的不同对象的排序集合，在这种情况下是营业额值，您可以使用PriorityQueue

更新：在自定义数据结构中使用列表和集合

这里的问题是我们必须保持两个条件。1. 符号必须是唯一的 2. 集合应该按营业额排序

compareTo()in Quote 可以一次检查一项，不能同时检查一项。因此，在这种情况下，我们可能不得不使用自定义数据结构。

首次使用仅turnover在compareTo();

    @Override
    public int compareTo(Quote o) {
        return Double.compare(o.turnover, turnover);
    }

然后实现自定义数据结构。请注意，我们使用 HashSet 来单独跟踪符号。使用列表以便保留重复的营业额值。

static class QuoteCollection {
    Set<String> symbols = new HashSet<>();
    List<Quote> quotes = new LinkedList<>();

    public void onQuoteUpdate(Quote q) {

        if (symbols.contains(q.getSymbol())) {
            // this requires quotes.equals() to be implemented
            quotes.remove(q);
        } else {
            symbols.add(q.getSymbol());
        }
        insertToCollection(q);
    }

    // inserting at correct position to remain sorted
    private void insertToCollection(Quote q) {
        int index = Collections.binarySearch(quotes, q);
        if (index < 0)
            index = ~index; // bitwise compliment to find insert position if it is not available in the list
        quotes.add(index, q);
    }

    public List<Quote> getQuotes() {
        return quotes;
    }
}

然后在 main() 中使用它。请注意， printTopStocks() 已稍作更改。

public static void main(String args[]) {
    Main test = new Main();
    QuoteCollection quoteCollection = new QuoteCollection();
    quoteCollection.onQuoteUpdate(new Quote("appl", 1000d));
    quoteCollection.onQuoteUpdate(new Quote("msft", 2000d));
    quoteCollection.onQuoteUpdate(new Quote("face", 3000d));
    test.printTopStocks(quoteCollection.getQuotes());
    quoteCollection.onQuoteUpdate(new Quote("face", 50d));
    test.printTopStocks(quoteCollection.getQuotes());
}
public void printTopStocks(List<Quote> quotes) {
    System.out.println("--Top Stocks By Turnover--");
    for (final Quote quote : quotes) {
        System.out.println(quote);
    }
}

这种方法确实涉及数据复制。但是，可以以线性时间复杂度维护已排序的集合（因为它使用 'List.remove()'）

推荐阅读