NavigableMap vs. SortedMapa?

Question

¿Hay alguna razón para usar SortedMap en lugar de NavigableMap, además de la versión de JVM? (NavigableMap ha estado allí desde 1.6; SortedMap ha estado allí desde 1.2)

Estoy tratando de encontrar el valor con la clave más grande como la clave < = clave de referencia K0. Parece que no puedo entender cómo hacerlo con un SortedMap (si fuera estrictamente <, luego llamaría al headMap() y luego a lastKey() y luego a get()), pero NavigableMap.floorEntry() parece ser exactamente lo que necesito.

---

aclaración: sólo como ejemplo, estoy manejando rangos dispersas de los números de versión con diferentes modelos de comportamiento. Las claves pueden ser [0, 2, 5], de modo que los números de versión 0 y 1 se manejan con el valor de la clave # 0, los números de versión 2-4 se manejan con el valor de la clave # 2 y los números de versión> = 5 ser manejado por el valor en la clave # 5.

Answer 1

Personalmente, soy un gran creyente en el uso de la interfaz menos específica que le proporciona lo que necesita. Esto hace que tus intenciones sean más claras y pone menos restricciones a tus posibles implementaciones.

La mayoría de los desarrolladores desean colecciones ordenadas para propósitos de iteración y quizás para el rendimiento de acceso aleatorio. He visto muy pocos casos en los que necesitaba un elemento cercano.

Si necesita esa funcionalidad, siga adelante. Creo que TreeMap realmente implementa NavigableMap. Pero cuando no lo necesita, ¿por qué restringirse?

Answer 2

¿Hay alguna razón para usar SortedMap en lugar de NavigableMap, además de la versión de JVM?

Sí, puedo pensar en un ejemplo. El proveedor del mapa puede haberlo envuelto con Collections.unmodifiableSortedMap, por lo que incluso si la fuente era TreeMap (que implementa NavigableMap), solo tiene una referencia a SortedMap y no puede convertirlo a NavigableMap.

Estoy tratando de encontrar el valor con la clave más grande, tal que la clave < = clave de referencia K0. Parece que no puedo entender cómo hacer esto con un SortedMap

Bien, hay dos casos: el mapa contiene una coincidencia exacta para la clave o no. Por lo tanto, primero busque una coincidencia exacta y solo si no existe, entonces m.headMap(key).lastKey() dará la respuesta correcta.

---

Esto lo hace (aunque no es tan eficiente como un verdadero 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

Cuando se trabaja con números enteros se puede utilizar x < A + 1 en lugar de x < = A y ya terminaste Me refiero a headMap (A + 1), etc., debería hacer el trabajo. De lo contrario, buscaría la solución de finnw ya que es más claro que cualquier cosa con la que pueda salir.

Answer 4

"[NavigableMap] está destinado a reemplazar la interfaz SortedMap." http://download.oracle.com/javase/6/docs/technotes/guides/collections/changes6.html

A pesar de esto, estoy de acuerdo con Uri:.. Usar la interfaz menos específica que pueda

Answer 5

Creo que el uso de iteradores es mejor que usar headMap y tailMap, porque no es eficiente Probé el siguiente código para los casos y funciona bien y floorEntry2 es tres veces más rápido que 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"); 
     } 

    } 

} 

Answer 6

¿hay alguna razón para usar en lugar de SortedMap NavigableMap, además de la versión JVM?

Sí, si necesita devolver un mapa no modificable y no está utilizando Google Guava.

NavigableMap está destinado a reemplazar SortedMap. NavigableMap agrega métodos a la interfaz SortedMap que se necesitan con bastante frecuencia, son fáciles de agregar para un implementador de Map, pero son difíciles de escribir en términos de métodos SortedMap existentes. Al devolver SortedMap en lugar de NavigableMap, los llamantes de su código no trabajarán.

Desafortunadamente no se proporcionó Collections.unmodifiableNavigableMap. IMO esto probablemente fue un descuido, pero no fue corregido en JDK 1.7 así que tal vez alguien tenía una razón para dejarlo. Sugiero usar com.google.common.collect.Maps.unmodifiableNavigableMap.