NavigableMap 与 SortedMap？

问题描述 投票：0回答：6

除了 JVM 版本之外，还有什么理由使用 

SortedMap
代替 
NavigableMap
 吗？ （
NavigableMap
自1.6以来才存在；
SortedMap
自1.2以来一直存在）

我正在尝试找到具有最大键的值，例如键<= reference key K0. I can't seem to figure out how to do this with a 

SortedMap
（如果严格来说是<, then I'd call 
headMap()
，然后是
lastKey()
，然后是
get()
），但是
NavigableMap.floorEntry()
似乎正是我需要。

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

java sorting dictionary
6个回答
11
投票

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

大多数开发人员希望排序集合用于迭代目的，或许还为了随机访问性能。我见过很少需要闭合元素的情况。

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

9
投票

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

是的，我能想到一个例子。地图的提供者可能已经用 

Collections.unmodifiableSortedMap
包装了它，因此即使源是 
TreeMap
（实现 
NavigableMap
），您也只能引用 
SortedMap
并且不能将其转换为 
NavigableMap
.

我正在尝试找到具有最大键的值，例如该键<= reference key K0. I can't seem to figure out how to do this with a SortedMap

有两种情况：要么映射包含与键完全匹配的内容，要么不包含。因此，首先查找完全匹配，只有当它不存在时，

m.headMap(key).lastKey()
才会给出正确的答案。

这样就可以了（尽管它不如真正的

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();
}
6
投票

除了 JVM 版本之外，还有什么理由使用 

SortedMap
代替 
NavigableMap
吗？

是的，如果您需要在 Java 7 或更早版本上返回不可修改的地图，并且您没有使用 Google Guava。

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

不幸的是没有提供

Collections.unmodifiableNavigableMap
。 IMO 这可能是一个疏忽，但它在 JDK 1.7 中没有得到纠正，所以也许有人有理由忽略它。然而，它是在 Java 8 中添加的。我建议使用
com.google.common.collect.Maps.unmodifiableNavigableMap
。

3
投票

使用整数时，您可以使用 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.

3
投票

我认为使用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");
        }

    }

}
1
投票

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

尽管如此，我还是同意 Uri 的观点：使用尽可能不具体的接口。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.