Estructuras de datos que pueden asignar un rango de claves a un valor

Estoy tratando de encontrar una estructura de datos que tome un valor particular de un rango de valores y lo asigne a una clave.

Por ejemplo, tengo las siguientes condiciones:

  1. De 1 a 2.9, quiero asignarlo a A.
  2. De 4 a 6, quiero asignarlo a B.
  3. De 6.5 a 10, quiero asignarlo a C.

Tengo un valor de 5 y me gustaría asignarlo a una clave. Por lo tanto, en base a las condiciones anteriores, debería asignarlo a B.

¿Hay alguna estructura de datos en Java que alguien me pueda recomendar para resolver el problema?

Actualmente estoy usando una tabla hash que solo puede asignar un valor a una clave. Traté de asignar el rango de valores a un valor particular que existe en la tabla hash. Sin embargo, me quedé atrapado en el mapeo del rango de valores a un valor particular. Así que ahora estoy tratando de hacer otra forma de mapear los rangos de valores a una clave. ¿Alguien tiene alguna idea de cómo puedo resolver este problema?

EDITAR:

Gracias a Martin Ellis, decidí usar TreeMap para resolver el problema.

¿Sus rangos no se superponen? Si es así, podrías usar un TreeMap:

TreeMap m = new TreeMap(); m.put(1.0, 'A'); m.put(2.9, null); m.put(4.0, 'B'); m.put(6.0, null); m.put(6.5, 'C'); m.put(10.0, null); 

La lógica de búsqueda es un poco complicada por el hecho de que probablemente desee una búsqueda inclusiva (es decir, 2.9 mapas a ‘A’, y no indefinido):

 private static  V mappedValue(TreeMap map, K key) { Entry e = map.floorEntry(key); if (e != null && e.getValue() == null) { e = map.lowerEntry(key); } return e == null ? null : e.getValue(); } 

Ejemplo:

 mappedValue(m, 5) == 'B' 

Más resultados incluyen:

 0.9 null 1.0 A 1.1 A 2.8 A 2.9 A 3.0 null 6.4 null 6.5 C 6.6 C 9.9 C 10.0 C 10.1 null 

Esto parece una situación natural para usar una estructura de árbol.

Lamentablemente, no será práctico implementar la interfaz java.util.Map porque especifica un método para devolver todas las claves, y en su situación, teóricamente, tiene una cantidad de teclas poco práctica.

Cada nodo de su árbol debe tener una clave mínima, una clave máxima y un valor asociado con ese rango. A continuación, puede tener enlaces a los nodos que representan el siguiente rango más alto y el siguiente más bajo (si existen). Algo como:

 public class RangeMap, V> { protected boolean empty; protected K lower, upper; protected V value; protected RangeMap left, right; public V get(K key) { if (empty) { return null; } if (key.compareTo(lower) < 0) { return left.get(key); } if (key.compareTo(upper) > 0) { return right.get(key); } /* if we get here it is in the range */ return value; } public void put(K from, K to, V val) { if (empty) { lower = from; upper = to; value = val; empty = false; left = new RangeMap(); right = new RangeMap(); return; } if (from.compareTo(lower) < 0) { left.put(from, to, val); return; } if (to.compareTo(upper) > 0) { right.put(from, to, val); return; } /* here you'd have to put the code to deal with adding an overlapping range, however you want to handle that. */ } public RangeMap() { empty = true; } } 

Si necesita búsquedas más rápidas de las que puede proporcionar el árbol, es posible que desee buscar algo así como una lista de omisiones o desarrollar su propia función hash.

Un HashMap no funcionará para mapear rangos a valores a menos que encuentre una forma de generar un código hash para rangos y valores individuales que coincidan. Pero por debajo del enfoque podría ser lo que estás buscando

 public class RangeMap { static class RangeEntry { private final double lower; private final double upper; private final Object value; public RangeEntry(double lower, double upper, Object mappedValue) { this.lower = lower; this.upper = upper; this.value = mappedValue; } public boolean matches(double value) { return value >= lower && value < = upper; } public Object getValue() { return value; } } private final List entries = new ArrayList(); public void put(double lower, double upper, Object mappedValue) { entries.add(new RangeEntry(lower, upper, mappedValue)); } public Object getValueFor(double key) { for (RangeEntry entry : entries) { if (entry.matches(key)) return entry.getValue(); } return null; } } 

Podrías hacerlo

 RangeMap map = new RangeMap(); map.put(1, 2.9, "A"); map.put(4, 6, "B"); map.getValueFor(1.5); // = "A" map.getValueFor(3.5); // = null 

No es muy eficiente ya que solo itera sobre una lista y en ese estado no se quejará si coloca rangos conflictivos allí. Simplemente devolverá el primero que encuentre.

PD: mapear así sería mapear un rango de claves a un valor

Este tipo de estructura de datos se denomina Árbol de Intervalos . (La página de Wikipedia solo presenta el caso donde los intervalos pueden superponerse, pero uno puede imaginar un caso en el que desee eliminar asignaciones para cualquier intervalo superpuesto cuando agregue un nuevo intervalo. Haga una búsqueda en Google de implementaciones y vea si se ajusta a sus necesidades.

Guava RangeMap proporciona una solución especializada lista para usar :

 RangeMap rangeMap = TreeRangeMap.create(); rangeMap.put(Range.closed(1, 100), "foo"); // {[1, 100] => "foo"} rangeMap.put(Range.open(3, 6), "bar"); // {[1, 3] => "foo", (3, 6) => "bar", [6, 100] => "foo"} rangeMap.get(42); // returns "foo" 

solo tiene una lista como valor en su mapa.

 Map> map = new HashMap>(); 

y también una sugerencia :

no use Hashtable a menos que desee un acceso sincronizado.

EDITAR:

Los métodos Hashtable están sincronizados, es decir, no hay dos subprocesos que puedan acceder a esos métodos en un único punto de tiempo. Los elementos de HashMap no están sincronizados. Si usas Hashtable habrá un golpe de rendimiento. usa HashMap para un mejor rendimiento.

Una de las maneras sería usar una implementación de lista como valor para la clave.

 map.put("A", ArrayList);