Java Map值比较器，插入时排序

Question

我希望能够使用值比较器将项目插入到HashMap、TreeMap或SortedMap（您可以建议一些其他的API）中。我已经阅读了许多帖子，包括这个one，大多数帖子建议在插入所有项后重新将HashMap插入到具有值比较器的SortedMap中。

我不想重新插入所有值。有没有选项或类似数据结构的Map，在每次插入后都支持激活值比较器？

如果有重复的问题，我会感激一个链接（我已经做了一些搜索，尽管我可能错过了一些）

再次强调，我希望添加一个值到某种有序Map中，以便所有项目都按值而不是键排序，在每个单独的插入后。

Map条目中的值实际上是一个带有一些getter的复杂对象，我只想按值对象上的特定getter排序。

- Michael

---

你可以将这些项插入到 TreeMap 中，并在其构造函数中为 TreeMap 提供所需的比较器。就像你已经链接到的问题中所展示的那样。 - DNA

为什么您不喜欢您在问题中提到的答案呢？您需要一个有序映射 - 使用TreeMap。您需要按值中的特定字段进行比较 - 使用建议的valuecomparator，实现会稍微改变但比例仍然相同。 - Mark Bramnik

@MarkBramnik 这些映射传递的是键而不是值，对吗？ - Andrew White

@DNA：TreeMap不接受值比较器作为输入，只接受键比较器。 - Michael

@Mark Bramnik：请再次查看解决方案，它需要重新插入所有项，“sorted_map.putAll(map);” TreeMap本身无法接收值比较器。 - Michael

@Michael - 这个链接的示例清楚地展示了使用按值排序的比较器初始化TreeMap。我会称之为“值比较器”。但是，请阅读有关该解决方案的各种问题的评论。 - DNA

Answer 1

我认为你需要的是org.apache.commons.collections.bidimap.TreeBidiMap。

基于红黑树实现的BidiMap，所有添加到其中的对象都必须实现Comparable接口。

该类保证映射按照键和值的自然顺序以升序排列，即键和值的类的自然顺序。

- Amit Deshpande

---

感谢您的解决方案，我更倾向于不使用任何外部库。 - Michael

Answer 2

我想到了一些解决方法，虽然不完美并且会使用更多的内存，但它相当简单。我可以扩展Map的键来保存Value对象getter返回的值，然后扩展键比较器按键的正确元组进行排序。 更新 非常好地工作，并具有良好的性能表现。

- Michael

---

如果键保存了值，你如何从映射中检索值？你需要知道排序值才能获取对象值吗？ - ygesher

Answer 3

地图的本质是将键映射到值。Guava有一个双向映射的概念，但您实际上并不关心从值到键的映射，而是希望公开排序后的值迭代。我建议创建一个自定义容器，其中包含HashMap和优先队列。

因此，扩展Map、Collection和Iterable接口，并在添加时将元素插入到HashMap和Priority Queue中。当您进行迭代时，请遍历队列；当您搜索/获取时，请转到Map。

- Andrew White

Answer 4

我正在寻找类似的东西，但无法使用TreeBidiMap，因为它要求Map的键实现Comparable接口。

所以我写了自己的极简ValueTreeMap：

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;

public class ValueTreeMap<K, V extends Comparable<V>> implements Iterable<V> {
    private TreeSet<V> tree = new TreeSet<V>();
    private HashMap<K, V> map = new HashMap<K, V>();

    public void put(K key, V value){
        V oldValue = map.get(key);
        if(oldValue != null){
            tree.remove(oldValue);
        }
        tree.add(value);
        map.put(key, value);
    }

    public V get(K key){
        return map.get(key);
    }

    @Override
    public Iterator<V> iterator() {
        return tree.iterator();
    }

}

- Crigges

---

我扩展了你的解决方案，构建了一个实现Map接口的类：github。 - ygesher