NavigableMapとSortedMapの比較

Question

NavigableMapの代わりにSortedMapをJVMバージョン以外に使用する理由はありますか？ （NavigableMapは1.6以来ずっとそこにいた;

私はキー< =参照キーK0というような最大のキーで値を見つけようとしている。私はSortedMapでこれを行う方法を考え出すことができません（もしそれが厳密に<だったら、headMap()とし、lastKey()と呼んでget()と呼ぶでしょう）、しかしNavigableMap.floorEntry()が私の必要とするようです。

---

明確化：単なる一例として、私は別の行動モデルとバージョン番号のまばらな範囲を扱いますよ。キーは[0、2、5]かもしれないので、バージョン番号0と1はキー＃0の値で処理され、バージョン番号2-4はキー＃2の値で処理され、バージョン番号> = 5キー＃5の値で処理されます。

Answer 1

個人的に、私はあなたに必要なものを提供する最も特殊なインターフェイスを使用していると信じています。これはあなたの意図をより明確にし、可能な実装に制限を少なくします。

ほとんどの開発者は、ソートされたコレクションを反復目的やランダムアクセスパフォーマンスのために使用したいと考えています。私は密接な要素が必要なケースはごくわずかでした。

この機能が必要な場合は、先に進んでください。 TreeMapは実際にNavigableMapを実装していると思います。しかし、あなたがそれを必要としないときは、なぜあなた自身を制限するのですか？

Answer 2

NavigableMapの代わりにSortedMapを使用する理由はありますか？

はい私は1つの例を考えることができます。マップのプロバイダはCollections.unmodifiableSortedMapでラップしている可能性があります。したがって、ソースがTreeMap（NavigableMap）の場合でも、SortedMapへの参照のみがあり、NavigableMapにキャストできません。

キー< =参照キーK0というような最大のキーで値を見つけようとしています。私は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(); 
} 

Answer 3

あなたの代わりにX < = Aのx < A + 1を使用することができ、整数と協力し、あなたは終わった。私はheadMap（A + 1）など、仕事をする必要があります。さもなければ、私はfinnwの解決策に行くだろう。なぜなら、私が出てくるものよりもはっきりしているからだ。

Answer 4

"[NavigableMap]は、SortedMapインターフェイスに取って代わるものです。「これにもかかわらず http://download.oracle.com/javase/6/docs/technotes/guides/collections/changes6.html

が、私はウリに同意する：。。あなたができる少なくとも特定のインターフェイスを使用し

Answer 5

私はイテレータを使用してのheadMapとのtailMapを使用するよりも優れていると思い、それは効率的ではないので、私は次のようにテストしました例のコードと、それは良い作品とfloorEntry2がfloorEntry1より3倍高速である。

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"); 
     } 

    } 

} 

Answer 6

JVMのバージョンのほかに、代わりにNavigableMapのののSortedMapを使用する理由はありますか？

はい、Google Guavaを使用していない、変更不可能な地図を返す必要がある場合。

NavigableMapはSortedMapに取って代わるものです。 NavigableMapは、メソッドをSortedMapインターフェイスに追加します。これらのメソッドは非常に頻繁に必要とされ、Map実装者が追加するのは簡単ですが、既存のSortedMapメソッドに関して記述するのは難しいです。 NavigableMapではなくSortedMapを返すと、コードの呼び出し元が不要になります。

Collections.unmodifiableNavigableMapが提供されていないことは残念です。 IMOこれは見落としの可能性が高いですが、JDK 1.7では修正されていないので、誰かがそれを無視する理由があったかもしれません。 com.google.common.collect.Maps.unmodifiableNavigableMapを使用することをお勧めします。