在Java中按值映射自动排序 [英] Automatically sorted by values map in Java

问题描述

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

请记住，这张地图会是真的很大（几十万，甚至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 
  pre> 
 
 
特别是，对我来说真正重要的是能够随时使用
最小值获取条目 - 使用命令： 
  smallestItem = sorted_map.lastEntry（）; 
  
这应该给我'oranges'条目
 
 
 
编辑：我是一个Java新手，所以请详细阐述你的答案 - 感谢
 
 
 
 EDIT2：这可能有帮助：熟悉的人：特别是n-gram）在巨大的文本文件中。所以我需要建立一个地图，其中键是字，值是这些词的频率。然而，由于限制（如RAM），我想只保留X个最常用的词 - 但你不能预先知道哪些是最常见的词当然。所以，我认为它可能工作（作为一个近似）的方式是开始计数字，当地图达到顶限（如1 mil条目），最少频繁的条目将被删除，以保持地图的大小1 mil always。
解决方案
保留2个数据结构：
 
 
 
 
 
一个词典 - > count。只需使用一个普通的 HashMap< String，Long> 。
 
 
 
  list [count] 持有设置 的单词。
 
 
 
我写这个就像一个数组作为一个符号的方便。事实上，你可能不知道出现次数的上限，所以你需要一个可调整大小的数据结构。使用 Map< Long，Set< String>> 实现。或者，如果使用太多内存，使用 ArrayList< Set< String>> （你必须测试 count == size （） -  1 ，如果是，使用 add（），而不是 set（count + 1） 
 
 
 
 
 
要增加单词（伪代码）的出现次数：
  //假设数据结构是在实例变量dict和arr 
 public void tally（final String word）
 {
 final long count = this.dict.get（word）或0如果不存在; 
 this.dict.put（word，count + 1）; 
 //将单词移动到arr 
 this.arr [count] .remove（word）; //这就是为什么我们使用Set：在这里快速删除。 
 this.arr [count + 1] .add（word）; 
} 
  
按顺序对字词进行重复（伪代码）：
  for（int count = 0; count< arr.size; count ++）
 for（final String word：this.arr [count] ）
 process（word，count）; 
  
 
I need to have an automatically sorted-by-values map in Java - so that It keeps being sorted at any time while I'm adding new key-value pairs or update the value of an existing key-value pair, or even delete some entry.  

Please also have in mind that this map is going to be really big (100's of thousands, or even 10's of millions of entries in size).

So basically I'm looking for the following functionality:

Supposed that we had a class 'SortedByValuesMap' that implements the aforementioned functionality
and we have the following code:
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));
}
the output should be:
bananas:6
apples:4
lemons:3
oranges:2
In particular, what's really important for me, is to be able to get the entry with the 
lowest value at any time - using a command like:
smallestItem = sorted_map.lastEntry();
which should give me the 'oranges' entry

EDIT: I am a Java newbie so please elaborate a bit in your answers - thanks

EDIT2: This might help: I am using this for counting words (for those who are familiar: n-grams in particular) in huge text files. So I need to build a map where keys are words and values are the frequencies of those words. However, due to limitations (like RAM), I want to keep only the X most frequent words - but you can't know beforehand which are going to be the most frequent words of course. So, the way I thought it might work (as an approximation) is to start counting words and when the map reaches a top-limit (like 1 mil entries) , the least frequent entry will be deleted so as to keep the map's size to 1 mil always.
解决方案
Keep 2 data structures:


A dictionary of words -> count. Just use an ordinary HashMap<String, Long>.
An "array" to keep track of order, such that list[count] holds a Set<String> of words with that count.

I'm writing this as though it were an array as a notational convenience. In fact, you probably don't know an upper bound on the number of occurrences, so you need a resizable data structure. Implement using a Map<Long, Set<String>>. Or, if that uses too much memory, use an ArrayList<Set<String>> (you'll have to test for count == size() - 1, and if so, use add() instead of set(count + 1)).


To increment the number of occurrences for a word (pseudocode):
// 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);
}
To iterate over words in order (pseudocode):
for(int count = 0; count < arr.size; count++)
    for(final String word : this.arr[count])
        process(word, count);


                        
这篇关于在Java中按值映射自动排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！