java - 在 Java 中按值映射自动排序

Question

我需要有一个 自动 在 Java 中按值排序的映射 - 以便在我添加新的键值对或更新现有的键值对，甚至删除一些条目。

还请记住，这张 map 将会非常大(大小为 100 的数千，甚至是 10 的数百万条目)。

所以基本上我正在寻找以下功能:

假设我们有一个实现上述功能的“SortedByValuesMap”类 我们有以下代码:

SortedByValuesMap<String,Long> sorted_map = new SortedByValuesMap<String, Long>();
sorted_map.put("apples", 4);
sorted_map.put("oranges", 2);
sorted_map.put("bananas", 1);
sorted_map.put("lemons", 3);
sorted_map.put("bananas", 6);

for (String key : sorted_map.keySet()) {
  System.out.println(key + ":" + sorted_map.get(key));
}

输出应该是:

bananas:6
apples:4
lemons:3
oranges:2

尤其是对我来说真正重要的是能够获得带有 任何时候的最低值 - 使用如下命令:

smallestItem = sorted_map.lastEntry();

这应该给我“橙子”条目

编辑:我是 Java 新手，所以请详细说明您的答案 - 谢谢

EDIT2:这可能会有所帮助:我正在使用它来计算巨大文本文件中的单词(对于那些熟悉的人:特别是 n-gram)。所以我需要建立一个 map ，其中键是单词，值是这些单词的频率。但是，由于限制(如 RAM)，我只想保留 X 最常用的词——但你不能事先知道哪些是最常用的词。因此，我认为它可能起作用的方式(作为近似值)是开始计算单词，本地图达到上限(如 1 百万个条目)时，将删除最不频繁的条目以保持 map 的大小总是 100 万。

Answer 1

保留2个数据结构:

• 单词词典 -> 计数。用普通的HashMap<String, Long> .

• 用于跟踪顺序的“数组”，例如 list[count]持有 Set<String>具有该计数的单词。

  我写这个好像它是一个数组作为符号方便。事实上，您可能不知道出现次数的上限，因此您需要一个可调整大小的数据结构。使用 Map<Long, Set<String>> 实现.或者，如果这使用太多内存，请使用 ArrayList<Set<String>> (您必须测试 count == size() - 1 ，如果是，请使用 add() 而不是 set(count + 1) )。

增加单词的出现次数(伪代码):

// assumes data structures are in instance variables dict and arr
public void tally(final String word)
{
    final long count = this.dict.get(word) or 0 if absent;
    this.dict.put(word, count + 1);
    // move word up one place in arr
    this.arr[count].remove(word);   // This is why we use a Set: for fast deletion here.
    this.arr[count + 1].add(word);
}

按顺序迭代单词(伪代码):

for(int count = 0; count < arr.size; count++)
    for(final String word : this.arr[count])
        process(word, count);