java NavigableMap 与 SortedMap？

NavigableMap vs. SortedMap?

提问by Jason S

Is there any reason to use SortedMapinstead of NavigableMap, besides the JVM version? (NavigableMaphas only been there since 1.6; SortedMaphas been there since 1.2)

除了 JVM 版本之外，还有什么理由可以使用SortedMap而不是NavigableMap？（NavigableMap仅从 1.6SortedMap开始存在；从 1.2 开始存在）

I'm trying to find the value with the greatest key such that key <= reference key K0. I can't seem to figure out how to do this with a SortedMap(if it were strictly <, then I'd call headMap()and then lastKey()and then get()), but NavigableMap.floorEntry()seems to be exactly what I need.

我试图找到具有最大键的值，使得键 <= 参考键 K0。我似乎无法弄清楚如何使用 a SortedMap（如果它是严格的 <，然后我会打电话headMap()然后lastKey()然后get()），但NavigableMap.floorEntry()似乎正是我需要的。

---

---

clarification:just as an example, I'm handling sparse ranges of version numbers with different behavior models. The keys might be [0, 2, 5], so that version numbers 0 and 1 get handled by the value at key #0, version numbers 2-4 get handled by the value at key #2, and version numbers >= 5 get handled by the value at key #5.

澄清：举个例子，我正在处理具有不同行为模型的版本号的稀疏范围。键可能是 [0, 2, 5]，因此版本号 0 和 1 由键 #0 处的值处理，版本号 2-4 由键 #2 处的值处理，版本号 >= 5由键 #5 处的值处理。

回答by Uri

Personally, I'm a big believer in using the least specific interface that provides you with what you need. This makes your intentions clearer and places less restrictions on your possible implementations.

就我个人而言，我坚信使用最不具体的界面来为您提供所需的东西。这使您的意图更加清晰，并且对您可能的实现的限制更少。

Most developers want Sorted collections for iteration purposes and perhaps for random access performance. I've seen very few cases where I needed a close element.

大多数开发人员希望 Sorted 集合用于迭代目的，也可能是为了随机访问性能。我见过很少需要关闭元素的情况。

If you need that functionality, go ahead. I think that TreeMap actually implements NavigableMap. But when you don't need it, why restrict yourself?

如果您需要该功能，请继续。我认为 TreeMap 实际上实现了 NavigableMap。但是当你不需要它时，为什么要限制自己呢？

回答by finnw

Is there any reason to use SortedMap instead of NavigableMap, besides the JVM version?

除了 JVM 版本之外，还有什么理由使用 SortedMap 而不是 NavigableMap 吗？

Yes I can think of one example. The provider of the map may have wrapped it with Collections.unmodifiableSortedMap, so even if the source was a TreeMap(which implements NavigableMap) you only have a reference to a SortedMapand you cannot cast it to NavigableMap.

是的，我可以想到一个例子。地图的提供者可能已经用 包装了它Collections.unmodifiableSortedMap，所以即使源是 a TreeMap（实现了NavigableMap），您也只有对 a 的引用，SortedMap而不能将其强制转换为NavigableMap。

I'm trying to find the value with the greatest key such that key <= reference key K0. I can't seem to figure out how to do this with a SortedMap

我试图找到具有最大键的值，使得键 <= 参考键 K0。我似乎无法弄清楚如何使用 SortedMap 做到这一点

Well there are two cases: either the map contains an exact match for the key or it does not. So first look for an exact match and only if it does not exist then m.headMap(key).lastKey()will give the right answer.

那么有两种情况：要么地图包含与键的完全匹配，要么不包含。所以首先寻找一个完全匹配的，只有当它不存在时m.headMap(key).lastKey()才会给出正确的答案。

---

---

This will do it (though it is not as efficient as a real NavigableMap):

这将做到这一点（尽管它不如 real 有效NavigableMap）：

static <K, V> Map.Entry<K, V> floorEntry(final SortedMap<K, V> m, K key) {
    final SortedMap<K, V> tail; 
    if (m.containsKey(key)) {
        tail = m.tailMap(key);
    } else {
        SortedMap<K, V> head = m.headMap(key);
        if (head.isEmpty()) {
            return null;
        } else {
            tail = head.tailMap(head.lastKey());
        }
    }
    return tail.entrySet()
               .iterator()
               .next();
}

回答by maaartinus

When working with integers you can use x < A+1 instead of x <= A and you're done. I mean headMap(A+1), etc., should do the job. Otherwise, I'd go for finnw's solution since it's more clear than anything I can come out with.

处理整数时，您可以使用 x < A+1 而不是 x <= A 就完成了。我的意思是 headMap(A+1) 等，应该可以完成这项工作。否则，我会选择 finnw 的解决方案，因为它比我能想出的任何东西都更清楚。

回答by kevin cline

Is there any reason to use SortedMap instead of NavigableMap, besides the JVM version?

除了 JVM 版本之外，还有什么理由使用 SortedMap 而不是 NavigableMap 吗？

Yes, if you need to return an unmodifiable map and you are not using Google Guava.

是的，如果您需要返回一个不可修改的地图并且您没有使用 Google Guava。

NavigableMap is intended to supersede SortedMap. NavigableMap adds methods to the SortedMap interface that are needed quite often, are easy to for a Map implementer to add, but are awkward to write in terms of existing SortedMap methods. Returning SortedMap instead of NavigableMap will cause callers of your code unnecessary work.

NavigableMap 旨在取代 SortedMap。NavigableMap 向 SortedMap 接口添加了经常需要的方法，对于 Map 实现者来说很容易添加，但是就现有的 SortedMap 方法而言编写起来很尴尬。返回 SortedMap 而不是 NavigableMap 会导致代码的调用者做不必要的工作。

It's unfortunate that Collections.unmodifiableNavigableMap was not provided. IMO this was likely an oversight, but it wasn't rectified in JDK 1.7 so maybe someone had a reason to leave it out. I suggest using com.google.common.collect.Maps.unmodifiableNavigableMap.

不幸的是，没有提供 Collections.unmodifiableNavigableMap。IMO 这可能是一个疏忽，但它没有在 JDK 1.7 中得到纠正，所以也许有人有理由将它排除在外。我建议使用com.google.common.collect.Maps.unmodifiableNavigableMap。

回答by kevin cline

I think that using Iterators is better than using headMap and tailMap, because it is not efficient. I tested the following code for cases and it works good and floorEntry2 is three times faster than floorEntry1.

我认为使用 Iterators 比使用 headMap 和 tailMap 更好，因为它效率不高。我针对案例测试了以下代码，它运行良好，并且 floorEntry2 比 floorEntry1 快三倍。

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;

import java.util.*;
import java.util.Map.Entry;

import org.junit.Before;
import org.junit.Test;


class TestMapUtils <K,V> {

    public TestMapUtils()
    {

    }

    public Map.Entry<K, V> floorEntry1(final SortedMap<K, V> m, K key) {
        final SortedMap<K, V> tail; 
        if (m.containsKey(key)) {
            tail = m.tailMap(key);
        } else {
            SortedMap<K, V> head = m.headMap(key);
            if (head.isEmpty()) {
                return null;
            } else {
                tail = head.tailMap(head.lastKey());
            }
        }
        return tail.entrySet()
                   .iterator()
                   .next();
    }

    public Map.Entry<K, V> floorEntry2(final NavigableMap<K, V> m, K key) {
        Iterator<Map.Entry<K,V>> i = m.entrySet().iterator();
        Entry<K,V> tailEntry = null;
        if (key==null) {
            while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (e.getKey()==null)
                return null;
            }
        } else {
            while (i.hasNext()) {
            Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                {
                    return e;
                }
                else
                {
                    if (((Integer) e.getKey()).intValue() < (((Integer) key).intValue())) {
                        tailEntry = e;
                    }
                }
            }
        }
        return tailEntry;
    }
}

public class TestSortedMap {

    protected TestMapUtils<Integer, Integer> testMapUtils;
    private NavigableMap<Integer, Integer> sortedMap;
    @Before
    public void setUp()
    {
        testMapUtils = new TestMapUtils<Integer, Integer>();
        sortedMap = addElementsToMap();
    }

    private NavigableMap<Integer, Integer> addElementsToMap() {
        NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        map.put(10, 1);
        map.put(20, 2);
        map.put(30, 3);
        map.put(40, 4);
        map.put(50, 5);
        map.put(60, 6);
        return map;
    }

    @Test
    public void testFloorEntry()
    {

        long startTime1 = System.nanoTime();

        Entry<Integer, Integer> entry = testMapUtils.floorEntry2(sortedMap, 30);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry2(sortedMap, 60);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry2(sortedMap, 70);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry2(sortedMap, 55);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 50);

        entry = testMapUtils.floorEntry2(sortedMap, 31);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry2(sortedMap, 0);
        assertNull(entry);



        long endTime1 = System.nanoTime() - startTime1;

        long startTime2 = System.nanoTime();

        entry = testMapUtils.floorEntry1(sortedMap, 30);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry1(sortedMap, 60);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry1(sortedMap, 70);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 60);

        entry = testMapUtils.floorEntry1(sortedMap, 55);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 50);

        entry = testMapUtils.floorEntry1(sortedMap, 31);
        assertNotNull(entry);
        assertEquals(entry.getKey().intValue(), 30);

        entry = testMapUtils.floorEntry1(sortedMap, 0);
        assertNull(entry);

        long endTime2 = System.nanoTime() - startTime2;

        if ( endTime2 > endTime1 )
        {
            System.out.println("First Execution is faster.. "+endTime1+", "+endTime2);
        } else if ( endTime1 > endTime2 ) {

            System.out.println("Second Execution is faster.. "+endTime1+", "+endTime2);
        } else {
            System.out.println("Execution times are same");
        }

    }

}

回答by Tom

"[NavigableMap] is intended to supersede the SortedMap interface." http://download.oracle.com/javase/6/docs/technotes/guides/collections/changes6.html

“[NavigableMap] 旨在取代 SortedMap 界面。” http://download.oracle.com/javase/6/docs/technotes/guides/collections/changes6.html

Despite this, I agree with Uri: use the least specific interface you can.

尽管如此，我同意 Uri：尽可能使用最不具体的界面。