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

Question

是否有按频率排序的非重复"列表"实现？

例如：

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的Multiset。 该方法Multisets.copyHighestCountFirst按每个元素的出现次数对给定的多集进行排序。

Answer 2

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

---

一种特殊情况是，如果您只添加和删除元素，并且只是不时地想要按顺序遍历/列出所有元素，在这种情况下，我建议以下实现：

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

---

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