Java 按频率排列的非重复有序列表

Question

是否有按频率排序的非重复 "list" 实施？

例如：

TreeSet<String> cities = new TreeSet<String>();

cities.add("NYC");    // Ordered list is [NYC]
cities.add("Boston"); // Ordered list is [Boston, NYC] (alphabetical order)
cities.add("NYC");    // Ordered list is [NYC, Boston] because NYC was added twice
cities.add("Philly"); 
cities.add("Philly");
cities.add("Philly"); // Ordered list is now [Philly, NYC, Boston]

Answer 1

这对于基本的 JDK 来说很棘手，而对于纯 Set 是不可能的，但是如果第三方库是公平的游戏，您可以使用 Guava's Multiset. The method Multisets.copyHighestCountFirst 对给定的排序按每个元素出现的次数进行多重设置。

Answer 2

我认为没有任何标准库 class 可以有效地支持此类功能。最佳实施取决于您想要使用哪些操作的频率（添加、删除、查找最大值、删除最大值、按顺序遍历……）。

一个特殊情况是，如果您只添加和删除元素，并且只是不时想要 traverse/list 所有元素按顺序排列，在这种情况下，我建议执行以下操作：

对于添加和删除，将您的数据存储在名称映射到频率的任何 Map<String, Integer>（例如 HashMap 或 TreeMap）中，这将允许快速添加和删除。如果您需要按频率列出名称，只需将所有数据拉到 List 并使用合适的比较器排序。

但是，如果您想在每次插入后查看最大元素，那么之前的实现会非常失败。在这种情况下，我会使用一些混合结构，例如组合 map 和 heap（同时使用两者），map 用于快速名称查找，heap 用于选择具有最大频率的元素。

Java 按频率排列的非重复有序列表

Java non-duplicate ordered list by frequency

java

treeset