在Java中按值映射自动排序
我需要在Java中有一个自动按值排序的映射 – 以便在我添加新的键值对或更新现有键值对的值时随时对其进行排序，甚至删除一些条目。
还请记住，这张地图将会非常大（数百万，甚至是数百万条目的大小）。
所以基本上我正在寻找以下function：
假设我们有一个实现上述function的“SortedByValuesMap”类，我们有以下代码：
SortedByValuesMap sorted_map = new SortedByValuesMap(); 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）。 所以我需要建立一个地图，其中键是单词，值是这些单词的频率。 但是，由于限制（如RAM），我想只保留X最常用的单词 – 但事先你不能知道哪些是最常用的单词。 因此，我认为它可能起作用的方式（作为近似）是开始计算单词，当地图达到上限（如1 mil条目）时，将删除最不频繁的条目，以便将地图的大小保持为总是1密耳。
保留2个数据结构：
- 单词词典 – >计数。 只需使用普通的
HashMap。 -
用于跟踪顺序的“数组”，以便
list[count]保存具有该计数的单词Set。我写这个就好像它是一个数组作为符号方便。 实际上，您可能不知道出现次数的上限，因此您需要一个可resize的数据结构。 使用
Map。 或者，如果使用太多内存，请使用ArrayList（您必须测试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);
如果Long值是不同的TreeMap那么如何使用其他索引或仅使用TreeMap或TreeMap ？
你也可以写一个堆 。
番石榴BiMap解决方案：
//Prepare original data BiMap biMap = HashBiMap.create(); biMap.put("apples" , 4); biMap.put("oranges", 2); biMap.put("bananas", 1); biMap.put("lemons" , 3); biMap.put("bananas", 6); //Create a desc order SortedMap SortedMap sortedMap = new TreeMap(new Comparator(){ @Override public int compare(Integer o1, Integer o2) { return o2-o1; }}); //Put inversed map sortedMap.putAll(biMap.inverse()); for (Map.Entry e: sortedMap.entrySet()) { System.out.println(e); } System.out.println(sortedMap.lastKey());
尝试http://paaloliver.wordpress.com/2006/01/24/sorting-maps-in-java/上发布的解决方案。 您可以灵活地进行升序或降序排序。
这就是他们所说的
import java.util.Comparator; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.SortedMap; import java.util.TreeMap; public class MapValueSort { /** inner class to do soring of the map **/ private static class ValueComparer implements Comparator { private Map _data = null; public ValueComparer (Map data){ super(); _data = data; } public int compare(String o1, String o2) { String e1 = (String) _data.get(o1); String e2 = (String) _data.get(o2); return e1.compareTo(e2); } } public static void main(String[] args){ Map unsortedData = new HashMap(); unsortedData.put("2", "DEF"); unsortedData.put("1", "ABC"); unsortedData.put("4", "ZXY"); unsortedData.put("3", "BCD"); SortedMap sortedData = new TreeMap(new MapValueSort.ValueComparer(unsortedData)); printMap(unsortedData); sortedData.putAll(unsortedData); System.out.println(); printMap(sortedData); } private static void printMap(Map data) { for (Iterator iter = data.keySet().iterator(); iter.hasNext();) { String key = (String) iter.next(); System.out.println("Value/key:"+data.get(key)+"/"+key); } } }
输出
Value/key:BCD/3 Value/key:DEF/2 Value/key:ABC/1 Value/key:ZXY/4 Value/key:ABC/1 Value/key:BCD/3 Value/key:DEF/2 Value/key:ZXY/4
更新：您不能按值对地图进行排序，抱歉。
您可以使用像 TreeMap这样的SortedMap实现，使用Comparator按值定义顺序（而不是默认值 – 按键）。
或者，更好的是，您可以使用预定义的比较器值将元素放入PriorityQueue中 。 与TreeMap相比，它应该更快，占用更少的内存。
您可以参考java.util.LinkedHashMap的实现。 基本思想是，使用内部链表来存储订单。 这是一些细节：
从HashMap扩展。 在HashMap中，每个条目都有一个键和值，这是基本的。 您可以按值按顺序添加next和prev指针来存储条目。 以及用于获取第一个和最后一个条目的标头和尾部指针。 对于每个修改（添加，删除，更新），您可以添加自己的代码来更改列表顺序。 它只不过是一个线性搜索和指针切换。
当然，如果条目太多，添加/更新会很慢，因为它是一个链表不是数组。 但只要列表排序，我相信有很多方法可以加快搜索速度。
所以这就是你得到的：在通过密钥检索条目时与HashMap具有相同速度的地图。 一个链接列表，按顺序存储条目。
如果此解决方案符合您的要求，我们可以进一步讨论。
对于jtahlborn：正如我所说，没有任何优化肯定会很慢。 既然我们现在谈论的是绩效而不是现在，那么可以做很多事情。
一种解决方案是使用树而不是链接列表，如红黑树。 然后迭代树而不是迭代地图。
关于最小的值，它更容易。 只需使用成员变量来存储最小值，在添加或更新元素时，更新最小值。 删除时，在树中搜索最小的（这非常快）
如果树太复杂，也可以使用另一个列表/数组来标记列表中的某些位置。 例如，每个可能有100个元素。 然后在搜索时，首先搜索位置列表，然后搜索真实列表。 此列表也需要维护，在某些修改时间重新计算位置列表是合理的，可能是100。
我发现需要一个类似的结构来保存按关联值排序的对象列表。 基于此线程中Mechanical snail的建议，我编写了这样一个地图的基本实现。 随意使用。
import java.util.*; /** * A map where {@link #keySet()} and {@link #entrySet()} return sets ordered * with ascending associated values with respect to the the comparator provided * at constuction. The order of two or more keys with identical values is not * defined. * * Several contracts of the Map interface are not satisfied by this minimal * implementation. */ public class ValueSortedMap extends HashMap { protected Map> valueToKeysMap; public ValueSortedMap() { this((Comparator) null); } public ValueSortedMap(Comparator valueComparator) { this.valueToKeysMap = new TreeMap>(valueComparator); } public boolean containsValue(Object o) { return valueToKeysMap.containsKey(o); } public V put(K k, V v) { V oldV = null; if (containsKey(k)) { oldV = get(k); valueToKeysMap.get(oldV).remove(k); } super.put(k, v); if (!valueToKeysMap.containsKey(v)) { Collection keys = new ArrayList (); keys.add(k); valueToKeysMap.put(v, keys); } else { valueToKeysMap.get(v).add(k); } return oldV; } public void putAll(Map m) { for (Map.Entry e : m.entrySet()) put(e.getKey(), e.getValue()); } public V remove(Object k) { V oldV = null; if (containsKey(k)) { oldV = get(k); super.remove(k); valueToKeysMap.get(oldV).remove(k); } return oldV; } public void clear() { super.clear(); valueToKeysMap.clear(); } public Set keySet() { LinkedHashSet ret = new LinkedHashSet (size()); for (V v : valueToKeysMap.keySet()) { Collection keys = valueToKeysMap.get(v); ret.addAll(keys); } return ret; } public Set> entrySet() { LinkedHashSet> ret = new LinkedHashSet>(size()); for (Collection keys : valueToKeysMap.values()) { for (final K k : keys) { final V v = get(k); ret.add(new Map.Entry() { public K getKey() { return k; } public V getValue() { return v; } public V setValue(V v) { throw new UnsupportedOperationException(); } }); } } return ret; } }
此实现不遵守Map接口的所有合同，例如反映实际映射中返回的键集和条目集中的值更改和删除，但是这样的解决方案有点大，可以包含在这样的论坛中。 也许我会在一个上工作，并通过github或类似的东西提供它。
如果您只需要“min”值，那么只需使用法线贴图并随时跟踪“min”值即可。
编辑：
所以，如果你真的需要价值订购，并且想要使用开箱即用的解决方案，那么你基本上需要2个系列。 一个法线贴图（例如HashMap）和一个SortedSet（例如TreeSet>）。 您可以通过TreeSet遍历有序元素，并使用HashMap按键查找频率。
显然，你总是可以编写类似于LinkedHashMap的东西，其中元素可以通过键定位并且可以按顺序遍历，但这几乎完全是自定义代码（我怀疑任何特定的已经存在，但我可能是错误）。