¿Existe una estructura de datos para este tipo de lista / mapa?

22

Quizás haya un nombre para lo que quiero, pero no lo sé. Necesito algo similar a a LinkedHashMapen Java, pero donde devuelve el valor 'anterior' si no hay ningún valor en la clave especificada.

Es decir, tengo una lista de objetos almacenados por una clave entera (que en mi caso es en unidades de tiempo):

; key->value
10->A
15->B
20->C

Entonces, si tuviera que consultar un valor para la clave 0-9, volvería null. La parte especial es que si consultara por algo 10 <= i <= 14 devolvería A. O, para i> = 20, devolvería C.

¿Hay una estructura de datos para esto?

java data-structures Mella
fuente
No sé si hay uno implementado, pero probablemente podría extender el existente para hacer esto. Si cumplirá con sus objetivos de rendimiento o no sin una reescritura, no lo sé ...
Rig
1
+1 para la gran pregunta. La mayoría de las personas con tres representantes de dígitos bajos hacen el tipo de pregunta "por favor haga mi tarea". No es el caso aquí.
Tulains Córdova

Respuestas:

33

Estás buscando un NavigableMap . Este es un subtipo de SortedMap que también tiene algunas funciones disponibles además de la naturaleza del mapa que se está ordenando. Tenga en cuenta que el mapa navegable "está destinado a reemplazar la interfaz SortedMap". ( Mejoras del marco de colecciones de Java SE 6 ). Todo lo que actualmente implementa se SortedMapimplementa, NavigableMapy es probable que esto siga siendo cierto.

En particular, el método floorKey(K key)que "devuelve la clave más grande menor o igual que la clave dada, o nulo si no existe dicha clave.

Este es solo uno de los muchos métodos que le permiten obtener claves específicas o submapas del mapa.

  • techo / piso (la entrada que es más alta / más baja que el parámetro)
  • acceso de llaves o mapa en orden descendente
  • head / tail (las entradas menor / mayor que una clave dada)
  • Mayor / menor (la siguiente tecla que es mayor o menor que el parámetro)
  • submapa (dadas dos claves, devuelve el mapa que está entre las dos claves)

Java tiene dos implementaciones de NavigableMap : TreeMap y ConcurrentSkipListMap .

Si observa la idea / implementación de una lista de omisión , verá por qué funcionaría realmente bien con dicha estructura y sus consultas.


fuente
1+ gran respuesta. Nunca pensé que existiera un mapa tan específico en la API de Java.
Tulains Córdova
@ user61852 Mi tipo de datos favorito es la lista de omisión y busqué con ella. Cuando lo vi implementado en 1.6, investigué todo lo que proporcionaba y noté las interfaces que tenía y, por lo tanto, mi familiaridad con él.
Ese es el tipo de cosas que me convencen de que Java es uno de los lenguajes mejor diseñados que puedes encontrar.
Tulains Córdova
1
Tenga en cuenta que si bien esto parece abordar el problema de OP, no actúa como lo LinkedHashMapque él menciona. Ni TreeMaptampoco ConcurrentSkipListMapse ordenan por tiempo de inserción como LinkedHashMap, sino que se ordenan por una Comparatoro el orden natural de la clave si se implementan Comparable.
MikeFHay
1
Muy buen punto. La operación de piso es lo que estaba buscando, el comparador que puedo agregar fácilmente. Y en mi caso, resulta mucho mejor implementar el comparador en lugar de reinventar la rueda. Gracias.
Nick
1

Lo que está buscando es una tabla de símbolos que admita operaciones ordenadas. Y en su caso es la operación de piso.

La implementación hash de una tabla de símbolos es la más rápida, pero no ofrece esas operaciones ordenadas.

Pero la implementación en árbol de las tablas de símbolos sí. Un ejemplo de eso en Java es la clase TreeMap

Moha el todopoderoso camello
fuente