Java中自动按值排序的Map

Question

我需要在Java中拥有一个自动按值排序的映射表，这样当我添加新的键值对或更新现有键值对的值，甚至删除某些条目时，它始终保持排序。

请注意，这个映射表将非常大（大小可能达到数十万或数百万条目）。

因此，基本上我正在寻找以下功能：

假设我们有一个实现了上述功能的'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();

应该给我“oranges”条目。

编辑：我是一个Java新手，请在你的答案中详细说明一些 - 谢谢。

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

- Alexandros

---

数百万条记录？为什么不使用数据库呢？ - Kru

@Kru：使用数据库会使其变得非常慢。 - Alexandros

如果这只是英语，你高估了有多少常用词汇，特别是那些通常使用的词汇。 - Dave Newton

@Dave Newton 你说得对 - 我提到了单词，是为了不让那些不熟悉n-gram的人感到困惑，而我实际上计算的是n-gram。随着N的增加，n-gram尤其是变得非常多样化。可能的组合呈指数级增长。 - Alexandros

@BalusC: 我认为这不是完全相同的问题-另一个问题的接受解决方案会在排序时进行全排序，而这个问题是关于始终保持TreeMap排序（从而可迭代）的。 - Timothy Jones

Answer 1

保留2个数据结构:

1. 一个单词->数量的字典，可以使用普通的HashMap 2. 一个用于跟踪顺序的"数组"，使得list[count]保存具有该计数的单词的Set。我写这篇文章是为了表示它是一个数组，以方便记号。实际上，您可能不知道出现次数的上限，因此需要一个可调整大小的数据结构。可以使用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);

- Mechanical snail

Answer 2

如何使用额外的索引或仅使用TreeMap<Long, TreeSet<String>>或TreeMap<Long, String>（如果Long值是不同的）？

您还可以编写一个堆。

- NiematojakTomasz

---

长整型数值不是唯一的。两个不同的条目可能具有相同的长整型数值 - 长整型数值实际上代表频率。 - Alexandros

所以你可以使用 TreeMap<Long, TreeSet<String>>。 - NiematojakTomasz

可能会起作用，但我担心它会使地图操作翻倍，这将导致时间加倍 - 在我的情况下，我有数百万条目，这可能会产生巨大的影响。 - Alexandros

不是很多。只是常数因子会稍微增加一些。 您还可以创建一些类似于Map.Entry<K,V>的对类，并使用TreeSet<Pair<Long, String>>。 - NiematojakTomasz

很抱歉要说反话（我也在另一个答案中发表了评论），但是 TreeMap<Long,TreeSet<String>> 的方法也意味着在执行查找之前，您需要知道将 String 映射到的 Long - 如果您知道了，那么您就不需要执行查找了... - Timothy Jones

是的，但你可以保留TreeMap<Long,TreeSet<String>>和Map<String,Long>两个数据结构。我猜在Java中没有提供一个单一的数据结构能够同时实现这两个功能。在SQL表中，你会想要在两列上建立索引，所以我猜你也需要在Java中有2个“索引”。 - NiematojakTomasz

Answer 3

我发现需要一个类似的结构来按相关值排序并保持对象列表。基于 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.
 * <p>
 * Several contracts of the Map interface are not satisfied by this minimal
 * implementation.
 */
public class ValueSortedMap<K, V> extends HashMap<K, V> {
    protected Map<V, Collection<K>> valueToKeysMap;

    public ValueSortedMap() {
        this((Comparator<? super V>) null);
    }

    public ValueSortedMap(Comparator<? super V> valueComparator) {
        this.valueToKeysMap = new TreeMap<V, Collection<K>>(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<K> keys = new ArrayList<K>();
            keys.add(k);
            valueToKeysMap.put(v, keys);
        } else {
            valueToKeysMap.get(v).add(k);
        }
        return oldV;
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> 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<K> keySet() {
        LinkedHashSet<K> ret = new LinkedHashSet<K>(size());
        for (V v : valueToKeysMap.keySet()) {
            Collection<K> keys = valueToKeysMap.get(v);
            ret.addAll(keys);
        }
        return ret;
    }

    public Set<Map.Entry<K, V>> entrySet() {
        LinkedHashSet<Map.Entry<K, V>> ret = new LinkedHashSet<Map.Entry<K, V>>(size());
        for (Collection<K> keys : valueToKeysMap.values()) {
            for (final K k : keys) {
                final V v = get(k);
                ret.add(new Map.Entry<K,V>() {
                    public K getKey() {
                        return k;
                    }

                    public V getValue() {
                        return v;
                    }

                    public V setValue(V v) {
                        throw new UnsupportedOperationException();
                    }
                });
            }
        }
        return ret;
    }
}

这个实现并不遵守 Map 接口的所有契约，比如在返回的键集和条目集中反映值更改和删除在实际映射中的情况，但是这样的解决方案会比较庞大，无法包含在像这样的论坛中。也许我会开发一个并通过 Github 或类似的方式提供。

- David Bleckmann

Answer 4

Guava BiMap 解决方案：

//Prepare original data
BiMap<String, Integer> 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<Integer, String> sortedMap = new TreeMap<Integer, String>(new Comparator<Integer>(){
    @Override public int compare(Integer o1, Integer o2) {
      return o2-o1;
}});

//Put inversed map
sortedMap.putAll(biMap.inverse());
for (Map.Entry<Integer, String> e: sortedMap.entrySet()) {
      System.out.println(e);
}
System.out.println(sortedMap.lastKey()); 

- 卢声远 Shengyuan Lu

---

OP已经说过这些值不是唯一的，因此BiMap无法使用。 - jtahlborn

Answer 5

尝试使用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<String> {
        private Map<String, String>  _data = null;
        public ValueComparer (Map<String, String> 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<String, String> unsortedData = new HashMap<String, String>();
        unsortedData.put("2", "DEF");
        unsortedData.put("1", "ABC");
        unsortedData.put("4", "ZXY");
        unsortedData.put("3", "BCD");


        SortedMap<String, String> sortedData = new TreeMap<String, String>(new MapValueSort.ValueComparer(unsortedData));

        printMap(unsortedData);

        sortedData.putAll(unsortedData);
        System.out.println();
        printMap(sortedData);
    }

    private static void printMap(Map<String, String> data) {
        for (Iterator<String> 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

- user3656845

Answer 6

更新：很抱歉，您无法按值对地图进行排序。

您可以使用SortedMap实现，例如使用TreeMap和Comparator定义按值排序的顺序（而不是默认按键排序）。

或者，更好的方法是，您可以将元素放入具有预定义比较器的PriorityQueue中，该比较器按值排序。与TreeMap相比，它应该更快，占用的内存更少。

- Michał Šrajer

---

请问您能否提供一个如何做到这一点的示例？ - Alexandros

我认为你不能使用优先队列，因为文档说明迭代器不能保证以任何特定顺序遍历队列。 - Timothy Jones

@Timothy Jones：这就是为什么我建议使用PriorityQueue作为替代方案（如果可能的话）。我没有表达清楚。感谢您指出这一点。 - Michał Šrajer

如果我使用按值排序的TreeMap，那么通过键访问项也会很快吗？ - Alexandros

@Alexandros 使用Java TreeMap实现，通过键获取值的时间复杂度为log2(n)，这是由于树结构所致。我不知道这对你来说是否足够快，但它并不是常数时间。 - Peter

为了能够按值对您的TreeMap进行排序，您的键需要包含相应的值。如果这样做，您将很难通过键查找值... - jtahlborn

Answer 7

您可以参考java.util.LinkedHashMap的实现方式。基本思路是使用内部链接列表来存储顺序。以下是一些细节：

继承自HashMap。在HashMap中，每个条目都有一个键和值，这是基本的。您可以添加next和prev指针以按值顺序存储条目。还可以添加头和尾指针以获取第一个和最后一个条目。对于每个修改（添加、删除、更新），您可以添加自己的代码来更改列表顺序。这不过是一次线性搜索和指针切换。

如果条目太多，添加/更新肯定会很慢，因为它是一个链接列表而不是数组。但只要列表排序，我相信有很多方法可以加速搜索。

所以这就是您得到的东西：当通过键检索条目时，具有与HashMap相同速度的映射。一个按顺序存储条目的链接列表。

如果此解决方案符合您的要求，我们可以进一步讨论。

---

给jtahlborn：

正如我所说，如果没有任何优化，它肯定会很慢。由于我们现在谈论的是性能而不是实现，因此可以做很多事情。

一种解决方案是使用树而不是链表，例如红黑树。然后迭代树而不是迭代映射。

关于最小值，这更容易。只需使用成员变量存储最小值，在添加或更新元素时更新最小值。删除时，在树中搜索最小值（这非常快）

如果树太复杂，也可以使用另一个列表/数组来标记列表中的某些位置。例如，每100个元素标记一次。然后在搜索时，先搜索位置列表，然后再搜索真实列表。还需要维护此列表，可能需要在修改一定次数（例如100次）后重新计算位置列表。

- DeepNightTwo

---

OP 表示使用一个可能有数千万条目的集合。使用这么多条目更新“排序”的链表将非常慢。 - jtahlborn

Answer 8

如果您所需的只是“min”值，那么只需使用普通映射并在任何时候跟踪修改后的“min”值即可。

编辑：

所以，如果您真的需要值排序并且想要使用现成的解决方案，您基本上需要两个集合。一个普通映射（例如HashMap），和一个SortedSet（例如TreeSet>）。您可以通过TreeSet遍历有序元素，并通过键使用HashMap查找频率。

显然，您始终可以编写自己的东西，类似于LinkedHashMap，其中元素可以通过键定位并按顺序遍历，但这几乎完全是自定义代码（我怀疑已经存在这种特定的东西，但我可能错了）。

- jtahlborn

---

因为在过程中，我可能会想要删除最小值的条目。在删除该项后，我需要知道下一个最小值的项目。有点像弱链。 - Alexandros

为什么要踩这个回答？@Timothy Jones基本上已经把我的建议写成了被选中的答案。 - jtahlborn