在 Java 中按值映射自动排序

data-structures collections associative-array java sorted

2022-09-01 16:15:35

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

请记住，这张地图将非常大（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新手，所以请在您的答案中详细说明一下 - 谢谢

编辑2：这可能会有所帮助：我正在用它来计算大型文本文件中的单词（对于那些熟悉的人：特别是n-grams）。因此，我需要构建一个映射，其中键是单词，值是这些单词的频率。但是，由于限制（如RAM），我只想保留X个最常用的单词 - 但你不能事先知道哪些是最常见的单词。因此，我认为它可能起作用的方式（作为近似值）是开始计算单词，当地图达到上限（如1 mil条目）时，最不频繁的条目将被删除，以便始终将地图的大小保持在1 mil。

答案 1

保留 2 个数据结构：

单词字典 ->计数。只需使用普通的.HashMap<String, Long>
一个“数组”，用于跟踪顺序，以便保存具有该计数的单词。list[count]Set<String>

我写这个，就好像它是一个数组作为符号上的便利。实际上，您可能不知道出现次数的上限，因此您需要一个可调整大小的数据结构。使用 .或者，如果这占用了太多内存，请使用（您必须测试，如果是这样，请使用代替）。Map<Long, Set<String>>ArrayList<Set<String>>count == size() - 1add()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);

答案 2

使用其他索引或仅使用多头值或多头值是否不同，怎么样？TreeMap<Long, TreeSet<String>>TreeMap<Long, String>

你也可以写一个堆。