Java数据结构类似于TreeMap + Hash？

Question

我需要将键值对输入到数据结构中，该数据结构允许我按键的升序检索它们 - 但它们可能是许多具有相同值的键。

因此，如果 kv 对是 {10-a, 10-b, 9-c, 8-d, 8-e, 8-f, 4-g, 4-h, 2-i} 我会需要按顺序检索值:a、b、c、d、e、f、g、h、i。 JAVA API中有支持这个的数据结构吗？

我尝试使用 TreeMap，因为它使它们保持顺序，这使我可以使用 TreeMap.lastKey() 检索当前最高的键，但我不知道它会覆盖 map 中已有的任何重复键。我需要一些不会覆盖的东西(类似于哈希)，但也允许我按排序顺序检索它们 - 这存在吗？

谢谢!

Answer 1

不幸的是，您可能找不到支持相同键的多个值的结构。正如 Dilum 所说，“MultiMap”或“多值 map ”有多种实现方式可以很好地工作。

除了Guava的TreeMultiMap ，还有 Spring 框架的 MultiValueMap和 Apache Common 的 MultiValueMap .

Spring 实现的一个示例是:

import org.springframework.util.LinkedMultiValueMap;
import org.springframework.util.MultiValueMap;


public class MultiValueMapExample {

    public static void main(String[] args) {
        // 10-a, 10-b, 9-c, 8-d, 8-e, 8-f, 4-g, 4-h, 2-i
        MultiValueMap<Integer, String> map = new LinkedMultiValueMap<Integer, String>();
        map.add(10, "a");
        map.add(10, "b");
        map.add(9, "c");
        map.add(8, "d");
        map.add(8, "e");
        map.add(8, "f");
        map.add(8, "g");
        map.add(4, "h");
        map.add(2, "i");

        System.out.println(map.toString());
        // {10=[a, b], 9=[c], 8=[d, e, f, g], 4=[h], 2=[i]}
    }
}

您可以通过以下 Maven 依赖项添加 Spring-Core 来使用它:

<dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-core</artifactId>
            <version>3.1.1.RELEASE</version>
        </dependency>

如果您需要帮助在您的项目中获取这些库中的任何一个，请随时发表评论/联系我。

更新 1

事实证明，没有一种方便的方法可以从原始 API 中进行过滤/排序。我在下面添加了一个简单的过滤函数，应该可以解决这个问题。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.springframework.util.LinkedMultiValueMap;
import org.springframework.util.MultiValueMap;


public class MultiValueMapExample {

    public static void main(String[] args) {
        // 10-a, 10-b, 9-c, 8-d, 8-e, 8-f, 4-g, 4-h, 2-i
        MultiValueMap<Integer, String> map = new LinkedMultiValueMap<Integer, String>();
        map.add(8, "g");
        map.add(4, "h");
        map.add(10, "a");
        map.add(10, "b");
        map.add(9, "c");
        map.add(8, "d");
        map.add(8, "e");
        map.add(8, "f");

        map.add(2, "i");

        System.out.println(map.toString());
        // {8=[g, d, e, f], 4=[h], 10=[a, b], 9=[c], 2=[i]}

        MultiValueMap<Integer, String> filteredMap = filter(5, map);
        System.out.println( filteredMap.toString() );
        // {10=[a, b], 9=[c], 8=[g, d, e, f], 4=[h], 2=[i]}

    }

    public static MultiValueMap<Integer, String> filter(int numberOfResults, MultiValueMap<Integer, String> map){
        MultiValueMap<Integer, String> result = new LinkedMultiValueMap<Integer, String>();

        List<Integer> keys = new ArrayList<Integer>(map.keySet());
        Collections.sort(keys, Collections.reverseOrder());

        for(Integer key : keys){
            if( result.size() <= numberOfResults ){
                result.put(key, map.get(key));
            }else{
                break;
            }
        }

        return result;

    }
}